一種具有重排通信的數(shù)據(jù)分布策略

摘要：主要討論了一種適用于分布和共享內(nèi)存的循環(huán)級的數(shù)據(jù)分布策略。該方法支持由數(shù)據(jù)重排而引起的通信。

關(guān)鍵詞：高性能并行計算機(jī)； 自動并行編譯； 數(shù)據(jù)分布； 計算劃分

中圖分類號：TP314文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2007)07－0019－03

并行處理的思想幾乎是隨著計算機(jī)的誕生而誕生的。并行處理技術(shù)一直是人們提高計算能力的一個重要手段。在應(yīng)用并行計算機(jī)時，人們總是希望有一個具有自動并行化功能的并行編譯系統(tǒng)[1]來自動發(fā)掘程序中的并行性，從而使串行程序能自動轉(zhuǎn)換為并行程序。并行程序編譯器是一個可以將串行程序自動轉(zhuǎn)換為等價并行程序的編譯器，然后再由并行語言的系統(tǒng)編譯器將轉(zhuǎn)換出來的并行程序編譯為機(jī)器碼在并行機(jī)器上予以執(zhí)行。雖然并行化編譯技術(shù)有一定的局限性，但它仍然是并行計算機(jī)系統(tǒng)中最重要的程序開發(fā)工具之一。提高并行化編譯方法對充分利用并行機(jī)資源和提高并行機(jī)效率起著十分重要的作用。基于共享內(nèi)存的自動并行編譯技術(shù)已經(jīng)比較成熟；基于分布內(nèi)存的并行編譯技術(shù)由于數(shù)據(jù)劃分問題還存在著很多困難。本文重點針對分布內(nèi)存體系結(jié)構(gòu)中的數(shù)據(jù)分布及優(yōu)化技術(shù)進(jìn)行了討論。

在分布存儲模式下，對單一循環(huán)的最大限度并行化和本地化[2]的技術(shù)已經(jīng)比較成熟，而如何對多循環(huán)進(jìn)行最優(yōu)的并行化和本地化則是一個需要解決的問題。Kennedy和Kremer表明尋找最佳的數(shù)據(jù)分布模式的問題是NP完全問題[3]，但研究者針對特定的程序模式提出了許多數(shù)據(jù)分布方案。對于高性能并行計算機(jī)而言，如何找到一種好的計算和數(shù)據(jù)劃分，對數(shù)據(jù)和計算進(jìn)行合理劃分，增強(qiáng)數(shù)據(jù)本地化，減少處理器間的通信是提高其并行性能的關(guān)鍵。但在數(shù)據(jù)劃分過程中，重排通信有時不可避免，如何進(jìn)行合理的數(shù)據(jù)和計算劃分以減少通信并最大限度地利用程序的并行性，是并行編譯中的一個重要問題。

1具有完全一致數(shù)據(jù)分布的數(shù)據(jù)和計算的劃分方法

在分布存儲的機(jī)器上，循環(huán)級并行的并行性是通過循環(huán)嵌套迭代空間的分解來實現(xiàn)的。過程內(nèi)一致性數(shù)據(jù)分布是指在整個過程中數(shù)組的分布方式唯一，即無數(shù)據(jù)重排。

在過程內(nèi)求解具有一致性數(shù)據(jù)分布的數(shù)據(jù)和計算劃分[4]過程中，首先要定義三個向量空間，即循環(huán)迭代空間L、數(shù)組下標(biāo)空間A、處理器空間P；然后基于以上三個向量空間建立一組滿足分解條件的仿射關(guān)系方程式；最后通過解方程來找到滿足條件的數(shù)據(jù)劃分和計算分解。有解則存在具有過程內(nèi)完全一致的數(shù)據(jù)分布，使得程序能夠并行執(zhí)行；無解則程序只能串行執(zhí)行。

在上述三個定義中，將計算和數(shù)據(jù)劃分的線性部分用線性矩陣C、D表示，劃分的偏移部分用常向量 δ、γ表示。

若數(shù)組元素和循環(huán)迭代滿足上述方程[5]關(guān)系，則這種劃分是一種無重組無流水通信的劃分，這種分解稱為線性分解。數(shù)據(jù)分布方式是一種過程內(nèi)具有完全一致數(shù)據(jù)分布的數(shù)據(jù)劃分。這種分解方法是本文進(jìn)一步分析具有數(shù)據(jù)重排的數(shù)據(jù)和計算劃分方法的基礎(chǔ)。

