分段约束的超字并行向量发掘路径优化算法

doi:10.11772/j.issn.1001-9081.2015.04.0950

计算机应用 ›› 2015, Vol. 35 ›› Issue (4): 950-955.DOI: 10.11772/j.issn.1001-9081.2015.04.0950

分段约束的超字并行向量发掘路径优化算法

徐金龙, 赵荣彩, 韩林

数学工程与先进计算国家重点实验室(信息工程大学), 郑州 450001

收稿日期:2014-10-28 修回日期:2015-01-13 出版日期:2015-04-10 发布日期:2015-04-08
通讯作者: 徐金龙
作者简介:徐金龙(1985-),男,山东诸城人,博士研究生,CCF会员,主要研究方向:体系结构、并行编译; 赵荣彩(1957-),男,河南洛阳人,教授,博士生导师,博士,CCF高级会员,主要研究方向:体系结构、先进编译、操作系统; 韩林(1978-),男,山东临沂人,副教授,博士,主要研究方向:并行编译、并行识别。
基金资助:
国家科技重大专项(2009zx10036-001-001);国家863计划项目(2009AA01220)。

Vector exploring path optimization algorithm of superword level parallelism with subsection constraints

XU Jinlong, ZHAO Rongcai, HAN Lin

State Key Laboratory of Mathematical Engineering and Advanced Computing (Information Engineering University), Zhengzhou Henan 450001, China

Received:2014-10-28 Revised:2015-01-13 Online:2015-04-10 Published:2015-04-08

摘要/Abstract

摘要：

超字并行(SLP)是一种针对基本块的向量并行发掘方法,结合循环展开可以发掘更多的并行性,但同时也会产生过多的发掘路径。针对上述问题,提出了一种分段约束的SLP发掘路径优化算法;采用分段的冗余删除方法,来保证冗余删除后段的同构性。采用段间的SLP发掘,来约束发掘路径;最后进行pack调整来处理访存重叠的情况。实验结果表明,该方法有效增强了SLP向量化功能,对于测试程序,向量化的平均加速比接近2。

关键词: 向量化, 超字并行, 循环展开, 同构, 冗余删除

Abstract:

Superword Level Parallelism (SLP) is a vector parallelism exploration approach for basic block. With loop unrolling, more parallel possibility can be explored. Simultaneously too much exploring paths are brought in. In order to solve the above problem, an optimized SLP method with subsection constraints was proposed. Redundant elimination on segmentation was used to obtain homogeneous segments. Inter-section exploring method based on SLP was used to restrain exploring paths and reduce the complexity of the algorithm. And finally pack adjustment was used to deal with the situation of overlap on memory access. The experimental results show that the vectorization capability of SLP is enhanced; for the test serial program, the average speedup of vectorized version is close to 2.

Key words: vectorization, Superword Level Parallelism (SLP), loop unrolling, isomorphism, redundant elimination

中图分类号:

TP314

徐金龙, 赵荣彩, 韩林. 分段约束的超字并行向量发掘路径优化算法[J]. 计算机应用, 2015, 35(4): 950-955.

XU Jinlong, ZHAO Rongcai, HAN Lin. Vector exploring path optimization algorithm of superword level parallelism with subsection constraints[J]. Journal of Computer Applications, 2015, 35(4): 950-955.

参考文献

