基于SIMD扩展部件的嵌套循环向量并行的实现方法及其装置

摘要

本发明涉及一种基于SIMD扩展部件的嵌套循环向量并行的实现方法及其装置，该方法包含：通过设定破环测试参数对待并行化程序区域进行依赖环破除测试，将SIMD扩展部件对应于待并行化程序区域中循环的局部并行，通过循环分段发掘待并行化程序区域中单层循环局部并行性；将循环分段依次应用在循环嵌套的每一层循环，对待并行化程序区域中整个循环嵌套进行SIMD并行化处理。本发明通过依赖环破除测试，减少不必要的循环分段造成的性能损耗，充分发掘单层循环的局部并行性，循环分段依次应用于循环嵌套的每一层循环实现整个循环嵌套的SIMD并行化，充分发挥SIMD短向量扩展部件的并行性，实现高性能计算线程间负载均衡、性能优化，对高性能计算具有重要意义。

说明书

技术领域

本发明属于高性能计算并行化处理技术领域，特别涉及一种基于SIMD扩展部件的嵌套循环向量并行的实现方法及其装置。

背景技术

人类对计算能力无休止的需求，使得并行计算技术越来越受到人们的重视，总体上并行硬件技术的发展要远远快于并行软件技术的发展。SIMD扩展部件为提升程序性能提供了硬件支持，为充分发挥SIMD扩展的性能，需要充分发掘程序中的并行性，开发具有良好可扩展性的向量化程序。

虽然SIMD扩展部件和向量机都属于单指令多数据流并行模式，但两者的体系结构在设计原则和硬件实现上有较大差异。具体表现为：1、SIMD扩展部件受限于功能部件集成数量和数据总线的宽度，其向量长度远远小于向量机，它能同时处理的数据个数是有限的。而向量机只要操作允许，向量长度可以不受限制。2、SIMD扩展部件的所有操作大都是在向量寄存器上执行的，通过向量装载指令将内存中的向量数据存放到向量寄存器，然后执行向量操作，再将向量结果写到内存中。而向量机可以直接在向量数据上进行运算。3、SIMD部件与标量执行部件共用一个指令缓存和指令队列，SIMD指令之间是串行的。而向量机具有独立的指令部件，可向多个执行单元发射不同的向量指令。以上差异的第一条使得向量机一般采用向量全长的数据加工方式，一次向量操作将要从头到尾执行全部数据的运算，称之为全局并行；而SIMD扩展部件一般采用分段的数据加工方式，每次向量操作只执行一小段数据的运算，称之为局部并行。图1描述循环迭代执行时全局并行与局部并行时的区别。

Kennedy等人最初提出了针对多层循环的向量代码生成方法codegen，实际上是面向向量机的全局并行性的一种向量化方法。这种方法并不能直接应用于当前主流的SIMD短向量扩展部件。因此，当前优化编译器中实际采用的向量化方法都在传统方法的基础上考虑了SIMD的局部并行特性，同时为了简化算法，一般仅实现了最内层循环的向量化(或次外层循环的向量化)。上述的方法分别实现了“嵌套循环的全局并行”和“单层循环的局部并行”的发掘。但目前并没有一个好的方法来发掘高性能计算并行处理中的“嵌套循环局部并行性”。

发明内容

针对现有技术中的不足，本发明提供一种基于SIMD扩展部件的嵌套循环向量并行的实现方法及其装置，针对SIMD扩展部件特征，通过分段技术对嵌套循环局部并行性发掘，实现整个循环嵌套的SIMD并行化，有效保证高性能计算线程间负载均衡，实现性能优化。

按照本发明所提供的设计方案，一种基于SIMD扩展部件的嵌套循环向量并行的实现方法，包含：通过设定破环测试参数对待并行化程序区域进行依赖环破除测试，将SIMD扩展部件对应于待并行化程序区域中循环的局部并行，通过循环分段发掘待并行化程序区域中单层循环局部并行性；将循环分段依次应用在循环嵌套的每一层循环，对待并行化程序区域中整个循环嵌套进行SIMD并行化处理。