2具有數(shù)據(jù)重排的數(shù)據(jù)和計算劃分方法

數(shù)據(jù)和計算分解算法[6]是以中粒度循環(huán)級并行為基礎(chǔ)進(jìn)行的。在對程序進(jìn)行分析時，首先要分析過程內(nèi)的數(shù)組是否存在一致性劃分，即數(shù)組在過程內(nèi)有唯一分布且不存在數(shù)組重排通信。數(shù)據(jù)一致性分解雖然可以最大限度地減少由重排引起的通信，但由于很多程序中數(shù)組找不到一致性分布方式，不能并行執(zhí)行，并行效率低，使用的程序范圍很小，實際應(yīng)用中價值小。能不能設(shè)計一種算法綜合考慮通信開銷和并行效率兩方面因素，在進(jìn)行數(shù)據(jù)和計算分解時允許存在一定的數(shù)據(jù)重排通信，即數(shù)組在過程內(nèi)可以有多種分布方式。程序執(zhí)行時，當(dāng)分布方式發(fā)生變化，數(shù)組則進(jìn)行一次重排通信，即在算法實現(xiàn)中綜合考慮通信開銷與并行度之間的關(guān)系，使得算法所處理的程序能在有一定通信開銷的情況下并行執(zhí)行，從而使能處理的程序范圍增加。

允許數(shù)據(jù)重排的劃分方法是指數(shù)據(jù)的分布方式在各個循環(huán)嵌套之間是可變的，重排劃分實現(xiàn)的基礎(chǔ)是數(shù)據(jù)一致性分解算法。在允許重排的劃分中，首先將根據(jù)數(shù)組和循環(huán)嵌套之間的關(guān)系建立通信圖。通信圖中的頂點向量表示循環(huán)嵌套；邊表示兩個循環(huán)嵌套之間是否有數(shù)組可達(dá)。有數(shù)據(jù)可達(dá)則存在一條邊；否則不存在邊。邊的權(quán)值為數(shù)組可達(dá)的通信開銷。

2．1通信圖G＝（V，E）的建立

圖G的頂點集V：V中的任一頂點表示過程內(nèi)程序具有一級或多級并行性的可并行的循環(huán)嵌套。

邊集E（無向）：若在循環(huán)嵌套u(yù)與循環(huán)嵌套v之間有數(shù)組可達(dá)，則在循環(huán)嵌套u(yù)與循環(huán)嵌套v之間存在一條邊（u，v）（即使u、v之間存在多個數(shù)組可達(dá)，也僅用一條邊表示）。邊的權(quán)值w(u，v)表示數(shù)組從循環(huán)嵌套u(yù)到循環(huán)嵌套v所需的最大通信開銷。計算公式為

根據(jù)例1建立的通信圖如圖1所示。進(jìn)行允許數(shù)據(jù)重排的劃分時，通信圖中的頂點向量根據(jù)數(shù)據(jù)分布的變化劃分為不同的分解區(qū)域。在每個分解區(qū)域中數(shù)據(jù)的分布方式不變化，即具有一致性劃分；在分解區(qū)域之間數(shù)據(jù)的分布方式是變化的，即存在允許數(shù)據(jù)重排的劃分。

在動態(tài)劃分算法中，為了便于解決問題，首先將圖1所示的通信圖擴(kuò)充為如圖2所示的完整的層次結(jié)構(gòu)樹型圖。圖中將增加頂點向量來表示最外層的串行循環(huán)，并在層次之間增加一些邊將圖擴(kuò)充為樹型結(jié)構(gòu)。

2．2動態(tài)分解算法思想