[1] Intel Corporation. Intel 64 and IA-32 architectures software developer's manual[EB/OL]. [2013-10-10].http://www.intel.com/Assets/PDF/manual/252046.pdf.
[2] Intel Corportation. Legal disclaimer & optimization notice[EB/OL]. [2013-10-10].https://gcc.gnu.org/wiki/cauldron2014?action=AttachFile&do=get&target=Cauldron14_AVX-512_Vector_ISA_Kirill_Yukhin_20140711.pdf.
[3] STEWART J. An investigation of SIMD instruction sets [D]. Melbourne: University of Ballarat, 2005.
[4] ALLEN R, KENNEDY K. Optimizing compilers for modern architectures: a dependence-based approach[M]. San Francisco: Morgan Kaufmann, 2002.
[5] LARSEN S, AMARASINGHE S. Exploiting superword level parallelism with multimedia instruction sets[C]// PLDI 2000: Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation. New York: ACM Press, 2000:145-156.
[6] KIM T, HOSKOTE Y. Automatic generation of custom SIMD instructions for superword level parallelism[C]// Proceedings of the 2014 Design, Automation and Test in Europe Conference and Exhibition. Piscataway: IEEE Press, 2014:1-6.
[7] LIU P, ZHAO R, GAO W, et al. A new algorithm to exploit superword level parallelism[C]// Proceedings of the 2013 IEEE 11th International Conference on Dependable, Autonomic and Secure Computing. Piscataway: IEEE Press,2013: 521-527.
[8] ZHAO B, ZHAO R, LI Y, et al. SLP exploitation method for type conversion statements[J]. Computer Science,2014, 41(11): 16-21.(赵博, 赵荣彩, 李雁冰, 等. 类型转换语句的 SLP 发掘方法[J]. 计算机科学, 2014, 41(11): 16-21.)
[9] WEI S. Reaserch of SIMD vectorization algorithm and optimization[D]. Zhengzhou: Information Engineering University, 2012.(魏帅. 面向 SIMD 的向量化算法及重组技术研究[D]. 郑州:信息工程大学, 2012.)
[10] PRIETO M, PINUEL L, CATTHOOR F, et al. Improving superword level parallelism support in modern compilers[C]// CODES+ISSS 2005: Proceedings of the Third IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. Piscataway: IEEE Press, 2005: 303-308.
[11] KUDRIAVTSEV A, KOGGE P. Generation of permutations for SIMD processors[C]// LCTES 2005: Proceedings of the 2005 ACM SIGPLAN/SIGBED Conference on Languages, Compilers, and Tools for Embedded Systems. New York: ACM Press, 2005:147-156.
[12] LIU J, ZHANG Y, JANG O, et al. A compiler framework for extracting superword level parallelism[C]// PLDI 2012: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation. New York: ACM Press, 2012: 347-358.

[1]	刘专, 韩瑞琛, 张延松, 陈跃国, 张宇. 面向多核CPU和GPU平台的数据库星形连接优化[J]. 计算机应用, 2021, 41(3): 611-617.
[2]	徐周波, 李珍, 刘华东, 李萍. 基于邻居信息聚合的子图同构匹配算法[J]. 计算机应用, 2021, 41(1): 43-47.
[3]	宋祥帅, 杨伏长, 谢江, 张武. Graphlet Degree Vector方法的优化与并行[J]. 计算机应用, 2020, 40(2): 398-403.
[4]	税留成, 刘卫忠, 冯卓明. 基于生成式对抗网络的图像自动标注[J]. 计算机应用, 2019, 39(7): 2129-2133.
[5]	王吉祥, 过弋, 戚天梅, 王志宏, 李真, 汤敏伟. 嵌入互联网舆情强度的人民币汇率预测[J]. 计算机应用, 2019, 39(11): 3403-3408.
[6]	施炜杰, 董一鸿, 王雄, 潘剑飞. 基于索引的子图查询技术研究进展[J]. 计算机应用, 2019, 39(1): 39-45.
[7]	杨伏长, 朱嘉富, 孙佳敏, 谢江. 生物复杂网络motif发现的并行算法[J]. 计算机应用, 2019, 39(1): 72-77.
[8]	李颖颖, 高伟, 高雨辰, 翟胜伟, 李朋远. 发掘函数级单指令多数据向量化的方法[J]. 计算机应用, 2017, 37(8): 2200-2208.
[9]	张素平, 韩林, 丁丽丽, 王鹏翔. 新型超字级并行改进算法[J]. 计算机应用, 2017, 37(2): 450-456.
[10]	张晓琳, 王萍, 郭彦磊, 王静宇. 社会网络子集(θ, k)-匿名方法[J]. 计算机应用, 2015, 35(8): 2178-2183.
[11]	侯永生赵荣彩高伟高伟. 非正规化循环的单指令多数据向量化[J]. 计算机应用, 2013, 33(11): 3149-3154.
[12]	索维毅赵荣彩姚远刘鹏. 面向DSP的超字并行指令分析和冗余优化算法[J]. 计算机应用, 2012, 32(12): 3303-3307.
[13]	陈立宁罗可. 基于Apriori图挖掘算法的优化及其在3D构造解析的应用[J]. 计算机应用, 2010, 30(12): 3391-3396.
[14]	张博刚张威陈月宁廖飞雄. 基于运行监测的图形用户界面自动化测试模型[J]. 计算机应用, 2010, 30(10): 2749-2753.
[15]	郭鑫黄云颜一鸣周清平. 一种新的频繁子树增量式更新方法[J]. 计算机应用, 2010, 30(05): 1300-1303.

分段约束的超字并行向量发掘路径优化算法

Vector exploring path optimization algorithm of superword level parallelism with subsection constraints

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics