基于人工神经网络的线程数据加速划分∗

盛红雷 贾 崟

（1.南京南瑞集团公司信息通信技术分公司 南京 210000）（2.国网冀北电力有限公司 北京 100054）

1 引言

线程级推测（Thread-Level Speculation，TLS）是多核上一种加速串行程序的线程级自动并行化技术［1］。按照摩尔定律，半导体处理器进入了多核时代［2］。线程级并行（Thread-Level Parallelism，TLP）逐渐成为很好的一个选择，尤其适合于片上多处理器（Chip Multiprocessor，CMP）［3］。为了提升程序在CMP上运行的效率，已有的串行程序需要并行化从而能够在多核上执行，从而获得程序加速比性能的提升。推测多线程（Speculative Multithreading，SpMT）作为串行程序并行化的一种重要技术［4］，允许串行程序划分后生成的多个线程并行地、激进地执行，从而获得程序性能的提高。比较经典的 SpMT 代表有［5］Multiscalar，Hydra，Mitosis，POSH，DOMORE，DOE，SEED。机器学习方法已经被引入到推测多线程技术。文献［6］开发了自动基于编译器的方法来实现利用机器学习匹配一个并行化的程序到多核处理器，该方法利用机器学习实现了并行程序的最佳线程数目和调度策略。文献［7］给出一个自适应的基于OpenMP的机制，该机制利用机器学习方法给给定的循环产生合理数目的多线程版本，且选择一个运行时在多核结构上最合适的版本来执行。文献［8］利用机器学习方法来分配并行任务，具体方法是基于相似程序分配策略的先验知识在决定最佳任务分配方案之前利用静态程序特征来分类程序。机器学习在线程级推测中的应用主要包含：线程到多核的匹配、线程的调度、多线程的优化、线程划分的决策等，文献［9］利用K-Nearest-Neighbour（KNN）算法，根据相邻的相似度较高的训练程序的划分方案综合决定待划分程序的划分方案。

本文提出一种基于人工神经网络的线程划分预测模型。基于训练程序的特征信息和最优划分方案，预测模型按照指定的精度进行训练。训练好的模型根据测试程序的特征信息预测出划分方案。本文中ANN模型和Prophet自动划分编译器相互配合，使用Olden基准程序集进行离线学习和指导划分。

2 线程数据加速划分模型

2.1 基本思想

对于TLS自动划分过程，本文使用Prophet编译器完成。ANN预测模型通过写读（write and read）预测结果文件和Prophet关联［10］，从样本集中学习线程划分的知识，并根据待测过程的特征信息，预测该过程的划分方案，并将该方案反馈给Prophet的划分遍，从而实现Prophet对该过程有较优的划分。图1给出了ANN预测模型和Prophet关系图。箭头1代表ANN预测模型产生的划分方案反馈给Prophet过程，箭头2代表Prophet划分过程为ANN预测模型提供划分方案生成依据。

图1 ANN预测模型和Prophet关系图

2.2 整体框架

基于ANN的线程划分预测模型如图2所示。模型主要分为两个部分：训练阶段（上面虚框），测试阶段（下面虚框）。样本集是ANN预测模型学习划分知识的来源，其中的样本由两部分组成，即过程特征X和划分方案H。在训练阶段，首先从样本集中每一个样本分离出各自的过程特征x和划分方案h，并作为ANN模型的输入和输出来训练网络，直至网络达到指定的精度。在测试阶段，首先提取测试过程的特征信息，组成特征向量作为ANN模型的输入，并执行训练好的模型得出测试过程的划分方案。

图2 线程划分预测框架

2.3 特征提取

特征提取是由Prophet的剖析器Pro_ler来实现。Pro_ler首先分析基准程序的输入特征，并依据输入特征构造输入训练集。Pro_ler通过多次预执行程序捕获程序的剖析信息，工作流程如图3所示，当执行一个程序指令时，首先对指令类型做出判断，当指令是循环指令时，记录循环的迭代次数D，动态指令数M，循环个数C。当指令为非循环指令时，记录基本块个数N和动态指令数M，和分支个数P。最终，ANN模型选取程序关键路径上的5个特征：基本块个数N，动态指令数M ，分支指令个数P，循环个数C，函数调用次数E，并由这5个特征组成特征向量 X=＜N，M，P，C，E＞。

图3 程序剖析器Profiler

2.4 划分方案

在Prophet线程划分遍中，对程序加速比影响比较大有五个阈值，分别是依赖数，线程粒度下限，线程粒度上限，激发距离下限，激发距离上限，它们的名称（包括缩写）和释义如表1所示。

表1 线程划分最具影响的五个阈值

在图2中，得出上面五个因素变化能够影响加速比。五个因素变化时，Prophet划分遍在划分过程时产生不同的限制条件，程序的加速比因此产生波动。对程序中每个过程进行线程划分时，通过五个因素值的改变，导致程序中每个过程的加速比提高，从而整个程序的加速比也得到提高。我们把影响程序划分结果的最重要五个阈值作为线程划分方案 H 的组成部分，即 H=＜Dt，TsL，TsU，SdL，SdU＞。

3 实验准备

3.1 实验配置

