面向DSWP并行的OpenMP任务调度机制的扩展与实现

Extension to OpenMP Task Scheduling Mechanism for DSWP Parallelization and its Implementation

多核处理器能够提升多线程程序的性能,但早已存在的诸多单线程程序无法从中获益,程序员也习惯于编写单线程程序。自动并行化技术是将单线程程序移植到多核上的重要手段,但是当循环中存在无法确定的数据依赖或复杂的控制流时,传统的自动并行化技术无法取得良好效果。Ottoni等人针对传统自动并行失败的循环提出了Decoupled Software Pipelining(DSWP)算法用以实现指令级的细粒度并行,但其需要对处理器体系结构的深入了解以及对核间通信队列和专用指令的硬件支持,并行性能和应用广泛性受到限制。基于OpenMP应用编程接口实现的DSWP并行不依赖于硬件上对核间通信队列和专用指令的支持,且不受平台的限制,但现有的OpenMP任务调度机制无法满足DSWP并行中对任务调度的需求。对现有的OpenMP任务调度机制进行扩展,增加了任务与线程绑定的属性,保证了基于OpenMP的DSWP并行程序的正确执行。在GCC的OpenMP运行库libgomp中扩展了任务绑定属性子句的功能,扩展后的GCC作为OpenMP DSWP程序的基础编译器,为自动并行提供支持。通过对基准测试集NPB3.3.1的测试表明,传统自动并行失败的循环,经OpenMP DSWP自动并行后在双核处理器上平均加速比达到1.23以上;使用添加了OpenMP DSWP算法的Open64编译器生成的并行程序,与仅使用传统自动并行方法的Intel编译器和Open64编译器所得程序相比,平均加速比分别高出22%和26%。

While multicore processors increase throughput for multi-programmed and multithreaded codes, many impor-tant applications are single threaded and thus are not benefited. Automatic parallelization techniques play an important role in migrating singe threaded applications to multicore platform. Unfortunately, the prevalence of control flow, recur-sire data structures, and general pointer accesses in ordinary programs renders the existing techniques unsuitable. Ottoni et al. proposed an automatic parallelization algorithm called Decoupled Software Pipelining （DSWP）to exploit fine- grained pipeline parallelism at the instruction level. But it requires knowledge of micro-architectural properties and hard- ware support of a communication channel and two special instructions. The improved DSWP algorithm based on OpertMP increases the parallel granularity and does not rely on hardware support any more, but the existing OpenMP task scheduling mechanism cannot satisfy the need of DSWP. A new binding clause for the task construct in OpenMP was proposed to extend the task scheduling mechanism. It guarantees the correctness of the OpenMP DSWP paralleliza-tion. The new clause is implemented in the GCC runtime library libgomp, which provides support for the compilation of OpenMP DSWP programs. The experimental results show that loops failed to be parallelized by existing techniques can be parallelized by the improved automatic parallelization algorithm and gain significant performance improvement on du-al-core CPU. The average performance speedup is up to 1.23. Compared with Intel and Open64 compilers, the compiler with the improved algorithm can increase execution efficiency evidently and the average speedup of the OpenMP DSWP programs generated by it increases more than 22% and 26%.