基于线程级推测的非规则算法并行化研究

Irregular algorithms use pointer-based data structures to solve the problem, resulting in ambiguity of data dependences and control dependences that can be determined when algorithms are executed. The existing parallel strategies adopt static analysis technology to deal with these dependences, consequently, there are no good performance. As a result, it is one of key science problems that irregular algorithms are hard to parallel and parallelism of them is not high on multi-core platform. In this research, thread-level speculation technique is introduced into the parallelization of irregular algorithms in order to solve these ambiguous dependences and increase the degree of parallelism. By studying the parallel law of irregular algorithms, parallel programming model based on thread-level speculation will be built in order to construct explicitly parallel irregular algorithms. Using the theoretical analysis and experimental verification, evaluation model based on probability graph will be established for selecting dynamically and evaluating the performance for given execution model. By studying the relationship between features of irregular algorithm, scheduling methods and speedups, the scheduling method based on machine learning is proposed for predicting the optimal scheduling method. The goal of this project is to propose theories and methods for the parallelization of irregular algorithms based on thread-level speculation, and narrow the gap between the performance that irregular algorithm can achieve and the potential performance of multi-core platform. The expected result of this research can be applied to accelerate irregular application on multi-core platform. At same time, this project will bring new ideas and ways for the research on high-parallel algorithms of irregular algorithms.

非规则算法采用基于指针的数据结构解决问题，导致具有模糊关系的数据和控制依赖在运行时才能确定，现有的并行策略通过静态分析技术解决依赖问题，使得并行化效果不佳，非规则算法在多核平台上面临难以并行以及并行度不高这一科学问题。本课题拟借助线程级推测技术消解模糊依赖，增加算法运行时的并行度，解决上述问题。研究非规则算法并行规律，建立线程级推测并行编程模型，用于显式构造并行非规则算法；运用理论分析和实验验证方法，构建基于概率图的性能评估模型，实现对执行模型的性能评估及动态选择；研究非规则算法特征、调度方法和加速比之间的关系，提出基于机器学习的线程级推测调度方法，为算法预测出最优调度方法。研究目标是提出基于线程级推测的非规则算法并行化理论和方法，缩短非规则算法所能达到的性能和多核平台具有的潜在性能之间的“软差距”。预期成果可应用于多核平台加速非规则应用，为实现高并行度的非规则算法探索新途径，提供新思路。

本项目通过TLS编程模型显式构造非规则算法、动态选择TLS执行模型和预测最优的TLS调度方法相结合的研究思路，为非规则算法并行化提供了多措并举的TLS加速机制，缩短非规则算法所能达到的性能和多核处理器具有的潜在性能之间的“软差距”，解决了非规则算法在多核平台上难以并行以及并行度不高这一问题。研究了非规则算法内在特征与数据结构，提出TLS并行编程模型，简化了TLS编程难度，减轻了算法开发者TLS编程的负担，提高了并行非规则算法的开发效率。研究了TLS执行模型推测机制，构建了基于概率图和智能算法的TLS性能评估模型，实现了定量快速地对给定TLS执行模型进行性能评估及动态选择，模型能够有效地评判TLS执行模型的优劣程度，并为非规则算法提供最佳推测机制。研究了非规则算法TLS特征设计及特征约减技术，构建了蕴含TLS特征、调度方法和加速比规律的样本集，提出了基于机器学习的TLS调度方法，为具有不同特征的非规则算法预测出适合自身特征的最优调度方法，减少了推测多线程执行的冲突率，提升了推测线程执行的成功率。本项目的预期目标均已达到，已发表论文17篇（SCI检索9篇，EI检索7篇），申报国家发明专利1项，获批软件著作权2项，协助培养博士生2名，已毕业1名，参与项目研究的硕士生6名，已毕业2名。.本项目所取得的研究成果可用于多核平台加速非规则应用，具有多方面科学意义。（1）提出的基于TLS的非规则算法并行化核心理论与方法，对开发新的并行编译器以及非规则算法自动并行化具有重要的理论意义和应用价值，将在网络分析、人工智能等非规则应用方面具有广泛的应用前景和潜在价值；（2）所提性能评估模型蕴含了TLS执行模型在各种影响因素作用下与加速比性能的内在规律，揭示了各种TLS执行模型的推测并行性能，且独立于实际运行环境，对研发新型多核处理器具有重要意义，可用于TLS体系结构设计及评测方面。