一种面向循环优化和非规则代码段的粗粒度半自动并行化方法
发布时间：2019-07-28 20:00
【摘要】：多核架构已成为当今的主流,而大量传统的串行程序和遗留软件无法充分利用多核处理器的并行计算性能.人工改写这些遗留软件工作量繁重、成本高昂,自动实现程序并行化的技术成为学术和工业界研究的热点.该文提出了一种新颖的面向一般程序的for循环优化和非规则代码段的粗粒度半自动并行化方法.该方法通过程序动态分析,根据程序的控制流和数据依赖信息将源程序代码映射成可计算单元(CU)图,从中提取出可并行执行的非规则代码段.同时针对程序中for循环部分,提出了一种基于局部性分析的分块收益模型,有效地选择具有收益的循环代码实施循环分块优化;提出了一种基于cache均匀映射的最优分块因子大小选择算法UMC-TSS,以生成优化的分块代码,充分利用cache性能并实现分块的粗粒度并行.该文实现了一个基于LLVM编译架构的C/C++源码到Intel TBB并行源码转换的半自动化工具,它在AST上进行深度代码重构,只需少量的人工干预即可生成高效的并行代码.为了验证该文方法的有效性,从4组不同的基准测试集上选取18个具有代表性的测试程序在一台Intel Xeon多核服务器上进行了一系列实验,在循环级和任务级并行性能上分别获得平均10.95和4.45的加速比.和目前最先进的一种最优分块大小算法相比,UMC-TSS算法平均提升了4%的分块代码性能.实验结果还表明由源到源代码转换工具生成的Intel TBB并行代码具有良好的并行性和可扩展性.
【图文】：
ｏｖｅｒｃｎｔ＋＋；３３．ｅｎｄｉｆ３４．ｅｎｄｆｏｒ３５．ｉｆｔｅｍｐ＜ｔｕｐｌｅ．ｖａｌｔｈｅｎ／／记录最小ＵＭ值／／对应的分块大小３６．ｔｕｐｌｅ．ｖａｌ＝ｔｅｍｐ；３７．ｔｕｐｌｅＩ．＝Ｉ／ＣＬＳ×ＣＬＳ；／／空间局部性优化３８．ｔｕｐｌｅ．Ｋ＝Ｋ；３９．ｔｕｐｌｅ．Ｊ＝Ｊ；４０．ｅｎｄｉｆ４１．ｅｎｄｆｏｒ４２．ｐｏｉｎｔｅｒ＋＋；４３．ｅｎｄｗｈｉｌｅ４４．Ｏｕｔｐｕｔ（ｔｕｐｌｅＩ．，ｔｕｐｌｅ．Ｋ，ｔｕｐｌｅ．Ｊ）；图４粗粒度半自动并行化模型的工作流程ＰＬｕＴｏ不提供ＴＳＳ算法，每层循环默认采用３２作为分块因子．将ＵＭＣ－ＴＳＳ算法集成到本文实现的源到源并行代码转换工具中，在调用ＰＬｕＴｏ对ｆｏｒ循环进行分块优化时启动，将计算出的最优分块大小写到ｔｉｌｅ．ｓｉｚｅｓ文件中供ＰＬｕＴｏ生成相应的优化代码．需要注意的是，尽管该算法计算最优分块大小时所需的软硬件参数均可自动获得，但式（３）和算法１、２仅适用于包含类似矩阵乘法循环结构的科学计算ｋｅｒｎｅｌ，如ＢＬＡＳ３库中的Ｍａｔｍｕｌ、Ｄｓｙｒｋ、ＬＵ等以及Ｊａｃｏｂｉ迭代和Ｓｅｉｄｅｌ方程等．对于一般程序中的ｆｏｒ循环语句，，用户可以根据表１和表２所总结的数组数据在Ｌ１和Ｌ２ｃａｃｈｅ中的工作集大小对式（３）中左侧工作集和ＵＭＣ－ＴＳＳ算法中工作集的模拟映射代码进行修改．表中第１列和第１行分别表示数组的行和列下标．表１中工作集大小的计算前提假设是块内循环顺序为ｉ，ｊ，ｋ
点用来执行计算，边表示结点之间的依赖关系．ｆｌｏｗｇｒａｐｈ在逻辑拓扑上与Ｔａｓｋ图非常相似．源到源并行代码转换工具根据粗粒度任务的Ｔａｓｋ图进行相应的ｆｌｏｗｇｒａｐｈ代码重构和封装．以图１中ＣＵ图为例，经过合并转换后生成的Ｔａｓｋ图如图６所示．其中，Ｔａｓｋ０是一个虚拟任务，不进行任何计算，只负责传递消息给后继节点．Ｔａｓｋ图生成后，直接调用源到源代码转换工具生成ｆｌｏｗｇｒａｐｈ并行代码，其具体实现可参考文献［４６］．图６Ｔａｓｋ图示例粗粒度任务的ｆｌｏｗｇｒａｐｈ代码转换的过程主要分为３步．第１步：确定每个Ｔａｓｋ对应的代码段．对Ｔａｓｋ图中每个任务Ｔａｓｋｉ（包括Ｔａｓｋ０），遍历ＣｌａｎｇＡＳＴ．当ＡＳＴ结点的源代码行号存在于Ｔａｓｋｉ中时，ＩｄｅｎｔｉｆｙｉｎｇＣｏｄｅＳｅｃｔｉｏｎｓ模块将其作为字符串存储在任务对应的对象中．第２步：生成ｆｌｏｗｇｒａｐｈ结点的源代码．ＳｏｕｒｃｅＣｏｄｅＲｅｗｒｉｔｉｎｇ模块将根据３种不同的情况，分别生成ｆｌｏｗｇｒａｐｈ结点的源代码．（１）当前任务Ｔａｓｋｉ有一条或者零条入边，多条出边．如果它的后继结点都接受相同的数据（即依赖于同一变量），那么ＳｏｕｒｃｅＣｏｄｅＲｅｗｒｉｔｉｎｇ模块插入一个ＩｎｔｅｌＴＢＢ的ｂｒｏａｄｃａｓｔ＿ｎｏｄｅ结点，否则插入一个ＩｎｔｅｌＴＢＢ的ｓｐｌｉｔ＿ｎｏｄｅ结点．ｓｐｌｉｔ＿ｎｏｄｅ结点能够将不同类型的数据传递给对应的后继结点．如图６
【作者单位】： 西安交通大学电信学院计算机系;
【基金】：国家自然科学基金(91630206,91330117) 国家重点研发计划(2016YFB0201800) 陕西省社会发展科技攻关项目(2016SF-428)资助~~
【分类号】：TP332
本文编号：2520310
【图文】：
ｏｖｅｒｃｎｔ＋＋；３３．ｅｎｄｉｆ３４．ｅｎｄｆｏｒ３５．ｉｆｔｅｍｐ＜ｔｕｐｌｅ．ｖａｌｔｈｅｎ／／记录最小ＵＭ值／／对应的分块大小３６．ｔｕｐｌｅ．ｖａｌ＝ｔｅｍｐ；３７．ｔｕｐｌｅＩ．＝Ｉ／ＣＬＳ×ＣＬＳ；／／空间局部性优化３８．ｔｕｐｌｅ．Ｋ＝Ｋ；３９．ｔｕｐｌｅ．Ｊ＝Ｊ；４０．ｅｎｄｉｆ４１．ｅｎｄｆｏｒ４２．ｐｏｉｎｔｅｒ＋＋；４３．ｅｎｄｗｈｉｌｅ４４．Ｏｕｔｐｕｔ（ｔｕｐｌｅＩ．，ｔｕｐｌｅ．Ｋ，ｔｕｐｌｅ．Ｊ）；图４粗粒度半自动并行化模型的工作流程ＰＬｕＴｏ不提供ＴＳＳ算法，每层循环默认采用３２作为分块因子．将ＵＭＣ－ＴＳＳ算法集成到本文实现的源到源并行代码转换工具中，在调用ＰＬｕＴｏ对ｆｏｒ循环进行分块优化时启动，将计算出的最优分块大小写到ｔｉｌｅ．ｓｉｚｅｓ文件中供ＰＬｕＴｏ生成相应的优化代码．需要注意的是，尽管该算法计算最优分块大小时所需的软硬件参数均可自动获得，但式（３）和算法１、２仅适用于包含类似矩阵乘法循环结构的科学计算ｋｅｒｎｅｌ，如ＢＬＡＳ３库中的Ｍａｔｍｕｌ、Ｄｓｙｒｋ、ＬＵ等以及Ｊａｃｏｂｉ迭代和Ｓｅｉｄｅｌ方程等．对于一般程序中的ｆｏｒ循环语句，，用户可以根据表１和表２所总结的数组数据在Ｌ１和Ｌ２ｃａｃｈｅ中的工作集大小对式（３）中左侧工作集和ＵＭＣ－ＴＳＳ算法中工作集的模拟映射代码进行修改．表中第１列和第１行分别表示数组的行和列下标．表１中工作集大小的计算前提假设是块内循环顺序为ｉ，ｊ，ｋ
点用来执行计算，边表示结点之间的依赖关系．ｆｌｏｗｇｒａｐｈ在逻辑拓扑上与Ｔａｓｋ图非常相似．源到源并行代码转换工具根据粗粒度任务的Ｔａｓｋ图进行相应的ｆｌｏｗｇｒａｐｈ代码重构和封装．以图１中ＣＵ图为例，经过合并转换后生成的Ｔａｓｋ图如图６所示．其中，Ｔａｓｋ０是一个虚拟任务，不进行任何计算，只负责传递消息给后继节点．Ｔａｓｋ图生成后，直接调用源到源代码转换工具生成ｆｌｏｗｇｒａｐｈ并行代码，其具体实现可参考文献［４６］．图６Ｔａｓｋ图示例粗粒度任务的ｆｌｏｗｇｒａｐｈ代码转换的过程主要分为３步．第１步：确定每个Ｔａｓｋ对应的代码段．对Ｔａｓｋ图中每个任务Ｔａｓｋｉ（包括Ｔａｓｋ０），遍历ＣｌａｎｇＡＳＴ．当ＡＳＴ结点的源代码行号存在于Ｔａｓｋｉ中时，ＩｄｅｎｔｉｆｙｉｎｇＣｏｄｅＳｅｃｔｉｏｎｓ模块将其作为字符串存储在任务对应的对象中．第２步：生成ｆｌｏｗｇｒａｐｈ结点的源代码．ＳｏｕｒｃｅＣｏｄｅＲｅｗｒｉｔｉｎｇ模块将根据３种不同的情况，分别生成ｆｌｏｗｇｒａｐｈ结点的源代码．（１）当前任务Ｔａｓｋｉ有一条或者零条入边，多条出边．如果它的后继结点都接受相同的数据（即依赖于同一变量），那么ＳｏｕｒｃｅＣｏｄｅＲｅｗｒｉｔｉｎｇ模块插入一个ＩｎｔｅｌＴＢＢ的ｂｒｏａｄｃａｓｔ＿ｎｏｄｅ结点，否则插入一个ＩｎｔｅｌＴＢＢ的ｓｐｌｉｔ＿ｎｏｄｅ结点．ｓｐｌｉｔ＿ｎｏｄｅ结点能够将不同类型的数据传递给对应的后继结点．如图６
【作者单位】： 西安交通大学电信学院计算机系;
【基金】：国家自然科学基金(91630206,91330117) 国家重点研发计划(2016YFB0201800) 陕西省社会发展科技攻关项目(2016SF-428)资助~~
【分类号】：TP332
【相似文献】
相关期刊论文 前1条
1 赵捷;赵荣彩;韩林;许瑾晨;;循环携带反依赖的MPI自动并行化研究[J];计算机科学;2012年06期
相关重要报纸文章 前1条
1 陈文光 郑纬民;高性能计算的三大研究领域[N];计算机世界;2006年
相关博士学位论文 前1条
1 于海荣;多核环境下针对不规则应用程序的非投机并行策略[D];华中科技大学;2016年
相关硕士学位论文 前2条
1 蔡达;基于OpenACC的自动并行化技术研究[D];中国矿业大学;2016年
2 沈勤华;可扩展的自动并行化编译系统Agassiz[D];复旦大学;2008年
本文编号：2520310
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/2520310.html
