一种新型自动向量化编译算法

A New Algorithm for Auto-Vectorization Compilation

SIMD(single instruction multiple data)体系结构在高性能计算与嵌入式多媒体计算中扮演着重要的角色,对于SIMD指令的自动向量化编译技术是当前编译领域的研究热点.本文基于超字并行(super-word level parallelism,SLP)算法提出了一种新的自动向量化算法GSLP(global super-word level parallelism),该算法分为两部分:语句分组和语句调度.语句分组从全局出发分析超字复用信息,在语句分组的过程中,充分挖掘基本块的直接或者间接的超字复用信息,提高基本块内语句并行操作的机会;语句调度对基本块内的所有语句进行调度并调整超字内部单字(Single-word)数据的组织顺序,使生成的代码中打包/解包(pack/unpack)操作的数量降到最低.使用16个测试程序对GSLP算法进行测试,试验结果表明该算法使打包/解包操作的数量平均减少了41.6%,与SLP算法所产生的加速相比平均提高了4.7%.

The SIMD（single instruction multiple data）architecture plays an important role in high performance and embedded multi-media computing.Auto-vectorization compilation for SIMD instruction is the current hot research topic in the field of compilation.This paper proposed a new auto-vectorization algorithm GLSP（global super-word level parallelism）.Our algorithm mainly consists of two parts,statement grouping and statement scheduling.Statement grouping analyzes the reuse information of super-word from the global situation,makes full use of the opportunities on direct or indirect super-word reuse for basic blocks,and improves the opportunities on parallel operation of statements in a basic block.Statement scheduling reduces the number of packing and unpacking operation to minimum in generated code by scheduling all statements in a basic block and adjusts the organization order of single word in a super-word.A test including 16 test benches has been applied on GLSP algorithm.The experimental result showed that,compared with SLP algorithm,it has an average 41.6% reduction on pack/unpack operations,and an average 4.7%improvement on speed-up.