數據驅動的任務圖執行中并發構圖方法

王 松，花 嶸，孟現粉，郭聰聰，傅 游

(山東科技大學 計算機科學與工程學院，山東 青島 266590)

0 引 言

目前，已有的結構化網格應用的編程框架主要有deal.II[1]、libMesh[2]、Chombo[3]等。這些框架針對分布主存的計算系統，在通信、負載平衡等各個方面做了大量的設計和改進，但是面對結構多樣、存儲層次復雜的多核體系結構并沒有提供有效的解決方案[4]。

為了挖掘網格應用在多核平臺上的任務圖并行潛力，中國科學院計算技術研究所設計并開發了AceMesh任務調度系統作為運行時庫[5]，以支持網格應用基于數據驅動的任務圖并行，但該系統的任務圖構建是在并行執行前一次性完成，隨后在構建的任務圖基礎上進行任務的調度、執行。在超大規模計算任務的情況下，構圖時間開銷占到整個程序執行時間的30%左右，并隨著計算線程數的增加而增大。

本文以AceMesh任務調度系統為基礎，提出了并發構圖方法，優化了整個并行化調度執行過程，然后在多核平臺上對案例進行大規模數據集測試，對比了并發構圖和原有構圖方案的性能，驗證了并發構圖方法的性能。

1 AceMesh任務調度系統構圖過程分析

調用AceMesh并行化程序時，程序中可有向無環圖(directed acyclic graph，DAG)并行化的區域必須是一個無嵌套的單入單出的結構化代碼段[6,7]。AceMesh最初設計為單線程執行，在遇到DAG并行區域后通過線程初始化程序構造一個以它為主線程的線程池[8]，該線程池中的所有線程共享DAG并行區域中的所有任務。

AceMesh任務調度主要分為依次執行的兩個階段：DAG圖構建階段和執行階段。本文的研究對象集中在DAG圖構建階段。

DAG圖構建包括任務構造和任務注冊。任務構造是將用戶代碼中的數據訪問區間進行分割，并將因空間分割而帶來的與通信相關的鄰接關系、讀寫信息、變量地址等封裝成為可執行任務[9,10]。而任務注冊是為可執行任務分配內存空間，建立當前注冊任務與已注冊任務之間的邏輯依賴關系，并對沒有前驅和沒有后繼的任務進行分別記錄，將一個空任務作為所有無后繼任務的垂直后繼，以便于任務圖的調度執行和終止檢查[11,12]。

DAG圖構建階段利用一個哈希表(圖1)來記錄地址信息。哈希表的讀寫信息中的r-tasks記錄一組對該地址的最近讀任務，而w_task記錄對該地址的最后一個寫任務。若代碼中被訪問的某一數據地址不在哈希表中，需在表中為其增加一個新表項，并記錄讀寫信息；若數據地址已在哈希表中，則按照對該地址的讀、寫操作對其讀寫信息進行更新。

圖1 哈希表結構

哈希表中某一地址項的讀寫信息隨著對該地址的讀、寫操作而不斷變化。任務之間的依賴關系也由對同一地址的新注冊任務和已有注冊任務讀寫操作的相關性而確定。

已經記錄的沒有前驅的任務會被優先調度執行。在執行過程中，其它任務會依據其前驅任務的執行情況而被調度執行。當空任務的引用計數隨著前驅任務的執行遞減為零時表示DAG圖全部執行完成，哈希表中的信息也將會被刪除[13]。

2 任務圖規模決定因素和并發構圖性能分析

根據DAG圖構建過程分析，DAG圖的規模由以下3個因素決定：

(1)迭代次數。迭代次數的增加會使DAG圖的層次數增加，整個任務圖的任務數也隨之增加；

(2)數據規模。數據規模的擴大會使每一層循環的任務數增加，在分塊尺寸固定的情況下，數據規模越大，劃分的任務數越多；

(3)分塊尺寸。分塊尺寸指劃分后的數據塊大小，塊數與任務數相對應。分塊尺寸越小，任務數越大。

在實際測試中，任務圖的規模往往較大。以Chombo中AMRPoisson為例，其一個進程內就有數以百萬計的任務。

串行構圖的調度系統的程序執行時間為

