一种单指令多数据向量化归约方法

doi:10.3969/j.issn.1000-3428.2017.07.002

计算机工程

一种单指令多数据向量化归约方法

韩林,高伟,王冬,王鹏翔,李颖颖

(信息工程大学网络空间安全学院,郑州 450000)

收稿日期:2016-02-24 出版日期:2017-07-15 发布日期:2017-07-15
作者简介:韩林(1978—),男,博士,主研方向为先进编译技术、高性能计算;高伟,博士研究生;王冬、王鹏翔,硕士研究生;李颖颖,硕士。
基金资助:
数学工程与先进计算国家重点实验室开放课题(2013A11);郑州市科技局前沿技术研究计划项目(141PQYJS558)。

A Single Instruction Multiple Data Vectorization Reduction Method

HAN Lin,GAO Wei,WANG Dong,WANG Pengxiang,LI Yingying

(Institute of Cybersecurity,Information Engineering University,Zhengzhou 450000,China)

Received:2016-02-24 Online:2017-07-15 Published:2017-07-15

摘要/Abstract

摘要： 单指令多数据(SIMD)扩展部件旨在发掘多媒体程序和科学计算程序的数据级并行,归约操作引起的真依赖给发掘程序中的数据级并行带来了阻碍。但体系结构和指令集的差异,使得面向向量机的归约向量化方法并不适用于SIMD扩展部件。针对上述问题,提出一种面向SIMD扩展部件的归约向量代码生成方法,以及归约的识别方法,利用向量移位指令实现向量代码生成。基于SPEC2006标准测试集的测试结果表明,与未利用归约向量化技术前相比,利用该归约向量化方法后的向量化加速比提高34%,从而验证了该方法的有效性。

关键词: 单指令多数据向量化, 归约, 依赖分析, 代码生成, 并行性

Abstract: Single Instruction Multiple Data(SIMD) aims at exploiting the data-level parallelism of multimedia and scientific calculation.The true dependence caused by reduction operation hinders exploring data-level parallelism.But different architecture and instruction set make reduction vectorization method based on vector machine unsuitable to SIMD.This paper presents a new approach of generating SIMD code with reduction.It presents a method to identify reduction operations,and conducts code generation using vector shift instructions.Experimental result based on SPEC and some other standard test sets shows the validity of this method,with 34% improvement in the vectorization acceleration ratio.

Key words: Single Instruction Multiple Data(SIMD) vectorization, reduction, dependence analysis, code generation, parallelism

中图分类号:

TP391

韩林,高伟,王冬,王鹏翔,李颖颖. 一种单指令多数据向量化归约方法[J]. 计算机工程, doi: 10.3969/j.issn.1000-3428.2017.07.002.

HAN Lin,GAO Wei,WANG Dong,WANG Pengxiang,LI Yingying. A Single Instruction Multiple Data Vectorization Reduction Method[J]. Computer Engineering, doi: 10.3969/j.issn.1000-3428.2017.07.002.

https://www.ecice06.com/CN/Y2017/V43/I7/9

参考文献