在動態(tài)算法中，將通信圖中每一個頂點作為一個分解區(qū)域，從一個頂點出發(fā)使用貪心法將此頂點所連的邊中具有最大權(quán)值的邊所對應(yīng)的頂點向量試圖合并到一個分解區(qū)域中。經(jīng)計算，若數(shù)組存在一致性分解，則兩個頂點屬于一個分解區(qū)域，可以合并；否則，兩個頂點分別屬于兩個不同的分解區(qū)域，不能合并。由此減少這兩個頂點向量所表示的循環(huán)嵌套之間發(fā)生數(shù)據(jù)重排的可能性。算法通過自底向上的順序，使得通信盡可能發(fā)生在循環(huán)嵌套的最外層。在循環(huán)嵌套的每一層，邊值按降序排列，對于每一條邊（u，v)，算法試圖將兩個頂點u、v合并到一個分解區(qū)域。每合并一個點，將重新計算數(shù)據(jù)劃分的通信開銷。若小于合并前，則進(jìn)行合并，將u、v并入一個分解區(qū)域；否則，不進(jìn)行合并，u、v分別在不同的分解區(qū)域，沿此邊進(jìn)行數(shù)據(jù)重排。此算法中，貪心的開始節(jié)點是由最下層的通信量最大邊的葉子節(jié)點開始合并。若通信量相同，則從最下層的第一個葉子節(jié)點開始合并，先同層貪心，再由下向上。這符合本文進(jìn)行并行時使并行盡可能發(fā)生在最外層的粗粒度并行的思想。

對例1根據(jù)上面所講的算法思想進(jìn)行動態(tài)分解。首先根據(jù)程序建立如圖1所示的通信圖，根據(jù)式（2）可計算出各條邊的通信量；再將圖補(bǔ)充為完整的樹型層次圖（圖2）。根據(jù)動態(tài)分解算法思想，從最內(nèi)層的通信量最大的邊的葉子節(jié)點開始使用貪心法合并。如果合并完數(shù)據(jù)分布不變，則合并成功；否則，不能合并，兩個節(jié)點分別處于不同的分解區(qū)域。合并后的通信圖如圖3所示。節(jié)點1、2．1屬于同一劃分區(qū)，節(jié)點2．2與2．3屬于另一分解區(qū)域；在兩個分解區(qū)域之間進(jìn)行數(shù)據(jù)重排通信。

3結(jié)束語

在自動并行編譯算法中，如何最大限度地發(fā)現(xiàn)程序的并行性，提高串行程序并行化的效率，一直是自動并行化工作中所需解決的難點問題。本文主要闡述了在分布式存儲環(huán)境的并行化編譯中數(shù)據(jù)和計算的劃分算法。基于該算法實現(xiàn)的并行化編譯器能夠自動對串行代碼進(jìn)行數(shù)據(jù)一致性和允許數(shù)據(jù)重排通信的分解，并在后端代碼生成部分根據(jù)已得到的數(shù)據(jù)和計算劃分來將數(shù)據(jù)和計算分到不同的處理器中執(zhí)行。代碼實現(xiàn)中的并行編譯平臺基礎(chǔ)是基于斯坦福大學(xué)的SUIF[7]。通過對ppopp95和NAS測試程序測試，程序并行執(zhí)行結(jié)果與串行執(zhí)行結(jié)果一致，但并行執(zhí)行效率還有待于進(jìn)一步提高。

參考文獻(xiàn)：

[1]沈志宇，胡子昂，廖湘科，等.并行編譯方法[M].北京:國防工業(yè)出版社，2000.

[2]KENNEDY K， MCKINLEY K S. Optimization for parallelism and data locality: proc.of the 1992 ACM International Conference on Supercomputing[C].[S.l.]:[s.n.]， 1992:323－334.

[3]KENNEDY K， KREMER U. Automatic data layout for high perfor－mance Fortran: proc.of Supercomputing’95[C]. San Diego:[s.n.]， 1995.

[4]董春麗，韓林，張平，等.自動計算分解與數(shù)據(jù)劃分算法研究[J].微計算機(jī)信息，2005(33):195－197.

[5]ANDERSON J M， LAM M S. Global optimizations for parallelism and locality on scalable parallel machines: proc.of the ACM SIGPLAN’93 Conference on Programming Language Design and Implementation[C].[S.l.]:[s.n.]， 1993:112－125.

[6]ANDERSON J M， LAM M S. Global optimizations for parallelism and locality on scalable parallel machines: proc.of the ACM SIGPLAN’93 Conference on Programming Language Design and Implementation[C].[S.l.]:[s.n.]， 1993:112－125.

[7]Stanford Compiler Group. SUIF compiler system version 1.0[G]. US:Standford University， 1994.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”