一种基于OpenMP的DSWP自动并行算法  

Automatic Decoupled Software Pipelining Parallelization Algorithm Based on Open MP

作　　者：刘晓娴[1] 赵荣彩[2,3] 韩林[2,3] 李雁冰[2,3] 

机构地区：[1]广州军区联勤部,广东广州510000 [2]信息工程大学,河南郑州450001 [3]数学工程与先进计算国家重点实验室,河南郑州450001

出　　处：《信息工程大学学报》2015年第2期225-233,共9页Journal of Information Engineering University

基　　金：国家科技重大专项资助项目(009ZX01036-001-001-2)

摘　　要：多核处理器能够提升多线程程序的性能,但早已存在的诸多单线程程序无法从中获益,程序员也习惯于编写单线程程序。自动并行化技术是将单线程程序移植到多核上的重要手段,但是当循环中存在无法确定的数据依赖或复杂的控制流时,传统的自动并行化技术无法取得良好效果。decoupled software pipelining(DSWP)算法针对传统自动并行失败的循环实现了指令级的细粒度并行,但是需要对处理器体系结构和指令集的深入了解,对其并行性能和应用广泛性带来限制。通过对DSWP算法进行改进,提出了基于Open MP的DSWP自动并行算法。该算法增大了并行粒度,使用Open MP并行应用编程接口实现并行,不再依赖具体的体系结构,实现了DSWP算法的应用扩展。通过对基准测试集NPB3.3.1的测试表明,传统自动并行失败的循环,经文章算法并行后在双核处理器上平均加速比达到1.23以上;使用添加了文章算法的Open64编译器生成的并行程序,与仅使用传统自动并行方法的Intel编译器和Open64编译器所得程序相比,平均加速比分别高出22%和26%。Automatic parallelization techniques play an important role in migrating single threaded applications to muhicore platforms. Unfortunately, the prevalence of control flows, recursive data structures, and general pointer accesses in ordinary programs render the existing techniques unsuita- ble. An automatic parallelization algorithm called Decoupled Software Pipelining （DSWP） is pro- posed to exploit the fine-grained pipeline parallelism at the instruction level. But it requires the knowledge of micro-architectural properties and hardware support of a communication channel and two special instructions. An improved DSWP algorithm based on OpenMP is proposed. It increases the parallel granularity and does not rely on hardware support any more. The experimental results show that loops unable to be parallelized by existing techniques can be parallelized by the proposed algorithm and gain significant performance improvement on dual-core CPU. The average ratio of the performance speedup is up to 1.23. Compared with Intel and 0pen64 compilers, the compiler ex- tended with the proposed algorithm can increase execution efficiency evidently and the average speedup of the generated parallel codes increases more than 22% and 26%.

关 键 词：自动并行化 OPENMP DSWP 

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