Abstract
本文调研了一些对OpenMP进行优化的方法:
- H. Ma, R. Zhao, X. Gao and Y. Zhang针对OpenMP程序中的barrier提出几种新功能的支持和性能的优化^[1]^;
- 在SC20的Booth Talks上,Johannes Doerfert分享了在LLVM上对OpenMP做的一些优化^[2]^。
Barrier Optimization for OpenMP Program^[1]^
删除冗余的barrier
通过并行数据流分析,两个循环之间无数据依赖,所以S1的barrier是冗余的;parallel结束的时候有一个隐式的barrier,所以S2的barrier也是冗余的。
!$omp parallel
!$omp do
do i = 1, 100
a(i) = d(i)
end do !barrier S1
!$omp end do
!$omp do
do i = 1, 100
b(i) = c(i)
end do !barrier S2
!$omp end do
!$omp end parallel
优化时,可以在该语句块加上显式的nowait(!$omp end do nowait)。
实现DOACROSS并行
当并行化循环的时候,如果循环依赖距离是一个常数,如下代码:
do i = 2, 100
do j = 2, 100
a(i, j) = a(i - 1, j) + a(i, j-1)
end do
end do
对外层循环i进行数据依赖检查,可以得到a[i][j]和a[i-1][j]之间的依赖距离为1。因此循环可以以DOACROSS并行的方式运行。OpenMP只实现了DOALL并行,没有与DOACROSS对应的语句。
实现时,定义共享数组“_mylocks [ threadid ]”来存储每个线程的事件,定义私有变量_counter0指示当前线程正在等待的事件。数组“_mylocks”中的元素总数是线程数,每个元素表示相应线程的当前状态。实现的代码如下:
int _mylocks[256];
#pragma omp parallel
{
int _counter0 = l;
int _my_id = omp_get_thread_num();
int _my_nprocs = omp_get_num_threads();
_mylocks[my_id] = 0;
for (j_tile = 0; j_tile < N - l; j_tile += M) {
if (_my_id > 0) {
do {
#pragma omp flush(_mylock)
} while (_mylock[myid - l] < _counter0);
#pragma omp flush(a, _mylock)
_counter0 +=1;
}
#pragma omp for nowait
for (i = l; i < N; i++) {
for (j = j_tile; j < j_tile + M; j++){
a[i][j] = a[i - 1][j] + a[i][j - 1];
}
}
_mylock[myid] += 1;
#pragma omp flush(a, _mylock)
}
}
Region Barrier
当线程遇到region barrier时会继续执行。但是直到其他所有线程都进入这个区域之后,它才能运行出该区域。这样的好处是允许线程继续运行而不空转,可以实现CPU的负载均衡。
region barrier的实现代码如下:
unsigned _counter = 0;
#pragma omp parallel
{
{first parallel region}
#pragma omp atomic
_counter++;
{barrier region}
#pragma omp flush(counter)
while(counter % omp_get_num_threads())
{
#pragma omp flush(counter)
}
#pragma omp flush
{third parallel region}
}
当使用region barrier时,需要保证并行域R1和R3与并行域R2无依赖关系。
OpenMP SC20 Booth Talk Series : OpenMP compiler optimizations in LLVM ^[2]^
OpenMP运行时调用重复数据的消除
double *A = malloc(size * omp_get_thread_limit());
double *B = malloc(size * omp_get_thread_limit());
#pragma omp parallel
do_work(&A[omp_get_thread_num() * size]);
#pragma omp parallel
do_work(&B[omp_get_thread_num() * size]);
示例代码中重复调用了omp_get_thread_limit()和omp_get_thread_num()函数,可以将重复调用合并至一次调用。该功能已在LLVM实现,可通过如下编译选项进行优化:
$ clang deduplicate.c -g -O2 -fopenmp -Rpass=openmp-opt
Tracking OpenMP Internal Control Variables
void foo() {
#pragma omp parallel
bar();
}
void bar() {
if (omp_in_parallel()) {
...
} else {
...
}
}
以上代码,如果omp_in_parallel()的返回值可以判断为真,那么这个if结构就可以被删除。
References
- H. Ma, R. Zhao, X. Gao and Y. Zhang, "Barrier Optimization for OpenMP Program," 2009 10th ACIS International Conference on Software Engineering, Artificial Intelligences, Networking and Parallel/Distributed Computing, 2009, pp. 495-500, doi: 10.1109/SNPD.2009.16.
- https://www.openmp.org/wp-content/uploads/OpenMPOpt-in-LLVM-SC20-JD.pdf
作者介绍:谢依晖
湖南大学硕士研究生在读,本科毕业于湖南大学计算机科学与技术专业