作者介紹

謝依暉

湖南大學碩士研究生在讀，

本科畢業(yè)于湖南大學計算機科學與技術專業(yè)

?

Abstract

本文調研了一些對OpenMP優(yōu)化的方式：

Matthias Müller開發(fā)了一個Benchmark，并用手寫優(yōu)化后代碼和優(yōu)化前代碼對多款編譯器進行測試是否已經支持文章提到的幾種優(yōu)化方式[1]。

在早期的OpenMP設計中，編譯器前端產生的不少優(yōu)化障礙是無法通過常用的編譯器中端優(yōu)化技術來克服的，如阻止了常量傳播等各種編譯器經典轉換，這些優(yōu)化障礙嚴重影響了性能。Johannes，Hal等在現(xiàn)有的LLVM/Clang編譯器工具鏈上提出了一些優(yōu)化方法，緩解了這些優(yōu)化障礙[2]。

Some Simple OpenMP Optimization Techniques

可選代碼

在有些時候，使用OpenMP對程序進行并行化的性能不如串行運行。因此可以在較小的工作負載時避免并行執(zhí)行來減少額外開銷。手寫代碼的解決方案如下：

?

if?(condtion)?then
?!$omp?parallel
??!?code
?!$omp?end?parallel
else
?!?code
end?if

?

孤立指令

孤立指令如果沒有動態(tài)地包含在并行區(qū)域中，OpenMP 標準規(guī)定“被視為遇到一個大小為1的線程組”。線程為1的并行化通常會有更差的性能，盡管手寫版本要多調用一個函數，可它依然有著更好的性能。

手寫優(yōu)化版本：

?

if?(omp_in_parallel())?then
?!$omp?parallel
??!?code
?!$omp?end?parallel
else
?!?code
end?if

?

合并并行區(qū)域

在循環(huán)沒有依賴關系時，連接上下兩個循環(huán)：

?

!$omp?parallel?do
?do?i?=?1,?100
??a(i)?=?i
?end?do
!$omp?end?parallel?do
!$omp?parallel?do
?do?i?=?1,?100
??b(i)?=?i
?end?do
!$omp?end?parallel?do

?

在并行區(qū)域末尾添加隱式的nowait

因為在循環(huán)和并行區(qū)域的末端之間沒有代碼，所以不需要多個barrier。因此可以增加nowait消除多余的barrier。

?

do?n?=?1,?100000
?!$omp?parallel
??!$omp?do
??do?i?=?1,?100
???a(i)?=?i
??end?do
??!$omp?end?do?nowait
?!$omp?end?parallel
end?do

?

通過OpenMP指令幫助優(yōu)化代碼

?

do?i?=?1,?100
?a(index(i))?=?a(index(i))?+?b(i)
end?do

?

這個代碼，因為index[i]對編譯器未知，編譯器不能假設循環(huán)之間是獨立的。但是加上?!$omp parallel do?后，如果這個循環(huán)可以并行執(zhí)行，那么這個代碼同樣也可以用software pipelining 或者 vectorization來優(yōu)化。

Compiler Optimizations for OpenMP

屬性傳播

程序員可以在代碼中使用例如const或者是restrict屬性，這能夠讓程序員更好地傳遞執(zhí)行軌跡集信息給編譯器以便后續(xù)的優(yōu)化。同樣，編譯器也可以采用屬性說明通過分析而得到一些信息。

筆者創(chuàng)建了一個LLVM傳播通道，它在并行工作函數的參數聲明中傳遞以下屬性：

缺少指針捕獲

訪問行為（只讀，只寫）

缺少可被訪問者調用的別名指針

指針的對齊，非空和 dereferencability 信息

在此簡單給一個例子，源代碼如下：

?

int?foo()?{
?int?a?=?0;
?#pragma?omp?parallel?shared(a)
?{
??#pragma?omp?critical
??{?a?+=?1;?}
??bar();
??#pragma?omp?critical
??{?a?*=?2;?}
?}
?return?a;
}

?

以下代碼為編譯器前端為源代碼產生的偽C風格表示：

?

int?foo()?{
?int?a?=?0;
?int?*restrict?p?=?&a;
?omp_parallel(pwork,?p);
?return?a;
}
void?pwork(int?tid,?int?*p)?{
?if?(omp_critical_start(tid))?{
??*p?=?*p?+?1;
??omp_critical_end(tid);
?}
?bar();
?if?(omp_critical_start(tid))?{
??*p?=?*p?*?2;
??omp_critical_end(tid);
?}
}

?

優(yōu)化后的代碼：

?

void?pwork(int?tid,?int?*restrict?p)?{
?if?(omp_critical_start(tid))?{
??*p?+=?1;
??omp_critical_end(tid);
?}
?bar()[p];?//?May?"use"?pointer?p.
?if?(omp_critical_start(tid))?{
??*p?*=?2;
??omp_critical_end(tid);
?}
}

?

變量私有化

