SIMD数据置换操作的自动生成和优化  

Automatic Data Permutation Generation and Optimization for SIMD Devices

作　　者：陈向[1] 沈立[1] 李家文[1] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073

出　　处：《计算机科学》2011年第5期290-294,共5页Computer Science

基　　金：国家"973"重点基础研究发展计划(2007CB310901);国家自然科学基金项目(60803041)资助

摘　　要：SIMD指令能够高效开发数据级并行,因此当前绝大多数通用微处理器都支持这种机制。但是应用程序和算法的一些固有特性,如访存地址不对齐、非连续存储访问以及控制流等,使得编译器或程序员必须借助置换指令重新组合向量的各个元素,才能得到符合SIMD指令要求的操作数。这些冗余的置换指令已成为当前挖掘数据级并行的主要性能瓶颈。提出一种自动的数据置换指令生成和优化算法,以有效地减少置换指令带来的性能损失。该算法基于提出的一种新中间表示形式,其中包含有足够的操作数地址信息,因此可以将置换指令的生成转换为数据流图中冲突边的识别问题,而将置换指令的优化转化为用最少的置换指令来删除所有冲突边的问题。面向一组典型多媒体程序进行测试的结果表明,提出的算法可平均获得7%的性能加速。Nowadays,more and more general-purpose microprocessors provide enhanced SIMD instruction-set extensions to exploit data level parallelism.However,some inherent characteristics of applications and algorithms,such as memory address nonalignment,inconsecutive memory access and control flow,etc.,make compilers or programmers have to use permutation instruction to reorganize the element of vectors to get correct operands for SIMD instructions.And these redundant permutation instructions had become the performance bottleneck of exploiting data level paralle-lism.This paper proposed an automatic data permutation generation and optimization algorithm.It can effectively reduce the performance loss caused by permutation instruction.The algorithm is based on a new intermediate representation,which contains enough address message of the operand,with which the problem of data permutation generation and optimization can be solved via identifying and eliminating all conflict edges in data flow graphs with minimal costs.The test result to a group of typical multimedia program shows that the algorithm can achieve performance acceleration up to 7% on the average.

关 键 词：数据置换 中间表示 冲突边 

分 类 号：TP314[自动化与计算机技术—计算机软件与理论]