上述的，通过设定破环测试参数对待并行化程序区域进行依赖环破除测试中，破坏测试参数包含循环层及分段长度，设定分段长度VF，通过分段长度VF对待并行化程序区域中存在的依赖环进行破环标记。

上述的，将循环分段依次应用在循环嵌套的每一层循环，对待并行化程序区域中整个循环嵌套进行SIMD并行化处理中：通过循环分段从外层到内层依次应用于整个循环嵌套，包含如下内容：

a)通过依赖环破除测试，若当前循环层L_cur存在可破除依赖环，则对当前循环层L_cur进行循环分段，变换为L_cur1和L_cur2两层循环；

b)对分段后的内层循环L_cur2进行单层循环SIMD并行化，将当前循环层L_cur设置为下一层循环，转向步骤a进行循环迭代，直到下一层循环为空。

上述的，实现方法具体过程如下：

步骤1、对待并行化程序区域进行依赖分析，获取所有语句之间的依赖图；

步骤2、在依赖图中求解得到强连通区域集合，强连通区域集合包含多个强连通区域；

步骤3、将每个强连通区域看作单个节点，获得依赖凝聚图；

步骤4、对依赖凝聚图中的节点进行拓扑排序，得到节点集合序列；

步骤5、通过寻找语句集合获取依赖环集合，并判定依赖环集合是否为空集，若为空集则跳转至步骤7执行，否则，进入步骤6；

步骤6、对循环层进行循环分段，并标记循环分段后的可向量化语句，更新依赖图、依赖凝聚图及依赖凝聚图的拓扑排序，得到新的节点集合序列；

步骤7、遍历节点集合序列中的每个节点，判断节点集合序列是否为依赖环，若是，则删除待分段循环层上的依赖，并递归实现循环分段的嵌套循环向量化；否则，针对相应节点生成向量语句。

更进一步，步骤2中，在依赖图中求解得到强连通区域集合：通过Tarjan算法求解最大强连通区域集合{SCC₁,SCC₂,…,SCC_m}。

优选地，步骤3中依赖凝聚图：通过凝聚每个强连通区域为单节点，获取依赖凝聚图，其中，依赖凝聚图为有向无环图。

优选地，步骤4中，将依赖凝聚图中的m个节点进行拓扑排序，得到的节点集合序列表示为：

πs{π₁，π₂，…，π_m}。

优选地，步骤5中，通过寻找语句集合获取依赖环集合，寻找满足如下条件的语句：1)语句属于设定的并行循环最小嵌套层；2)且语句存在于强连通区域中，得到语句集合，记为SK{SK₁,SK₂,…,SK_e}，将相关的依赖环集合记为πk{πk₁，πk₂，…，πk_f}。

一种基于SIMD扩展部件的嵌套循环向量并行的实现装置，包含依赖环破除测试模块及循环分段模块，其中，

依赖环破除测试模块，用于通过设定破环测试参数对待并行化程序区域进行依赖环破除测试，并将测试结果反馈至循环分段模块；

循环分段模块，用于将SIMD扩展部件对应于待并行化程序区域中循环的局部并行，并根据依赖环破除测试模块反馈通过循环分段发掘待并行化程序区域中单层循环局部并行性；将循环分段依次应用在循环嵌套的每一层循环，对待并行化程序区域中整个循环嵌套进行SIMD并行化处理。

一种基于SIMD扩展部件的嵌套循环向量并行的实现装置，包含：依赖分析模块、依赖环获取模块、节点凝聚模块、拓扑排序模块、依赖环测试模块、循环分段模块及节点遍历模块，其中，

依赖分析模块，用于对待并行化程序区域进行依赖分析，获取所有语句之间的依赖图；

依赖环获取模块，用于在依赖图中求解得到强连通区域集合，强连通区域集合包含多个强连通区域；

节点凝聚模块，用于将每个强连通区域看作单个节点，获得依赖凝聚图；

拓扑排序模块，用于对依赖凝聚图中的节点进行拓扑排序，得到节点集合序列；