To=Tg+Texe

(1)

其中，To表示程序總的執行時間，Tg表示構圖時間，Texe表示圖執行時間。

并發構圖的調度系統的程序執行時間為

(2)

其中，Tp表示并發構圖后程序的總執行時間，N表示流水段數。

當任務規模不變時，通過并發構圖隱藏的時間為

(3)

則r表示并發構圖相對于串行構圖總時間的性能提升率為

(4)

Tg越大則r越小，即，構圖時間越大，性能提升率越高。

3 數據驅動的任務圖并行中并發構圖方法

并發構圖是指在構圖的同時進行圖執行。開始調用AceMesh時初始化計算線程，主線程和執行線程會同時運行。通過建立“生產者-消費者”之間的數據流動關系，則不需要增加顯式通信，兩者可以并發執行。并發構圖改變了任務調度執行的時機，不必等待DAG圖全部構建完成，在構圖過程中即可分批調度任務執行。在并發構圖的過程中，新的任務不斷地生成，同時也有任務不斷地被執行，執行完成的任務不再有任何數據依賴，任務間數據依賴的建立需要適應隨時有任務被執行完成的情況。為此，本文提出了一種哈希表維護策略。

3.1 并發構圖無前驅任務的隨時派生

在任務注冊階段，需在一個列表中記錄所有的一級就緒任務，即無前驅的任務。構圖完成后，主線程對一級就緒任務進行派生操作，由線程調度器自動進行圖執行。

串行構圖時，已經記錄了所有需要發起執行的任務。而并發構圖中，隨時會有任務結束，一些新注冊的任務因為沒有檢測到前驅，而成為無前驅的任務。因此，在并發構圖中，必須隨時處理新生成的、無前驅的任務。解決方法就是在任務注冊階段，隨時派生新生成的、無前驅的任務。

3.2 并發構圖下的哈希表維護

在執行流程為依次進行的情況下，系統需要記錄對于同一地址的最近讀寫信息，才能進行動態的依賴分析。為提高依賴測試效率，對每一個必要的變量地址維護一個哈希表項。通過搜索哈希表中的表項內容，可以建立與前驅任務之間的依賴關系。當某個任務需建立依賴關系時，所有前驅任務都未執行，從而那些任務指針都未被釋放，哈希表項中的任務指針都可訪問。

由于并發構圖會出現某個任務在注冊的同時，有部分前驅任務已執行完成或正在執行的情況，其中已完成的任務在哈希表中隨即被釋放，哈希表項中的對應任務指針不可訪問。此時注冊的任務與已經完成的前驅任務之間不應建立依賴關系，需要對哈希表進行維護。

延遲釋放是維護哈希表的基本思路，按照時機，又分為最晚釋放和最早釋放兩種策略。最晚釋放是指被執行完的任務并不立即釋放，而是拖延到整個程序結束再統一釋放，此策略對存儲資源的浪費嚴重。而最早釋放實質上是一種需求驅動的釋放策略，本文采用該策略進行任務釋放。

實際上如果某個任務一直不被釋放，則會一直保留在哈希表中，并隨著應用的執行變化而改變其引用計數值：在并發構圖-執行時，隨著任務引用的增加，其引用計數逐漸從0上升到某正數；隨著該任務引用數的減少，其引用計數降低到某正數直至0，或隨引用數穩定而固定在一個值，該過程不一定是單調的如圖2所示。

圖2 任務引用計數變化情況

某個任務進入哈希表后，直到DAG圖被執行完之前，其任務指針始終存在于哈希表的某些項中。

3.3 需求驅動的任務延遲釋放策略

需求驅動的任務延遲釋放策略將根據任務在哈希表中的引用計數決定何時釋放該任務，其主要思想是：若某任務執行結束時，檢測到引用計數為0，則釋放該任務；一直沒有釋放的任務，會在DAG圖執行完成后統一釋放。

與一個任務相關的前驅任務可能有多個，為了判斷哈希表中的某項是最后一個與該任務相關的任務項，給每個任務增加了兩個參數：任務的判斷狀態finished和任務在哈希表中的引用計數refcnt4hash。在多線程的環境下，注冊線程和執行線程可能會訪問同一個任務，并且任務的狀態和引用計數隨時間發生變化，需要保證轉換動作的原子性，以保證程序的正確性和線程安全性。

