基于机器学习的线程级推测模型和编译优化方法研究

线程级推测（TLS）是多核体系结构上加速串行程序的一种线程级自动并行化技术，TLS加速机制的性能受到软硬件多种复杂因素制约，已有的基于软硬件协同设计和启发式规则的编译优化方法带有经验性弱点。本项目首次提出TLS样本集以及从样本集中学习线程划分知识的思想，克服了经验性方法的弱点。研究基于机器学习的TLS模型，包括：TLS特征设计、特征值获取及表示，构建TLS样本集的方法和关键技术，学习算法，以及线程划分知识的表示及评价。提出基于机器学习的TLS线程划分方法，并基于课题组研制的Prophet编译系统实现新方法，预期经Olden基准程序测试比现有加速机制提高性能20%以上。研究目标是揭示TLS线程划分影响程序加速比的内在规律，证实机器学习能够全面提高TLS性能，为支持TLS的软硬件协同设计提供新途径。预期成果可应用于多核处理器体系结构设计、多核编译器、多核并行计算等领域以及加速现有串行应用程序。

本课题是研究基于机器学习的线程级推测模型和编译优化方法，首次提出线程级推测（TLS：Thread Level Speculation）样本集以及从样本集中学习线程划分知识的思想，克服了经验型方法的弱点。在此基础上取得的创新性研究成果分为线程级推测模型和编译优化两部分。首先，在基于机器学习的线程级推测模型方面：提出了一种有效的TLS特征设计、获取与表示方法，解决了机器学习方法在线程划分过程中知识的来源和表达的问题；提出了一种有效的构建TLS样本集的方法，该方法能够在基于机器学习的TLS划分过程中表达知识和指导划分；提出多个应用于TLS的机器学习算法并有效应用于指导TLS线程划分过程；提出了TLS中线程划分的理论评价模型，实现用概率模型预测线程划分的加速比以及预测最佳划分位置。在编译优化方面，首先在编译器端采用贪心的线程提取和自适应的线程推测并行机制，对循环提出了一种静态贪心的循环选择与动态自适应的循环并行方法；其次，对非循环提出了一种基于FP-growth的多路径选择与激发方法，利用多条候选推测路径来减少分支误推测的发生；再次，在运行时采用线程性能预测和线程分配机制，提出了一种基于SMT的线程性能预测与循环性能调节方法，利用每次循环调用的性能预测结果指导多层嵌套循环的动态选择和推测并行。本项目的研究结果揭示了程序sp-cqip插入点位置影响加速比的内在规律，证实机器学习方法能够全面提高TLS的性能，采用Olden基准程序评测，表明了比不用机器学习方法加速比平均提高20%以上。其次，本项目提出并形成了一种新的TLS编译优化方法，该方法由SpCFG表示、特征数据获取和样本学习、TLS线程生成和映射组成，为多核处理器及编译器研发提供了参考。本项目的预期目标均已经达到，已发表论文 23篇（EI检索23篇，SCI检索5篇），申请国家发明专利4项，培养博士研究生4名﹑硕士研究生10名以上。