基于全局数据重组的循环倾斜优化

doi:10.3969/j.issn.1006-2475.2017.06.009

计算机与现代化

基于全局数据重组的循环倾斜优化

(1.南方电网科学研究院有限责任公司，广东广州 510080;
2.电力行业信息安全等级保护测评中心第五实验室，广东广州 510080;
3.数学工程与先进计算国家重点实验室，河南郑州 450002)

收稿日期:2016-10-01 出版日期:2017-06-23 发布日期:2017-06-23
作者简介:陈华军(1980-)，男，湖北黄冈人，南方电网科学研究院有限责任公司、电力行业信息安全等级保护测评中心第五实验室高级工程师，硕士，研究方向：电力系统信息通信与信息安全; 王琦(1992-)，男，数学工程与先进计算国家重点实验室硕士研究生，研究方向：先进编译，高性能计算; 洪超(1987-)，男，助理研究员，硕士，研究方向：计算机网络，信息安全; 方萌(1989-)，男，助理研究员，硕士，研究方向：大数据，云计算，云安全。

Loop Skewing Optimization on Global Data Regrouping

(1. China South Power Grid International Co., Ltd., Guangzhou 510080, China;
2. 5th Lab, Electric Power Information Security Classified Protection Test and Evaluation Center, Guangzhou 510080, China;
3. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450002, China)

Received:2016-10-01 Online:2017-06-23 Published:2017-06-23

摘要/Abstract

摘要： 循环倾斜是程序优化中一种循环变换的手段，它改变空间迭代形式，将循环存在的跨迭代的并行用传统的并行标识出来，使得循环可以并行执行。但是循环倾斜后，并行执行的数据在内存中是离散的，而且每次迭代执行的次数是不一致的。为了更有效地利用SIMD，本文提出一种基于全局数据重组的循环倾斜优化方法。首先分析循环倾斜优化，针对数据离散的问题实现全局数据重组，改善数据局部性，循环易于向量化操作；针对迭代执行次数不一致问题，实现非满载向量操作，使尾循环得以向量执行。最后选择wavefront程序进行测试，优化后，程序计算可以获得平均10.73倍的加速效果。

关键词: 单指令多数据流, 循环倾斜, 数据重组, 非满载向量化

Abstract: Loop skewing is a method of loop transformation in program optimization. It changes the form of iteration space and marks the across iterations in loops with the traditional parallel. The loop can be calculated in parallel. But after loop skewing, data which is programed in parallel is discrete. Times of every iteration execution are different. To make full use of SIMD extension, this paper presents loop skewing optimization on global data regrouping. We analyze loop skewing optimization and regroup the data in array for the problem of discrete data. This part improves the data locality and it is simple to do the vector operation. Then we realize the non-full vector operation for the problem of different iteration times. This part makes the tail loop can be executed in vectorization. At last, we choose the wavefront program for testing. After optimization, the program execution speed can be increased by 10.73 times in average.

Key words: SIMD, loop skew, data regroup, non-full vector operation

中图分类号:

TP312