定義任務的狀態集Q={未結束，已結束，等待釋放，需釋放，已釋放}，初始化狀態為“未結束”，終止狀態為“已釋放”；定義事件集δ={refcnt4hash更新，調度器執行，調度器發現refcnt4hash≠0，調度器發現refcnt4hash=0，注冊代碼發現refcnt4hash=0，釋放，DAG結束釋放}。

任務注冊代碼和線程執行代碼共同維護任務的狀態。任務注冊時，設定任務的finished為false，設refcnt4hash為零。根據讀取的任務t的狀態來決定是否建立t與后繼的依賴關系：若t為“未結束”，則可建立依賴關系，若t為“結束”，則不建立依賴關系。線程在執行完任務t后，設置任務t的finished為true，此時若refcnt4hash=0，則立即釋放任務t；若refcnt4hash≠0，則只有在為一個新注冊任務建立依賴關系并檢測到有依賴關系的某個前驅任務的refcnt4hash=0時，才將該任務立即釋放。任務的狀態轉換過程如圖3所示。

圖3 并發構圖情況下任務的狀態轉換

綜上，需求驅動釋放是根據任務在哈希表中的計數情況，適時釋放執行完成的任務。當任務執行完成后不再與后繼任務有依賴關系，不需要再對該任務進行任何操作時，釋放占用的內存空間，避免內存資源的浪費。對程序結束后仍然存在于哈希表中的任務進行統一釋放，避免內存泄漏。

3.4 并發構圖的安全終止檢查方案

并發構圖情況下，做終止檢查時，需及時刪除無后繼任務列表中已執行完成的任務指針，否則會出現內存浪費和DAG圖死循環。

為解決這個問題，本文設計了基于無后繼任務收集的即時終止方案，包括3個過程：①獲得所有無后繼任務的列表；②過濾已經執行完成的無后繼任務，即將已完成的任務從列表中刪除；③為列表中剩余的每個任務追加同一個空任務。

在建立依賴關系時已經得到了所有無后繼的任務，即最后一層的任務，所有無后繼任務一定是最晚釋放的任務，也是最后進入哈希表的任務，可以通過任務指針被訪問到。

當空任務的refcnt4hash為0時，DAG圖全部執行完畢。

4 實驗結果和評價

本節對并發構圖策略下多線程執行的總時間進行測試，并與串行構圖的情況進行比較。

本文選用曙光I950r-G作為測試平臺，該平臺操作系統為Red Hat Enterprise Linux 6.3，操作系統內核版本為2.6.32.279，TBB版本為4.1。測試環境中，采用了Intel的icc 13.1.0作為C/C++的編譯器。測試程序為無patch的3d7p-stencil迭代計算。

無patch的3d7p-stencil的計算原理為

Bx,y,z(t+1)=αAx,y,z(t)+β(Ax-1,y,z(t)+Ax+1,y,z(t)+
Ax,y-1,z(t)+Ax,y+1,z(t)+Ax,y,z-1(t)+Ax,y,z+1(t))

(5)

B數組t+1時刻的 (x,y,z) 點數值取決于A數組t時刻的 (x,y,z)、 (x-1,y,z)、 (x+1,y,z)、 (x,y-1,z)、(x,y+1,z)、 (x,y,z-1)、 (x,y,z+1) 共7點的數值。

3d7p stencil計算的計算區域是256*256*256的三維立體空間，共迭代2000次，采用4×4二維分塊。3d7p并發構圖相對于串行構圖的總時間對比如圖4所示。

圖4 3d7p并發構圖與串行構圖性能對比

由表1中的數據和圖4中的性能對比結果表明，圖的執行時間與串行構圖執行總時間非常接近，即圖執行過程在總體執行過程中占據了很大的比例。同時，圖的注冊時間也相對穩定。可以通過邊構圖邊執行的策略使性能得到一定程度的提高。

表1 3d7p兩階段執行模式下與并發構圖性能對比

