Abstract: As a thread-level automatic parallelization technique, thread-level speculation (TLS) can partition irregular serial programs into multiple threads and implement these threads in parallel on multi-core architectures to improve the performance of programs. In view of the problem that the conventional heuristic rules-based (HR-based) thread partitioning method partitions the programs of different characteristics with the same scheme and several programs have bad partitioning effects, this paper proposes a machine learning based (ML-based) thread partitioning  approach, which uses a machine learning method to learn the knowledge of thread partitioning from TLS sample set, and predicts the schemes of thread partitioning for unknown programs, and finally applies the schemes to thread partitioning. In Prophet compilation system, Olden benchmarks are used to evaluate the proposed approach, and a comparison is made between the proposed approach and conventional heuristic rules-based partitioning approach. The experimental results show that the proposed approach can deliver an average 18.24% speedup improvement than HR-based thread partitioning approach.

Key words: thread-level speculation, thread partitioning, program characteristics, partition scheme

摘要： 作为一种线程级自动并行化技术，线程级推测（thread-level speculation，TLS）能够将非规则串行程序划分为多个线程，并采用一种激进的方式在多核体系结构上并行执行这些线程，以此提高程序的执行加速性能。针对现有的启发式划分方法对不同特征的程序采用的策略划分，导致部分程序划分效果较差的问题，提出利用机器学习方法从TLS样本集中学习线程划分的知识，并根据程序的特征预测其划分方案，并利用此划分方案对其进行划分。在Prophet编译系统上使用Olden基准程序集对基于程序特征的线程划分方法进行评估，并与传统的基于启发式规则划分效果进行比较，实验结果表明，比启发式规则划分方案获得的加速比平均提升了18.24%。

关键词: 线程级推测, 线程划分, 程序特征, 划分方案