参考文献［1］高伟,赵荣彩,韩林,等.SIMD自动向量化编译优化概述［J］.软件学报,2015,26(6):1265-1284. ［2］Intel Company.Intel C++Compiler［EB/OL］.［2016-03-21］.http://icc.gnu.org. ［3］Free Software Foudation.GNU Compiler Collection［EB/OL］.［2016-05-11］.http://gcc.gnu.org. ［4］Open64 Compiler［EB/OL］.［2016-05-23］.http://open64.sourceforge.net. ［5］魏帅.面向SIMD的向量化算法及重组技术研究［D］.郑州:解放军信息工程大学,2012. ［6］Allen R,Kennedy K.Optimizing Compilers for Modern Architectures［M］.［S.1.］:Morgan Kaufmann Publishers,2001. ［7］Nuzman D,Zaks A.Outer-loop Vectorization-revisited for Short SIMD Architectures［C］//Proceedings of 2008 International Conference on Parallel Architectures and Compilation Techniques.Toronto,Canada:［s.n.］,2008:215-222. ［8］Trifunovic K,Nuzman D,Cohen A,et al.Polyhedral-model Guided Loop-nest Auto-vectorization［C］//Proceedings of 2009 International Conference on Parallel Architectures and Compilation Techniques.Raleigh,USA:［s.n.］,2009:326-333. ［9］Kong M,Veras R,Stock K.When Polyhedral Transformations Meet SIMD Code Generation［C］//Proceedings of 2013 Conference on Programming Language Design and Implementation.Washington D.C.,USA:IEEE Press,2013:125-132. ［10］Barik R,Zhao Jisheng,Sarkar V.Efficient Selection of Vector Instructions Using Dynamic Programming［C］//Proceedings of the 43rd Annual IEEE/ACM Inter-national Symposium on Microarchitecture.Atlanta,USA:［s.n.］,2010:226-277. ［11］Liu Jun,Zhang Yuanrui,Kandemir M.A Compiler Framework for Extracting Superword Level Parallelism［C］//Proceedings of 2012 Conference on Programming Language Design and Implementation.Beijing,China:［s.n.］,2012:163-174. ［12］Karrenberg R,Hack S.Whole-function Vectorization［C］//Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization.Washington D.C.,USA:IEEE Press,2011:222-232. ［13］Shahbahrami A,Juurlink B,Vassiliadis S.Performance Impact of Misaligned Accesses in SIMD Extensions［C］//Proceedings of the 17th Annual Workshop on Circuits,Systems and Signal Processing.Washington D.C.,USA:IEEE Press,2006:334-342. ［14］Eichenberger A E,Wu P,O′Brien K.Vectorization for SIMD Architectures with Alignment Constraints［C］//Proceeding of ACM SIGPLAN 2004 Conference on Programming language Design and Implementation.New York,USA:ACM Press,2004:82-93. ［15］Larsen S,Witchel E,Amarasin S P.Increasing and Detecting Memory Address Congruence［C］//Pro-ceedings of 2002 IEEE International Conference on Parallel Architectures and Compilation Techniques.Washington D.C.,USA:IEEE Press,2002:18-29. ［16］Chang H,Sung W.Efficient Vectorization of SIMD Programs with Non-aligned and Irregular Data Access Hardware［C］//Proceedings of 2008 International Con-ference on Compilers,Architectures and Synthesis for Embedded Systems.New York,USA:ACM Press,2008:167-176. ［17］Bik A J C,Girkar M,Grey P M,et al.Automatic Intra-register Vectorization for the Intel Architecture［J］.International Journal of Parallel Programming,2002,32(2):65-98. ［18］Ren Gang,Wu Peng,Padua D A.Optimizing Data Permutations for SIMD Device［C］//Proceedings of 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation.New York,USA:ACM Press,2006:118-131. ［19］Li Yuxiang,Shi Hui,Li Chen.Vectorization-oriented Local Data Regrouping［J］.Computer System,2009,30(8):1529-1534. ［20］Nuzman D,Rosen I A.Auto-vectorization of Interleaved Data for SIMD［C］//Proceedings of ACM SIGPLAN Conference on Programming Language Design and Implementation.New York,USA:ACM Press,2006:132-143. ［21］Huang Libo,Li Chen,Wang Zhiying,et al.SIF:Over-coming the Limitations of SIMD Devices via Implicit Permutation［C］//Proceedings of the 16th International Symposium on High-performance Computer Architec-ture.Washington D.C.,USA:IEEE Press,2010:355-366. ［22］姚远.SIMD自动向量识别及代码调优技术研究［D］.郑州:解放军信息工程大学,2012. ［23］肖玮.二维SIMD结构的编译优化与功耗研究［D］.上海:复旦大学,2008. 编辑索书志

[1]	刘金硕, 文尧. 模板运算代码的自动生成与调优框架[J]. 计算机工程, 2024, 50(6): 35-47.
[2]	李宝莹, 李志淮, 王成爱, 杨锋. 自适应节点规模的区块链分片可扩展模型[J]. 计算机工程, 2024, 50(3): 137-147.
[3]	高秀武, 姜军, 白书敬, 黄亮明. 一种加速访存地址计算的编译优化[J]. 计算机工程, 2023, 49(1): 173-180.
[4]	尹青山. 一种面向无线体域网的改进SMART算法[J]. 计算机工程, 2019, 45(11): 121-125.
[5]	赵璐,张健沛,杨静. 收缩候选回溯集的有状态动态偏序归约方法[J]. 计算机工程, 2015, 41(5): 70-76.
[6]	孙大群，严义，邬惠峰. 梯形图数据依赖关系分析与并行提取[J]. 计算机工程, 2014, 40(2): 67-70,76.
[7]	臧统政, 吕克伟. 基于部分信息泄露的Hensel提升计算问题[J]. 计算机工程, 2013, 39(8): 38-43,54.
[8]	王小鉴, 廖晓峰, 黄宏宇. 基于归约函数数量裁减的彩虹表技术改进[J]. 计算机工程, 2013, 39(7): 156-160,164.
[9]	彭军，黎福海，罗旗舞，肖祥慧. 一种多通道并行固态存储系统的设计与实现[J]. 计算机工程, 2013, 39(12): 40-44,59.
[10]	王宁, 王铮. ICE系统自动生成研究[J]. 计算机工程, 2012, 38(22): 271-275.
[11]	金瑛棋, 吴俊敏, 赵小雨. 公平性考虑的短作业优先内存调度策略[J]. 计算机工程, 2012, 38(20): 243-246.
[12]	王申, 漆锋滨, 谷洪峰, 潘治. Linpack并行性能模型及其预测[J]. 计算机工程, 2012, 38(16): 81-84.
[13]	王建锋, 张天宏, 黄向华. 基于Matlab的复杂控制系统软件开发[J]. 计算机工程, 2012, 38(10): 54-56.
[14]	宋庆增, 顾军华. 稀疏矩阵向量乘的FPGA设计与实现[J]. 计算机工程, 2011, 37(23): 214-216.
[15]	马强, 刘佩林. 基于编程语言结构的通用配置代码生成方法[J]. 计算机工程, 2010, 36(18): 54-56.

选择文件类型/文献管理软件名称

选择包含的内容

一种单指令多数据向量化归约方法

A Single Instruction Multiple Data Vectorization Reduction Method

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

一种单指令多数据向量化归约方法

A Single Instruction Multiple Data Vectorization Reduction Method

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价