陈华军1,2，王琦3，洪超1,2，方萌1,2. 基于全局数据重组的循环倾斜优化[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2017.06.009.

CHEN Hua-jun1,2, WANG Qi3, HONG Chao1,2, FANG Meng1,2. Loop Skewing Optimization on Global Data Regrouping[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2017.06.009.

参考文献

[1] Intel. Intel Intrinsics Guide[DB/OL]. https://software.intel.com/sites/landingpage/IntrinsicsGuide/, 2011-10-20.

[2] Pennycook S J, Hughes C J, Smelyanskiy M, et al. Exploring SIMD for molecular dynamics, using Intel® Xeon® processors and Intel® Xeon Phi^TM coprocessors[C]// Proceedings of the 2013 IEEE 27th International Symposium on Parallel and Distributed Processing. 2013:1085-1097.

[3] Liu Xing, Smelyanskiy M, Chow E, et al. Efficient sparse matrix-vector multiplication on x86-based many-core processors[C]// Proceedings of the 27th International ACM Conference on Supercomputing. 2013:273-282.

[4] 高伟,赵荣彩,韩林,等. SIMD自动向量化编译优化概述[J]. 软件学报, 2015,26(6):1265-1284.

[5] 陈火旺,刘春林,谭庆平,等. 程序设计语言:编译原理[M]. 3版. 北京:国防工业出版社, 2000.

[6] Zhao Yuan, Kennedy K. Scalarization using loop alignment and loop skewing[J]. Journal of Supercomputing, 2005,31(1):5-46.

[7] Sarkar V. Optimized unrolling of nested loops[C]// Proceedings of the 14th ACM International Conference on Supercomputing. 2000:153-166.

[8] Liu Jun, Zhang Yuanrui, Jang O, et al. A compiler framework for extracting superword level parallelism[C]// Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation. 2012:347-358.

[9] Liu Peng, Zhao Rongcai, Gao Wei, 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. 2013:521-527.

[10] Dragomir O S, Bertels K. K-loops: Loop skewing for reconfigurable architectures[C]// Proceedings of the 2009 IEEE International Conference on Field-Programmable Technology. 2009:199-206.

[11] Sinkarovs A, Scholz S B. Data layout inference for code vectorisation[C]// Proceedings of the 2013 IEEE International Conference on High Performance Computing and Simulation. 2013:527-534.

[12] Mei Gang, Tian Hong. Performance Impact of Data Layout on the GPU-accelerated IDW Interpolation[DB/OL]. https://arxiv.org/pdf/1402.4986v1.pdf, 2014-02-20.

[1]	梁天恺, 黄康华, 刘凯航, 兰岚, 曾碧. 基于双向同态加密的深度联邦图片分类方法[J]. 计算机与现代化, 2023, 0(12): 36-40.
[2]	朱宏启, 王诚. 基于电商用户行为的隐式反馈推荐应用研究[J]. 计算机与现代化, 2023, 0(11): 44-50.
[3]	李曈, 丁国富. 一种支持多线程程序的符号执行技术[J]. 计算机与现代化, 2020, 0(06): 60-.
[4]	陈婷，余小平，陈俊凤，邓鹏，龚代平，邓小红. 基于平面不封闭图形切割的路径规划[J]. 计算机与现代化, 2019, 0(08): 39-.
[5]	张晓燕1,赫俊民2,刘文英1,林亚林1. 基于种群划分与变异策略的粒子群优化算法[J]. 计算机与现代化, 2019, 0(05): 122-.
[6]	汤雪芹. 基于自适应遗传算法的城际列车运行图编制方法[J]. 计算机与现代化, 2019, 0(03): 68-.
[7]	沈茂东1，裴健1，付新阳1，张俊岭1，公凡奎1，刘霞2. 一种新的输电线路异物检测网络结构——TLFOD Net[J]. 计算机与现代化, 2019, 0(02): 118-.
[8]	戴海能,茅耀斌. 一种改进的基于R-FCN模型的人脸检测算法[J]. 计算机与现代化, 2018, 0(08): 12-.
[9]	何俊杰,肖可,刘畅,陈松岩. 基于区域神经网络的TFT-LCD电路缺陷检测方法[J]. 计算机与现代化, 2018, 0(07): 33-.
[10]	周华君,丁爱芬,吕小俊. 一种基于策略集的概率缩域算法对多目标随机组卷问题的解决方案[J]. 计算机与现代化, 2018, 0(02): 80-.
[11]	王德宇1，徐友春2，李永乐2，陆峰1，郑凯文1. 基于深度学习的车辆检测方法[J]. 计算机与现代化, 2017, 0(8): 56-.
[12]	杨维永1，何军2，郑生军3，张旭东4. 一种适宜于子空间聚类的离群点检测算法[J]. 计算机与现代化, 2015, 0(12): 39-.
[13]	杨浩敏,马超,吴海燕. 一种改进型的分布式Lazy关联分类算法[J]. 计算机与现代化, 2015, 0(8): 116-120.
[14]	马世欢，李伟. 基于改进蚁群优化算法的网络服务质量路由算法[J]. 计算机与现代化, 2015, 0(7): 77-.
[15]	郭峰,曾培峰. 基于分布式服务器的视频监视系统[J]. 计算机与现代化, 2015, 0(6): 74-77+100.

基于全局数据重组的循环倾斜优化

Loop Skewing Optimization on Global Data Regrouping

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价