依赖环测试模块，用于通过寻找语句集合获取依赖环集合，并判定依赖环集合是否为空集，若为空集反馈至节点遍历模块，否则，反馈至循环分段模块；

循环分段模块，用于对循环层进行循环分段，并标记循环分段后的可向量化语句，更新依赖图、依赖凝聚图及依赖凝聚图的拓扑排序，得到新的节点集合序列；

节点遍历模块，用于遍历节点集合序列中的每个节点，判断节点集合序列是否为依赖环，若是，则删除待分段循环层上的依赖，并递归实现循环分段的嵌套循环向量化；否则，针对相应节点生成向量语句。

本发明的有益效果：

本发明将SIMD短向量扩展部件与向量机区分开来，将SIMD短向量扩展部件对应于循环的局部并行；通过采用循环分段依次应用于循环嵌套的每一层循环实现整个循环嵌套的SIMD并行化，并通过依赖环破除测试，减少不必要的循环分段造成的性能损耗，充分发掘单层循环的局部并行性，实现整个循环嵌套的SIMD并行化，本发明可用于实现程序自动SIMD并行化，产生高效且健壮的并行代码，对充分发挥计算机系统的硬件优势，提高计算机系统的性能具有重要意义。

附图说明：

图1为循环迭代全局并行与局部并行示意图；

图2为本发明的方法流程示意图；

图3为实施例实现过程示意图；

图4为实施例中无环循环和有环循环对比示意图；

图5为实施例中循环分段消除依赖环示意图；

图6为本发明的装置示意图之一；

图7为本发明的装置示意图之二。

具体实施方式：

下面结合附图和技术方案对本发明作进一步清楚、完整的说明，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

实施例，参见图2所示，一种基于SIMD扩展部件的嵌套循环向量并行的实现方法，包含：通过设定破环测试参数对待并行化程序区域进行依赖环破除测试，将SIMD扩展部件对应于待并行化程序区域中循环的局部并行，通过循环分段发掘待并行化程序区域中单层循环局部并行性；将循环分段依次应用在循环嵌套的每一层循环，对待并行化程序区域中整个循环嵌套进行SIMD并行化处理。

本实施例中，面向循环嵌套，针对SIMD短向量扩展部件，充分发掘多层循环同时并行化，大大提升SIMD短向量扩展部件的执行效率。

为了减少不必要的循环分段带来的性能损耗，在真正实施循环分段之前首先进行依赖环破除测试，只有当循环分段对SIMD并行是“有利”的，循环分段打破某个或某些依赖环时，进行循环分段，另一个实施例中，通过设定破环测试参数对待并行化程序区域进行依赖环破除测试中，破坏测试参数包含循环层及分段长度，设定分段长度VF，通过分段长度VF对待并行化程序区域中存在的依赖环进行破环标记。

又一实施例中，将循环分段依次应用在循环嵌套的每一层循环，对待并行化程序区域中整个循环嵌套进行SIMD并行化处理中：通过循环分段从外层到内层依次应用于整个循环嵌套，包含如下内容：

a)通过依赖环破除测试，若当前循环层L_cur存在可破除依赖环，则对当前循环层L_cur进行循环分段，变换为L_cur1和L_cur2两层循环；

b)对分段后的内层循环L_cur2进行单层循环SIMD并行化，将当前循环层L_cur设置为下一层循环，转向步骤a进行循环迭代，直到下一层循环为空。

将循环分段技术从外层到内层依次应用于循环嵌套，实现循环嵌套中尽可能多的语句的SIMD并行化。

再一实施例中，参见图3所示，基于SIMD扩展部件的嵌套循环向量并行的实现方法，具体步骤如下：

步骤1、对待并行化程序区域进行依赖分析，获取所有语句之间的依赖图；

步骤2、在依赖图中求解得到强连通区域集合，强连通区域集合包含多个强连通区域；

步骤3、将每个强连通区域看作单个节点，获得依赖凝聚图；

步骤4、对依赖凝聚图中的节点进行拓扑排序，得到节点集合序列；

步骤5、通过寻找语句集合获取依赖环集合，并判定依赖环集合是否为空集，若为空集则跳转至步骤7执行，否则，进入步骤6；

