一种面向自动向量化和数据置换操作的中间表示

J4 ›› 2012, Vol. 34 ›› Issue (7): 71-77.

一种面向自动向量化和数据置换操作的中间表示

陈向，沈立

(国防科学技术大学计算机学院，湖南长沙 410073)

收稿日期:2010-06-17 修回日期:2010-11-10 出版日期:2012-07-25 发布日期:2012-07-25
基金资助:
国家973计划资助项目(2007CB310901)；国家自然科学基金资助项目(60803041)

An Automatic Vectorization and Data Permutation Oriented Intermediate Representation

CHEN Xiang,SHEN Li

(School of Computer Science,National University of Defense Technology,Changsha 410073,China)

Received:2010-06-17 Revised:2010-11-10 Online:2012-07-25 Published:2012-07-25

摘要/Abstract

摘要：

在现有的SIMD程序设计中，编译器或程序员都需要借助置换指令对参与运算的向量操作数进行重新组织，才能符合SIMD指令的要求。这些置换指令带来了较大的性能损失。本文提出了一种新的中间表示，它能够完整地记录标量和向量操作数的存储地址信息，使得置换指令的产生尽可能地推后，减少了冗余置换指令的产生。利用这种中间表示实现了一种数据置换操作的优化算法，它能够有效地减少置换指令带来的性能损失。面向一组典型的多媒体程序进行测试的结果表明，本文提出的方法可以平均获得7%的性能加速。

关键词: 中间表示, SIMD, 数据置换

Abstract:

Compilers or programmers have to use a permutation instruction to reorganize the element of vectors to get the correct operands for the SIMD instructions in the design of a SIMD program recently. But these redundant permutation instructions result in performance loss. This paper proposes a new intermediate representation, which contains enough address messages for the operands of scalar and vector. It makes the generation of data permutations be postponed and the redundant permutation instruction be reduced. We utilize this new intermediate representation to implement an optimization algorithm on data permutation, which can effectively reduce the performance loss from permutation instruction. The test result to a group of typical multimedia program shows that the algorithm can achieve 7% performance acceleration on average.

Key words: intermediate representation;SIMD;data permutation

陈向，沈立. 一种面向自动向量化和数据置换操作的中间表示[J]. J4, 2012, 34(7): 71-77.

CHEN Xiang,SHEN Li. An Automatic Vectorization and Data Permutation Oriented Intermediate Representation[J]. J4, 2012, 34(7): 71-77.

参考文献

［1］Firasta N,Buxton M,Jimbo P,et al.Intel AVX: New Frontiers in Performance Improvements and Energy Efficiency［Z］. Intel White Paper, 2008.
［2］Seiler L, Carmean D, Sprangle E, et al. Larrabee: A ManyCore x86 Architecture for Visual Computing［J］. ACM Transaction on Graphics, 2008 27(3):115.
［3］Larsen S, Amarasinghe S. Exploiting Superword Level Pararllelism［C］∥Proc of In PLDI’00, 2000:145156.
［4］VASTF/AltiVec: Automatic Fortran Vectorizer for PowerPC Vector Unit［EB/OL］.［20041015］.http://www.psrv.com/vast altivec.html.
［5］Lee R. Multimedia Extensions for GeneralPurpose Processors［C］∥Proc of SIPS’97,1997:923.
［6］Power PC Microprocessor Family: Vector/SIMD Multimedia Extension Technology Programming Environments Manual［Z］.IBM Corporation, 2005.
［7］Ren Gang, Wu Peng, Padua D A. Optimizing Data Permutations for SIMD Devices［C］∥Proc of PLDI’06, 2006:118131.
［8］Eichenberger A E, Wu Peng, O’Brien K. Vectorization for SIMD Architectures with Alignment Constraints［C］∥Proc of PLDI’04, 2004:8293.
［9］Wu Peng, Eichenberger A E, Wang A. Efficient SIMD Code Generation for Runtime Alignment and Length Conversion［C］∥Proc of CGO’05, 2005:153154.
［10］Shahbahrami A,Juurlink B,Vassliliadis S,et al.Matrix Register File and Extended Subwords: Two Techniques for Embedded Media Processors ［C］∥Proc of Conf on Computing Frontiers 2005:171179.
［11］Lee R B. Subword Permutation Instructions for TwoDimensional Multimedia Processing in MicroSIMD Architectures ［C］∥Pros of ASAP’00, 2000:314.
［12］Naishlos D, Biberstein M, David Ben S, et al. Vectorizing for a SIMD DSP Architecture［C］∥Proc of CASES’03, 2003:211.
［13］Slingerland N T, Smith A J. Design and Characterization of the Berkeley Multimedia Workload［J］. Multimedia Systems, 2002,8(4):315327.
［14］Shin J, Hall M, Chame J. SuperwordLevel Parallelism in the Presence of Control Flow［C］∥Proc of CGO’05, 2005:165175.
［15］Huang Libo, Shen Li, Wang Zhiying, et al. SIF: Overcoming the Limitations of SIMD Devices Via Implicit Permutation［C］∥Proc of the 16th International Symposium on High Performance Computer Architecture,2010:112.

