基于特征集与AST的机器学习驱动speculative多线程虚拟样本生成

89 浏览量更新于2024-08-26 收藏 284KB PDF 举报

本文主要探讨了一种基于特征集和抽象语法树的推测性多线程虚拟样本生成方法（AVirtualSampleGenerationApproachforSpeculativeMultithreading UsingFeatureSetsandAbstractSyntaxTrees）。推测性多线程（Speculative Multithreading, SpMT）是一种旨在提升顺序程序执行效率的自动并行化技术，通过在编译时或运行时预测可能的并行执行路径来加速代码执行。传统基于启发式规则的方法虽然能够找到局部最优的推测性线程解决方案，但受限于经验依赖，往往无法达到性能的极限。为了克服这种局限，本文提出采用机器学习策略，尤其是当程序的非规则性使得单纯依靠经验规则难以建立有效的训练模型时。作者首先从Olden基准测试集中构建特征集，这些特征代表了程序的关键行为模式和结构。接着，通过扰动原有特征集，创造出新的特征集，目的是增加模型的泛化能力，使其能适应更多种类的程序。在这个过程中，抽象语法树（Abstract Syntax Trees, ASTs）被用来解析和转换程序的结构，以便从中生成虚拟样本。AST提供了程序的高层次语义表示，有助于捕捉潜在的并行性。通过这种方式，本文的方法不仅能够学习到更全面的程序特性，还能生成多样化的虚拟样本，从而提高推测性多线程技术的精度和性能。与仅依赖启发式规则的方法相比，这种方法具有更高的灵活性和适应性，有望突破性能瓶颈，尤其是在处理复杂和非结构化的程序时。这篇研究论文将特征工程、抽象语法树分析和机器学习相结合，提出了一种新颖的推测性多线程虚拟样本生成策略，为并行程序优化提供了一种有前景的新途径。这种方法对于推动并行计算领域的发展具有重要的理论价值和实践意义。

A Virtual Sample Generation Approach for Speculative Multithreading

Using Feature Sets and Abstract Syntax Trees

Bin Liu,Yinliang Zhao,Meirong Li,Yanzhao Liu, Boqin Feng

School of Electronic and Information Engineering

Xi’an Jiaotong University

Xi’an, China

liubin2010@stu.xjtu.edu.cn, zhaoy@mail.xjtu.edu.cn, wodilili@126.com, erdoslyz@yahoo.cn, bqfeng@mail.xjtu.edu.cn

Abstract—Speculative multithreading (SpMT) is a thread level

automatic parallelization technique to accelerate sequential

programs. Since approaches based on heuristic rules only get

the local optimal speculative thread solution and have reached

their speedup performance limit, machine learning approaches

have been introduced into speculative multithreading to avoid

the shortcomings of the heuristic rules relied on experience.

However, few irregular programs can meet the need for

training model of machine learning. To solve this problem, we

first build feature sets based on Olden benchmarks and then

disturb them into new sets. With the new sets, virtual samples

are generated by abstract syntax trees (ASTs). By this means,

we effectively resolve the shortage of samples for speculative

multithreading based on machine learning. On Prophet, which

is a generic SpMT processor to evaluate the performance of

multithread programs, the validity of virtual samples is

verified and reaches an average speedup of 1.47. Experiments

show that the virtual samples can simulate a variety of

procedure structures of Olden benchmarks and this sample

generation technique can provide sufficient samples for

training model.

Keywords-Speculative Multithreading; Machine Learning;

Program Features;Virtual Samples;Automatic Parallelization

I. INTRODUCTION

Multi-core processors are now the mainstream processor

architectures, offering more computing and storage resources,

increasing communication bandwidth and reducing

communication delay. To improve the irregular program

speedup performance on multi-core processors, huge amount

of sequential application programs must be reconstructed so

that they can be executed in parallel [1]. Thread-level

speculation (TLS), also known as SpMT, is an automatic

parallelization of sequential programs on multi-core

processors by parallelizing compiler technology [2].

Compared with manual parallelization, TLS can accelerate

irregular sequential application programs with lowest cost

and without user interactions. Examples of TLS include

Multiscalar, Hydra [3], Pinot [4], POSH [5] and Mitosis [6].

In recent years, machine learning approaches have been

introduced into TLS. Khan et al. [7] extracted features from

sequential programs and used machine learning algorithms to

cross-validate programs. The features were mapped to a

model library to get the program’s executive performance.

Tournavitis et al. [8] extracted the features of control and

data dependences in sequential programs to establish

analysis model. Taking the run-time information as training

samples, they could predict the potential concurrency units

of the program, get the right candidate threads and achieve

better results. Though this approach performed effectively,

only static program features were extracted and insufficient

information of programs were obtained. Wang et al. [9]

developed an automatic compiler-based approach to map a

parallelized program to multi-core processors using machine

learning. They focused on determining the best number of

threads for a parallel program and how they were scheduled.

However, as the feature values of the samples were

estimated, the model was imperfect and imprecise. Although

these research work had some effect in TLS, there are still a

lot of problems.

Sufficient training samples are an important guarantee for

generalization capability of learning model. In 1992, Vetter

et al. [10] proposed the idea of virtual sample, and they

generated virtual samples for image recognition by

geometric transformation. In [11], Li et al. proposed a non-

linear virtual sample generation technique using the group

discovery technology and parametric equations of

hypersphere. Different streaming parallel programs as

training examples for machine learning models were

generated by stream program generator in [12].

In our study, we proposed an automatic compiler-based

approach to partition irregular programs into ideal partition

structures by machine learning. This approach consists two

stages: first, using machine learning, useful knowledge are

obtained from the samples for guiding thread partitioning,

each sample contain an irregular sequential program and the

corresponding an ideal partition structure which can obtain

maximum speedup on multi-core processors. Then, we use

the knowledge to guide the thread partitioning. After that, we

get an ideal partition structure when a new irregular program

should be dealt with.

As sample sets are not enough for training model, we

proposed a sample generation approach to compensate for

the existing benchmark sets. First, features influencing

program’s speedup were studied in irregular application

programs and constructed feature sets based on Olden

benchmarks. After that, new sets were generated by

disturbing them, then the virtual samples were generated

based on abstract syntax trees. Finally, the validity of virtual

2012 13th International Conference on Parallel and Distributed Computing, Applications and Technologies

DOI 10.1109/PDCAT.2012.33

下载后可阅读完整内容，剩余5页未读，立即下载

weixin_38624628

粉丝: 8
资源: 934

基于特征集与AST的机器学习驱动speculative多线程虚拟样本生成

推测性多线程处理中的类似样本清洗

C#多线程执行

机器学习驱动的推测多线程线程分配优化

视觉特征组合构造的零样本学习方法

DEAP数据集特征提取方法：近似熵、排列熵、样本熵

利用GAN技术实现恶意软件对抗样本生成（Python项目实践）

Yolo目标检测对抗样本的生成与隐身策略

掌握按键精灵多线程编程技巧

多线程内存越界问题定位与解决实战

Java实现的多线程弹球小游戏详解

最新资源