OpenMP代碼涉及對所有變量的區(qū)域外聲明和區(qū)域內使用的冗長、易錯的分類。筆者根據變量的實際使用情況對變量分類進行轉換：

Shared：任何修改都可能對其它線程可見，也能在并行域之后可見。

Firstprivate：一個私有變量，但是使用并行域之前的值進行初始化。

Private：變量的本地線程的未初始化副本，類似于并行域中的shadowing重聲明。

從shared、firstprivate到private，允許對串行部分和并行部分使用單獨的變量，從而對兩個部分都做額外的優(yōu)化。但是如果下面的條件都滿足，那么私有化是允許的：

并行域結束后，在它的下一次使用之前，（重新）賦值過；

并行域內每個變量使用之前，都在并行域內賦值過；

變量的使用和它使用前的最后一次賦值沒有潛在的barrier。

此外，還可以用值傳遞代替引用傳遞，如果他們是live-in且不是live-out以及不用于線程間通信，這將是合理的。如果上面的條件只有第一個和最后一個滿足，將會傳遞變量的值。

最后，非live-out的變量可能可以在并行域前私有化，如果第一個條件成立，就用串行代碼中聲明的新變量的值替換并行域中的值。

并行域擴張

根據硬件的不同，并行域的開始和結束由于fork-join模式可能會增加大量的成本。以下代碼作為例子：

?

while?(ptr?!=?end)?{
?#pragma?omp?parallel?for?firstprivate(ptr)
?for?(int?i?=?ptr->lb;?i?ub;?i++)
??forward_work(ptr,?i);
?#pragma?omp?parallel?for?firstprivate(ptr,?a)
?for?(int?i?=?ptr->ub;?i?>?ptr->lb;?i--)
??backward_work(ptr,?a,?i?-?1);
?ptr?=?ptr->next;
}

?

外部循環(huán)和兩個并行域之間不存在依賴，為了降低fook和join的成本并改進程序內分析，擴展了相鄰的并行程序：

?

while?(ptr?!=?end)?{
?#pragma?omp?parallel?firstprivate(ptr,?a)
?{
??#pragma?omp?for?firstprivate(ptr)?nowait
??for?(int?i?=?ptr->lb;?i?ub;?i++)
???forward_work(ptr,?i);
??#pragma?omp?barrier?//?explicit?loop?end?barrier
??#pragma?omp?for?firstprivate(ptr,?a)?nowait
??for?(int?i?=?ptr->ub;?i?>?ptr->lb;?i--)
???backward_work(ptr,?a,?i?-?1);
??#pragma?omp?barrier?//?explicit?loop?end?barrier
?}
?ptr?=?ptr->next;
}

?

為了進一步減少開銷，擴展并行域也可以對串行構造展開，這只有在串行結構能得到適應的保護以及不會干擾并行語義的情況下進行。不過需要注意的是，以下優(yōu)化代碼會增加一個新的barrier：

?

#pragma?omp?parallel?shared(ptr)?firstprivate(a)
{
?while?(ptr?!=?end)?{
??#pragma?omp?for?firstprivate(ptr)?nowait
??for?(int?i?=?ptr->lb;?i?ub;?i++)
???forward_work(ptr,?i);
??#pragma?omp?barrier?//?explicit?loop?end?barrier
??#pragma?omp?for?firstprivate(ptr,?a)?nowait
??for?(int?i?=?ptr->ub;?i?>?ptr->lb;?i--)
???backward_work(ptr,?a,?i?-?1);
??#pragma?omp?barrier?//?explicit?loop?end?barrier
??#pragma?omp?master
??{?ptr?=?ptr->next;?}
??#pragma?omp?barrier?//?barrier?for?the?guarded?access
?}
}

?

通信優(yōu)化

串行代碼和并行代碼部分之間的運行時庫間接性不僅禁止信息傳輸，也禁止代碼運動。運行時函數調用的參數是在串行部分和并行部分之間通信的變量。這些變量是由前端根據代碼位置和捕獲語義確定的。

筆者提出的方法將執(zhí)行常量傳播，按值而不是按引用來傳遞參數，盡量減少要傳遞的變量的數量，將變量提出循環(huán)和并行區(qū)域。對優(yōu)化前的如下代碼，希望在通信時K和M被提出循環(huán)，N被512替代。

優(yōu)化前：

?

void?f(int?*X,?int?*restrict?Y)?{
?int?N?=?512;???//movable
?int?L?=?*X;?????//immovable
?int?A?=?N?+?L;??//movable
?#pragma?omp?parallel?for?firstprivate(X,?Y,?N,?L,?A)
?for?(int?i?=?0;?i?

	?

	優(yōu)化后：

	?
void?f(int?*X,?int?*restrict?Y)?{
?int?L?=?*X;
?int?K?=?*Y;
?int?M?=?512?*?K;
?#pragma?omp?parallel?firstprivate(X,?M,?L)
?{
??int?A?=?512?+?L;
??#pragma?omp?for?firstprivate(X,?M,?A,?L)
??for(int?i?=?0;?i?

	?

	?

	　審核編輯：湯梓紅