作者介紹

謝依暉

湖南大學(xué)碩士研究生在讀，

本科畢業(yè)于湖南大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)

?

Abstract

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

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

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

Some Simple OpenMP Optimization Techniques

可選代碼

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

?

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

?

孤立指令

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

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

?

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

?

合并并行區(qū)域

在循環(huán)沒有依賴關(guān)系時(shí)，連接上下兩個(gè)循環(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

因?yàn)樵谘h(huán)和并行區(qū)域的末端之間沒有代碼，所以不需要多個(gè)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

?

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

Compiler Optimizations for OpenMP

屬性傳播

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

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

缺少指針捕獲

訪問行為（只讀，只寫）

缺少可被訪問者調(diào)用的別名指針

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

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

?

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

?

以下代碼為編譯器前端為源代碼產(chǎn)生的偽C風(fēng)格表示：

?

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ū)域內(nèi)使用的冗長、易錯(cuò)的分類。筆者根據(jù)變量的實(shí)際使用情況對變量分類進(jìn)行轉(zhuǎn)換：

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

Firstprivate：一個(gè)私有變量，但是使用并行域之前的值進(jìn)行初始化。

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

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

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

并行域內(nèi)每個(gè)變量使用之前，都在并行域內(nèi)賦值過；

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

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

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

并行域擴(kuò)張

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

?

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)和兩個(gè)并行域之間不存在依賴，為了降低fook和join的成本并改進(jìn)程序內(nèi)分析，擴(kuò)展了相鄰的并行程序：

?

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;
}

?

為了進(jìn)一步減少開銷，擴(kuò)展并行域也可以對串行構(gòu)造展開，這只有在串行結(jié)構(gòu)能得到適應(yīng)的保護(hù)以及不會(huì)干擾并行語義的情況下進(jìn)行。不過需要注意的是，以下優(yōu)化代碼會(huì)增加一個(gè)新的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)化

串行代碼和并行代碼部分之間的運(yùn)行時(shí)庫間接性不僅禁止信息傳輸，也禁止代碼運(yùn)動(dòng)。運(yùn)行時(shí)函數(shù)調(diào)用的參數(shù)是在串行部分和并行部分之間通信的變量。這些變量是由前端根據(jù)代碼位置和捕獲語義確定的。

筆者提出的方法將執(zhí)行常量傳播，按值而不是按引用來傳遞參數(shù)，盡量減少要傳遞的變量的數(shù)量，將變量提出循環(huán)和并行區(qū)域。對優(yōu)化前的如下代碼，希望在通信時(shí)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?

	?

	?

	　審核編輯：湯梓紅