[1]	朱广林, 吕方, 赖庆宽, 陈华英, 何先波, . 编译器中激进蝴蝶优化方法的研究与实现[J]. 计算机工程与科学, 2021, 43(06): 962-968.
[2]	赵永浩, 贾海鹏, 张云泉, 张思佳. 基于SIMD的Square Root函数高性能实现与优化[J]. 计算机工程与科学, 2021, 43(04): 662-669.
[3]	张家豪，单征，岳峰，傅立国，王军，李明亮. 基于TCG技术的二进制翻译条件转移指令优化研究[J]. 计算机工程与科学, 2019, 41(08): 1343-1352.
[4]	孙海燕. 一种支持SIMD体系结构的高效分布式堆栈——HEDSSA[J]. 计算机工程与科学, 2017, 39(11): 1986-1990.
[5]	邓子椰，陈书明，彭元喜，雷元武. 一种基于SRT-8算法的SIMD浮点除法器的设计与实现[J]. J4, 2014, 36(05): 797-803.
[6]	姚文科1，杜云飞2，吴强1，杨灿群1. 基于Intel Xeon Phi的激光等离子体粒子模拟研究[J]. J4, 2014, 36(05): 809-813.
[7]	李国强,陈书明,万江华,杨惠. FT-SIMD: 一种高性能乘法器的设计[J]. J4, 2012, 34(1): 53-57.
[8]	辛乃军,陈旭灿,孙海燕,阳柳,罗杰,淡孝强,王霁. 基于GCC的高性能DSP Matrix向量指令集扩展[J]. J4, 2012, 34(1): 58-63.
[9]	吴铁彬,刘衡竹,杨惠,张剑锋,侯申. 一种快速SIMD浮点乘加器的设计与实现[J]. J4, 2012, 34(1): 69-73.
[10]	崔进鲜，庞建民，岳峰，张一弛，张刚. 动态二进制翻译中不对界问题的处理[J]. J4, 2010, 32(9): 95-97.
[11]	李初辉王伟肖玮. 一种共享主存二维SIMD结构资源分配算法的改进与实现[J]. J4, 2008, 30(9): 99-102.
[12]	董亚卓[1] 左艳辉[1] 刘明政[2] 窦勇[1]. 一种面向可重构硬件的编译中间表示方法[J]. J4, 2008, 30(9): 147-150.
[13]	钱兴隆臧斌宇朱传琪. 一种SIMD优化中的向量寄存器部分重用方法[J]. J4, 2007, 29(5): 141-146.
[14]	杜谋辉[1] 周媛媛[2] 余圣发[2] 林嘉宇[2]. H．264帧内预测模块在TMS320C6416上的并行实现[J]. J4, 2006, 28(11): 51-53.