步骤6、对循环层进行循环分段，并标记循环分段后的可向量化语句，更新依赖图、依赖凝聚图及依赖凝聚图的拓扑排序，得到新的节点集合序列；

步骤7、遍历节点集合序列中的每个节点，判断节点集合序列是否为依赖环，若是，则删除待分段循环层上的依赖，并递归实现循环分段的嵌套循环向量化；否则，针对相应节点生成向量语句。

更进一步，另一个实施例中，在依赖图中求解得到强连通区域集合，通过Tarjan算法求解最大强连通区域集合{SCC₁,SCC₂,…,SCC_m}。

另一实施例中，依赖凝聚图：通过凝聚每个强连通区域为单节点，获取依赖凝聚图，其中，依赖凝聚图为有向无环图。

又一实施例中，将依赖凝聚图中的m个节点进行拓扑排序，得到的节点集合序列表示为：πs{π₁，π₂，…，π_m}。

在其他实施例中，通过寻找语句集合获取依赖环集合，寻找满足如下条件的语句：1)语句属于设定的并行循环最小嵌套层；2)且语句存在于强连通区域中，得到语句集合，记为SK{SK₁,SK₂,…,SK_e}，将相关的依赖环集合记为πk{πk₁，πk₂，…，πk_f}。

依赖环破除测试：其目的是减少不必要的循环分段带来的性能损耗。破环测试相关的参数为：循环层和分段长度。为了便于产生向量化代码，分段长度定为VF。编译器中，依赖环是以强连通图的形式存在的，若强连通图是可拆分的，那么依赖环可破。破环测试算法伪代码可设计如下：

基于codegen的改进算法simdcodegen，即基于SIMD扩展部件的嵌套循环向量并行的实现算法，可设计为如下所示：

该算法可实现针对SIMD短向量部件的嵌套循环向量代码生成，在codegen的基础上增加了破环测试和循环分段，增强了算法对嵌套循环的SIMD并行发掘能力。

循环分段是对迭代的循环变换。循环分段将单层循环变换为两层嵌套循环，外层循环把原循环迭代空间划分为不同的段，每个段中执行原循环的多次迭代，与内层循环对应。循环分段总是合法的，段长可根据需要选取。如果原循环可并行化的，则分段后依然可并行化。将循环分段用于发掘SIMD并行性，实质上是通过循环分段技术来消除循环中的某些依赖，进而达到消除依赖环的目的。循环分段消除依赖环基于这样的事实：程序中的依赖环必然存在循环携带依赖，该依赖的依赖距离记为distance，那么如果循环迭代空间长度小于等于distance，那么该依赖实际上是不存在的。循环分段就是通过缩小段内迭代空间来消除依赖距离较大的循环携带依赖。针对SIMD短向量并行部件，每次可并行执行的迭代次数为VF(vector factor,向量因子)，考虑以VF为单位段长进行循环分段，那么段内所有依赖距离大于VF的依赖将被消除。

以图4(2)所示的循环来为例说明循环分段的作用。假定VF＝4，分段后的结果如图5(1)所示，方框内的代码为内层(段内)循环，索引下界为I，上界为I+3，此处MIN(I+3,100)用来保证分段后循环的计算范围不会超出源循环。对于内层循环，迭代次数小于等于4，语句S2到S1的距离为4的循环携带依赖可消除，因此依赖环可破除，最终可得到如图5(2)所示的向量化结果。

对应于上述的基于SIMD扩展部件的嵌套循环向量并行的实现方法的实施例，如图6所示，提供一种基于SIMD扩展部件的嵌套循环向量并行的实现装置，包含依赖环破除测试模块101及循环分段模块102，其中，

依赖环破除测试模块101，用于通过设定破环测试参数对待并行化程序区域进行依赖环破除测试，并将测试结果反馈至循环分段模块；

循环分段模块102，用于将SIMD扩展部件对应于待并行化程序区域中循环的局部并行，并根据依赖环破除测试模块反馈通过循环分段发掘待并行化程序区域中单层循环局部并行性；将循环分段依次应用在循环嵌套的每一层循环，对待并行化程序区域中整个循环嵌套进行SIMD并行化处理。