本文基于MatlabR2015b神经网络工具箱和SUIF/MACHSUIF［11］开发的 Prophet编译器［12］和模拟器，并选用了Olden基准程序集［13］作为预测模型的输入和验证程序集。Prophet模拟器是基于Tomasulo算法［14］模拟了8核超标量四流水的基于MIPS的R3000处理器，是一个执行驱动的模拟器，每个处理单元有独立的程序计数器、取指令单元、解码单元、执行单元。各个PE能够以顺序方式在一个时钟周期发射4条指令，而且有各自的多版本L1缓存（2时钟周期访问延迟）。多版本L1缓存被用于缓存各个执行单元的推测结果，并且进行缓存之间的通信。8个处理单元通过一个监听总线共享一个写回L2缓存。表2给出了Prophet参数配置列表。Prophet编译器实现预测方案指导划分的过程，而模拟器验证指导划分后获得的加速比。ANN线程预测模型的实验平台如下，软件平台：Windows7+Matlab2015a；硬件平台：处理器Intel（R） Core（TM）i5-2400 CPU@3.10GHz，64bit；8.00GB RAM。表3给出了ANN预测模型的参数配置。

表2 Prophet参数配置和取值

表3 ANN预测模型的参数配置和取值

3.2 评价指标

为了对ANN线程划分预测模型进行有效评价，从两个方面进行评价，分别是预测精度和性能增长率。其中，预测精度如图4给出了预测精度的计算图。

图4 预测精度计算图

预测模型的一个输出值对应于五维空间中的一个点，提取三个点：预测输出点，实际点和坐标轴原点，组成一个平面，横竖坐标轴分别为x轴和y轴。黑色五角星2代表ANN模型预测的结果，黑色圆圈1代表原有结果，线b代表预测结果到原点线段，线c代表原有结果到原点线段，虚线a代表预测输出和原有结果之间线段，我们用线b和线c之间夹角α(0～π)的余弦值cosα(0～1)来代表预测精度。当五角星和圆圈越近（即预测值和实际值越接近），夹角越小，余弦值越大，精度越高；反之，五角星和圆圈越远（即预测值和实际值越远），夹角越大，余弦值越小，精度越小。根据余弦定理：

其中，‖‖a，‖‖b和‖‖c分别代表线段a，b，c的长度。假设点1的坐标为 (Dt，TsL，TsU，SdL，SdU)，点 2 的坐标为 (Dt+δ1，TsL+δ2，TsU+δ3，SdL+δ4，SdU+δ5)，其中，δ1，δ2，δ3，δ4，δ5分别表示预测的五维输出和原有目标输出之间对应的差值。则

利用式（4），我们对基于ANN线程划分预测模型的预测精度进行定量评估。为了定量分析，定义性能增长率为

其中，C表示预测结果指导程序划分后获得的加速比；O表示原有基于启发式规则线程划分［15］取得的加速比；R代表性能增长率。

4 实验分析

4.1 加载样本集

根据特征提取和划分方案，提取的特征向量为X=＜N，M，P，C，E＞ ，线 程 划 分 方 案 为H=＜Dt，TsL，TsU，SdL，SdU＞ 。我们用 (X，H)来表示样本，从而得出样本是一个10维向量，即＜N，M，P，C，E，Dt，TsL，TsU，SdL，SdU＞ 。 提 供样本集的是database.text文件，共存储10321个样本。利用Matlab的导入功能将database.txt中的过程名去掉（方便预测模型训练），只导入特征向量X和对应的划分方案H，形成database.m文件。

4.2 建立模型

为了建立ANN预测模型，首先确定网络的各层结构，并初始化网络。根据样本特征向量X的维度确定神经网络的输入层含有5个神经元，而划分方案H的维度确定网络输出层含有5个神经元。利用Matlab中的new_（）函数，选择traingdm（）的训练方法以及learngdm（）的学习方法，针对输入的样本＜X，H＞进行训练，利用mse（）均方差来评价误差。利用train（）函数进行训练，并利用sim（）函数进行结果仿真。

4.3 实验结果分析

通过采用Matlab神经网络工具箱中的与BP网络有关的函数对样本数据进行训练，使得预测输出尽可能接近目标输出，在训练的过程中选择一部分作为训练样本，一部分作为测试样本。其中，目标输出结果如图4所示，经过神经网络预测模型预测出的11个过程的结果如表5所示。

表4 目标输出结果

通过式（4），计算出基于ANN的线程划分预测模型对这11个过程的预测精度值，分别是0.8417，0.9411，0.6383，0.8354，0.7402，0.941，0.3414，0.2407，0.9193，0.4345，0.8401。平均的预测精度为（0.8417+0.9411+0.6383+0.8354+0.7402+0.941+0.3414+0.2407+0.9193+0.4345+0.8401）/11=0.701245。图5显示出了11个过程的预测精度值和平均值。

图5 11个过程的预测精度值

基于ANN的线程划分预测模型为测试过程产生划分方案以后，应用划分方案指导Prophet对该过程进行线程划分成为要解决的问题。表4可以看出，预测输出是一个五维向量H=＜Dt，TsL，TsU，SdL，SdU＞ 的值。利用向量中的5个值替换划分中的具体阈值，从而达到指导划分的目的。为了反映性能提升的程度，用式（5）计算各个基准程序的性能增长率，如图6所示。

图6 性能增长率

由图6可以看出，与传统的方法相比，基于ANN线程划分预测模型预测结果指导划分后使Olden基准测试集的增长率变化范围由1.00%到11.8%。实验数据显示，本文的预测模型能产生出更优的划分方案，使得指导后的过程划分获得更好的加速比提升。

5 结语

本文提出，验证和应用了一种基于人工神经网络的线程划分预测模型。该文主要创新在于：1）利用人工神经网络非线性学习能力从样本集中学习线程划分知识，并预测未知程序的划分方案；2）用向量表达程序特征和线程划分方案，利于预测模型的学习；3）本文的预测模型和Prophet线程划分平台通过共享文件方式传递预测结果，从而在不影响Prophet正常运行的情况下，实现了预测结果指导Prophet线程划分过程的目的。实验证明了该文提出的预测模型能够学习样本集划分知识，为测试程序生成划分方案，实现了对该程序的自动和有效划分。