Fork-join parallelism 是一種組織並行程序的方式,它特別適合於分而治之的算法,比如歸並排序。 通過一組語言擴展,例如由 OpenMP (比如#pragma omp parallel和#pragma omp parallel等等)和 Cilk Plus(比如cilk_spawn 和 cilk_sync)提供的擴展,GCC和LLVM之類的主流編譯器內均可支持fork-join parallelism。這些編譯器前端處理這些語言擴展到“較低層”並行結構到更原始的表示,然後轉化成IR。例如,以下代碼片段使用Cilk cilk_for擴展使之可以並行運行該循環的每次迭代:
__attribute__((const)) double norm(const double *A, int n); void normalize(double *restrict out, const double *restrict in, int n) { cilk_for (int i = 0; i < n; ++i) out[i] = in[i] / norm(in, n); } }
這種方式的其中一個缺點是,雖然編譯器中端再也看不到循環了,但運行期調用是不透明的,它提取自己函數內的代碼塊傳入庫函數,該庫函數處理大量生成的循環迭代並隨後同步。這實際上妨礙了中端針對循環在IR層進行的各類優化,比如循環不變式代碼調整、調度等。
Schardl、Moses和 Leierson的工作是通過一個擴展的IR直接將fork-join模型放入中端,這使之前需要由並行處理添加額外代碼的代碼可以應用所有各類優化策略了。這種方式本身並不新穎,幾個特殊的IR已經特別設計以表示程序內的並行了,然而:
……在主流編譯器中使用單獨的IR一直以來都受非議,因為策劃、開發和維護這個額外的IR到像編譯器已有的串行IR同樣的標准需要付出相當大的工作量。
關鍵是麻省理工學院的三位研究人員已經找到了擴展LLVM的IR的方法,即通過保留它們的串行語言去表示邏輯任務並行。他們新的IR被稱為Tapir,代表並行任務不對稱,這表示並行任務必須在執行流程能被同步之前率先完成,從而使LLVM之類的串行中端可以去高效地優化並行代碼,這些研究人員們說。
Tapir通過增加三個新命令擴展LLVM的IR:detach、reattach和sync。雖然detach大致相當於像fork一樣的抽象,但是reattach 和 sync所代表的與join稍有不同。由於目的在於實現可串行化這一需求,所以並行計算必須確保分離鎖在分支續延之前執行完成。因此,雖然detach和reattach表示一個並行任務的開發和結束,但是同步任務的同步是在其並行上下文內發生的。
為了評估他們這些新方法的好處,麻省理工學院的研究員們比較了Cilk-enabled LLVM編譯器和Tapir-enabled的LLVM編譯器,用它們同時去編譯一組20個Cilk程序的套件。
在這20個程度中的17個,使用新IR的編譯器產出了更高效的軟件,其中三分之一提升了10%到25%。而新編譯器所產出的更低效率的軟件,其下降幅度也僅低於2%。
在GitHub上可以獲得Tapir,可運行以下命令進行構建:
git clone --recursive https://github.com/wsmoses/Tapir-Meta.git cd Tapir-Meta/ ./build.sh source ./setup-env.sh
查看英文原文:MIT Extended LLVM IR to Enable Better Optimization of Parallel Programs