对应于上述的基于SIMD扩展部件的嵌套循环向量并行的实现方法的另一实施例，如图7所示，一种基于SIMD扩展部件的嵌套循环向量并行的实现装置，包含：依赖分析模块201、依赖环获取模块202、节点凝聚模块203、拓扑排序模块204、依赖环测试模块205、循环分段模块206及节点遍历模块207，其中，

依赖分析模块201，用于对待并行化程序区域进行依赖分析，获取所有语句之间的依赖图；

依赖环获取模块202，用于在依赖图中求解得到强连通区域集合，强连通区域集合包含多个强连通区域；

节点凝聚模块203，用于将每个强连通区域看作单个节点，获得依赖凝聚图；

拓扑排序模块204，用于对依赖凝聚图中的节点进行拓扑排序，得到节点集合序列；

依赖环测试模块205，用于通过寻找语句集合获取依赖环集合，并判定依赖环集合是否为空集，若为空集反馈至节点遍历模块，否则，反馈至循环分段模块；

循环分段模块206，用于对循环层进行循环分段，并标记循环分段后的可向量化语句，更新依赖图、依赖凝聚图及依赖凝聚图的拓扑排序，得到新的节点集合序列；

节点遍历模块207，用于遍历节点集合序列中的每个节点，判断节点集合序列是否为依赖环，若是，则删除待分段循环层上的依赖，并递归实现循环分段的嵌套循环向量化；否则，针对相应节点生成向量语句。

本发明的实施例中，采用循环分段技术来实现单层循环局部并行性的发掘。循环分段技术将单层循环变换为两层嵌套循环，外层循环把原循环迭代空间划分为不同的段，每个段中执行原循环的多次迭代，与内层循环对应，内层循环迭代空间的变化使得依赖发生改变。将循环分段用于发掘SIMD并行性，实质上是循环分段就是通过缩小段内迭代空间来消除依赖距离较大的循环携带依赖，进而达到消除依赖环的目的，而依赖环是阻碍SIMD并行化的主要因素。循环分段后，如果内层循环中存在可并行的语句，那么执行对应的SIMD语句替换和重排序。根据依赖图获得拓扑序列，使得SIMD语句的排序符合上述序列，同时还要调整循环头，使其适应于新生成的SIMD语句。为了减少不必要的循环分段带来的性能损耗，在真正实施循环分段之前首先要进行依赖环破除测试。只有当循环分段对于SIMD并行是“有利的”，即循环分段可以打破某个或某些依赖环时，才进行循环分段。破环测试相关的参数为：循环层和分段长度。为了便于产生SIMD代码，分段长度定为VF，编译器中，依赖环是以强连通图的形式存在的，若循环分段使得某些强连通图可拆分，那么就将依赖环标记为可破除，针对该层循环实施循环分段，减少不必要的循环分段造成的性能损耗，充分发掘单层循环的局部并行性，实现整个循环嵌套的SIMD并行化，充分发挥SIMD短向量扩展部件的并行性，实现高性能计算线程间负载均衡，执行效率高，实现性能优化，对高性能计算具有重要意义。

本领域内的技术人员应明白，本发明的实施例可提供为方法、系统、或计算机程序产品。因此，本发明可采用完全硬件实施例、完全软件实施例、或结合软硬件方面的实施例的形式。而且，本发明可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD-ROM、光学存储器等)上实施的计算机程序产品的形式。

本发明是参照根据本发明实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

这些计算机程序指令也可存储在能引导计算机或其他科编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

对所公开的实施例的上述说明，使本领域专业技术人员能够实现或使用本申请。对这些实施例的多种修改对本领域的专业技术人员来说将是显而易见的，本文中所定义的一般原理可以在不脱离本申请的精神或范围的情况下，在其它实施例中实现。因此，本申请将不会被限制于本文所示的这些实施例，而是要符合与本文所公开的原理和新颖特点相一致的最宽的范围。