由表1中的數據表明，并發構圖與串行構圖相比，在2、4、8、16、32線程情況下性能分別提升了2%、6%、12%、22%、30%；在2、4、8、16、32線程情況下，并發構圖相對于串行構圖總時間分別隱藏了4.824 s、7.331 s、8.911 s、12.850 s、13.313 s；在2、4、8、16、32線程情況下，圖構建時間的性能提升分別為45%、66%、79%、85%、81%。

可見，并發構圖方法下程序執行的總時間與串行構圖執行總時間相比，不同線程數下有不同程度的性能提升，線程數越大，性能提升越明顯。

5 結束語

AceMesh任務調度系統的開發，降低了結構化網格應用并行化的難度，同時提升了執行效率。由于采用了兩階段執行的方案，構圖階段占用了大量的執行時間。

本文針對于構圖時間所占總時間比例大的問題，提出了并發構圖的方案，隱藏了任務圖執行中構圖時間，優化了AceMesh的調度執行過程。還對哈希表的維護策略、任務調度時機、任務圖終止檢查、任務釋放等構圖階段的關鍵環節進行了優化，并通過算例的大規模數據集測試驗證了并發構圖方法的性能。

[1]Bangerth W,Hartmann R,Kanschat G.Deal.II—A general-purpose object-oriented finite element library[J].ACM Tran-sactions on Mathematical Software,2007,33(4):467-473.

[2]Kirk B S,Peterson J W,Stogner R H,et al.libMesh:A C++ library for parallel adaptive mesh refinement/coarsening simulations[J].Engineering with Computers,2006,22(3-4):237-254.

[3]Nordén M,Holmgren S,Thuné M.OpenMP versus MPI for PDE solvers based on regular sparse numerical operators[C]//International Conference on Computational Science.Springer Berlin Heidelberg,2002:681-690.

[4]Meng Q,Luitjens J,Berzins M.Dynamic task scheduling for the Uintah framework[C]//IEEE Workshop on Many-Task Computing on Grids and Supercomputers.IEEE,2010:1-10.

[5]HOU Xionghui.Research on task scheduling techniques for optimizing data reuse in grid applications[D].Beijing:University of Chinese Academy of Sciences,2014(in Chinese).[侯雄輝.網格應用中優化數據重用的任務調度技術研究[D].北京:中國科學院大學,2014.]

[6]WANG Lei,CUI Huimin,CHEN Li,et al.Research and development task parallel programming models[J].Journal of Software,2013,24(1):77-90(in Chinese).[王蕾,崔慧敏,陳莉,等.任務并行編程模型研究與進展[J].軟件學報,2013,24(1):77-90.]

[7]Nguyen T,Cicotti P,Bylaska E,et al.Bamboo:Translating MPI applications to a latency-tolerant,data-driven form[C]//Proceedings of the International Conference on High Performance Computing,Networking,Storage and Analysis.IEEE Computer Society Press,2012.

[8]Acar U A,Chargueraud A,Rainey M.Scheduling parallel programs by work stealing with private deques[J].ACM Sigplan Notices,2013,48(8):219-228.

[9]Williams S,Kalamkar D D,Singh A,et al.Optimization of geometric multigrid for emerging multi-and manycore processors[C]//Proceedings of the International Conference on High Performance Computing,Networking,Storage and Analysis.IEEE Computer Society Press,2012:96.

[10]Chen L,Huo W,Long X J,et al.Parallel programming languages on multi-core and many-core architectures[J].Information Technology Letter,2012,10(1):23-40.

[11]Lee I,Angelina T,Boyd-Wickizer S,et al.Using memory mapping to support cactus stacks in work-stealing runtime systems[C]//Proceedings of the 19th International Conference on Parllel Architectures and Compilation Techniques.ACM,2010:411-420.

[12]Olivier S L,Porterfield A K,Wheeler K B,et al.Scheduling task parallelism on multi-socket multicore systems[C]//Proceedings of the 1st International Workshop on Runtime and Operating Systems for Supercomputers.ACM,2011:49-56.

[13]Cao Y J,Qian D P,Wei-Guo W U,et al.Adaptive scheduling algorithm based on dynamic core-resource partitions for many-core processor systems[J].Journal of Software,2012,712(2):240-252.