神威平臺上AceMesh編程模型的構圖優(yōu)化

葉雨曦，傅 游，梁建國，孟現粉，劉 穎，花 嶸

(1.山東科技大學 計算機科學與工程學院，山東 青島 266590; 2.中科寒武紀科技股份有限公司, 北京 100191； 3. 中國科學院計算技術研究所，北京 100190)

任務并行編程模型把任務作為并行的基本單位，為編程人員提供任務劃分和任務同步接口。編程人員需要考慮如何對應用程序進行合理的任務劃分，而任務具體的要在哪個物理核上執(zhí)行以及如何實現任務之間的同步都由運行時系統(tǒng)完成。任務并行編程模型可看作底層體系結構和上層程序應用之間的橋梁，向上隱藏并行處理的細節(jié)，提高編程層次，簡化并行編程；向下充分利用硬件資源，高效正確地執(zhí)行并行程序[1]。支持任務并行調度的并行編程模型主要有MIT的Cilk[2]/Cilk++[3]、Intel的Threading Building Blocks(TBB)[4]、BSC的OmpSs[5]、微軟的Task Parallel Library(TPL)[6]等。

中國科學院計算技術研究所并行編譯組提出了一種面向網格應用，以數據為中心，應用于多核、眾核平臺上的任務并行編程模型AceMesh[7-10]。AceMesh主要包括編譯器和任務調度系統(tǒng)。AceMesh編譯器作為一個源到源編譯框架[5]，根據平臺特性將帶指導語句的程序代碼自動生成指定平臺的并行化程序，編程人員只需要關注指導語言和應用本身即可。AceMesh任務調度系統(tǒng)采用基于有向無環(huán)圖[11](directed acyclic graph，DAG)的動態(tài)任務調度，能自動發(fā)掘結構化網格應用中存在的數據驅動的任務圖并行性，其性能較其他的任務并行編程模型優(yōu)越[12-13]。

AceMesh作為數據流驅動的任務并行模型，細粒度的任務劃分會使其構圖開銷顯著增加，降低應用的并行可擴展性。王松等[14]提出了并發(fā)構圖的方法，對AceMesh構圖進行了優(yōu)化，但該方法在訪存、內存申請和任務收集方面存在一定的問題，導致AceMesh構圖過程開銷仍過大。為提高構圖效率，本研究從減少通信開銷、設計內存池和優(yōu)化任務收集策略等角度對AceMesh構圖過程進行優(yōu)化，通過數據測試驗證構圖優(yōu)化的可行性和有效性。

1 “神威·太湖之光”平臺簡介

“神威·太湖之光”[13-15]計算機系統(tǒng)采用“申威26010”異構眾核處理器，芯片工作頻率1.45 GHz，峰值運算速度3.168 TFLOPS，采用了針對該處理器定制的64位申威指令系統(tǒng)，與X86指令系統(tǒng)不兼容。“申威26010”異構眾核處理器架構如圖1所示。

“申威26010”異構眾核處理器集成了4個運算核組，共260個運算核心，核組間支持Cache一致性，通過高速片上網絡相連。每個核組包含1個運算控制核心(management processing element, MPE)即主核、1個運算核心(computing processing elements,CPE)即從核陣列和1個存儲控制器(memory controller,MC)，通過iMC與主存相連。眾核處理器還集成系統(tǒng)接口總線用于連接標準PCIe接口，實現片間直連和互連，管理與維護接口負責系統(tǒng)管理、維護和測試。4個核組和系統(tǒng)接口總線通過群間傳輸網絡實現存儲共享和通信。主核具有兩級片上存儲層次：L1級數據和指令Cache、共享的L2級Cache。1個計算核組中的64個從核共享L2級指令Cache。每個從核具有私有L1級指令Cache和用于數據存儲的LDM空間。應用程序由主核啟動，借助高性能線程庫Athread將計算任務加載到從核執(zhí)行，雙方通過同步接口協(xié)同。

2 AceMesh任務調度系統(tǒng)的構圖過程及其存在的問題

AceMesh任務調度系統(tǒng)的工作機制如圖2所示。用DAG將計算任務之間的依賴關系表達出來的過程稱為構圖，利用構建的DAG分析保持數據原有依賴關系的正確任務執(zhí)行順序，并對任務進行調度和計算的過程，稱為圖執(zhí)行。DAG的構建由主核獨自完成，執(zhí)行由主核和從核共同完成。

圖2 AceMesh任務調度系統(tǒng)工作機制

構圖過程包括兩步：一是數據域的劃分及計算任務封裝。根據代碼訪問數據區(qū)域的不同，將整個數據域劃分成若干個數據區(qū)域。為減少通信量，盡可能把具有依賴關系的數據區(qū)域分配到一個數據塊中，并將數據塊、對該數據塊的操作和需要通信的鄰居節(jié)點封裝成一個計算任務；二是計算任務注冊。為了更好地發(fā)掘緩存中的數據重用性，初始化計算任務的親和性設置，根據最近、可達的數據訪問信息如變量地址、鄰居關系、讀寫信息等，構建正在注冊的計算任務與前驅計算任務間的數據依賴邊，并記錄為后繼任務；將沒有前驅的任務存放在無前驅任務列表need_spawn_tasks中，作為最先調度的任務；查找無后繼任務并將其存放在無后繼任務列表end_tasks中，用于檢查DAG執(zhí)行結束狀態(tài)。

在構建DAG的過程中存在下面3個問題：

1) DAG構建由主核獨立完成，為了在構建完成后喚醒從核，主核需要在主存上維護一個共享變量is_run。主核構建DAG時將is_run賦值為0，構建完成后將is_run賦值為1；處于等待狀態(tài)的從核會訪問is_run的值，若值為1則從核進入工作狀態(tài)，執(zhí)行計算任務。因此主核構建DAG期間所有的從核都在不斷地訪問主存，造成了很大的訪存開銷。

2) 系統(tǒng)使用new()、malloc()等申請分配內存，會調用操作系統(tǒng)的系統(tǒng)調用函數mmap2()，時間開銷大，應盡量減少系統(tǒng)調用的次數。AceMesh任務調度系統(tǒng)中大量地使用動態(tài)數據結構，如任務的繼承類、任務參數和任務后繼列表等，當任務的總數很多時，這些動態(tài)數據結構的分配和釋放造成大量的系統(tǒng)開銷。

3) 無后繼任務列表end_tasks是基于哈希表實現的，用于檢查DAG執(zhí)行結束狀態(tài)。每個新任務注冊后都需要對end_tasks列表執(zhí)行添加和查找操作，每次更新后存在后繼的任務需要從end_tasks列表中刪除。若無后繼任務占比較低，隨著注冊任務數增加，end_tasks列表的修改和查找開銷會變得越來越大。

3 AceMesh任務調度系統(tǒng)的構圖優(yōu)化

AceMesh任務調度系統(tǒng)先構圖后調度，合理高效的構圖方法可以有助于減少線程的等待時間，提高程序的執(zhí)行效率。本節(jié)針對第2節(jié)中AceMesh構圖過程存在的3個問題進行構圖優(yōu)化。

3.1 主、從核通信優(yōu)化

申威26010異構眾核處理器單核組存儲器訪問方式如圖3所示。每個核組的從核可以直接訪問主存和局存，從核訪問主存有gld/gst離散訪存和DMA批量式訪存兩種方式。主核不能直接訪問主存，但是可以通過I/O訪問局存，借助宏h2ldm(elment,penum,cgnum)函數直接對從核LDM變量進行I/O存取操作，其中element是運算核心程序內的局存私有變量，penum是核號，cgnum是核組號。

圖3 單核組存儲器訪問圖

AceMesh任務調度系統(tǒng)中從核訪問共享變量is_run的方式為gld/gst離散訪存。在訪存帶寬方面，gld/gst方式單個核組內的訪存帶寬為1.5 GB/s，DMA方式單個核組內的訪存帶寬為26 GB/s；在延遲方面，gld/gst方式延遲278 cycle；DMA方式延遲29 cycle。可以看出，與gld/gst方式相比，DMA方式帶寬利用率高，延遲小。

但是DMA批量式訪存也存在一定的局限性。圖4所展示的單核組DMA帶寬增長趨勢表明，只有當單次拷貝的數據塊大于256 B而且主存地址256 B對齊時，DMA方式才能有效利用訪存帶寬。另一方面，從核在構圖期間不斷地進行變量的數據傳輸，會占用訪存帶寬。因此DMA方式不是有效的優(yōu)化方式。

圖4 單核組DMA訪存帶寬

為了減少從核訪問主存的帶寬開銷，將主存上的共享變量is_run改為從核LDM私有變量，每個從核維護一個自己的通信變量is_run。如圖5所示，主核構圖完成后，通過h2ldm(is_run,i,cgid)=1訪問每個從核的LDM空間并將私有變量is_run賦值為1。從核判斷自己維護的私有變量is_run的值為1后開始執(zhí)行任務。當任務執(zhí)行完成后，主核再通過h2ldm(is_run,i,cgid)=0通知從核停止任務執(zhí)行，等待下一個任務圖的執(zhí)行。將is_run變量改為從核私有變量減少了從核訪問主存的次數，有效降低了構圖過程中的訪存開銷。

圖5 優(yōu)化后的主、從核通信流程

3.2 內存池優(yōu)化

AceMesh允許用戶為一個應用程序設置多個并行區(qū)，隨著應用計算規(guī)模的增加，單個并行區(qū)內提交的任務數也不斷增加，這些并行任務提交時申請的內存空間將在并行區(qū)結束后釋放。頻繁的內存申請和釋放會帶來嚴重的內存碎片問題，同時malloc()和free()函數的使用也會造成很大的時間開銷。

為解決上述問題，引入內存池管理存儲資源。內存池實質上是一種內存分配方式，在真正使用內存之前，通過調用系統(tǒng)內存分配函數預先申請適當大小的內存塊作為備用，之后應用程序對內存的分配和釋放則通過這個內存池來完成。當有新的內存需求時，就從內存池中分出一部分內存塊，若內存塊不夠，需要動態(tài)擴展時，再繼續(xù)申請新的內存塊。

本研究提出一種采用內存池管理內存分配的方法，其內存池的申請和釋放狀態(tài)轉換圖如圖6所示。內存池中可以申請多個內存塊，申請的內存塊中包含可分配的空閑節(jié)點，所有空閑塊由內存池空閑列表管理，若空閑塊被分配出去則將其從表中刪除；若已分配的內存塊被釋放，則將其重新插入到空閑列表的頭部。如果內存塊中的空閑塊不足，則申請新的內存塊。內存池的分配和釋放都是以固定大小的內存塊為單位，不會產生內存碎片，因此可以有效避免內存泄露。

圖6 內存池內存分配狀態(tài)轉換圖

內存池和內存塊的數據結構為：

typedef struct node{

void* data;

struct node* next;

}node;//內存塊

typedef struct MemPool{

void* to; //指向當前空閑塊的尾部

void* from; //指向當前空閑節(jié)點的可用位置

struct node* AllocatedMemNode; //指向內存塊的已分配列表

struct node* FreeMemNode; //指向內存塊的空閑列表

}MemPool;//內存池

根據內存池的工作流程，內存池申請算法如下。

Algorithm 1內存池申請算法輸入:需要使用的內存空間大小data_size,一個內存塊包含的內存節(jié)點數num_node,每個內存節(jié)點的存儲空間大小node_size輸出:內存池變量Mpool1 //內存池初始化2 struct MempoolMpool3 Mpool.AllocatedMemNode = NULL4 Mpool.FreeMemNode = NULL5 //為內存池加入新的內存塊6 byte *new_memory_block = (byte *)malloc(node_size * sizeof(byte))7 do i = 1, num_node8 申請一個新的內存塊node[i]9 node_i.data = new_memory_block + i * node_size10 if (i == 1) then continue11 else 上一個內存塊node[i-1].next指向node[i]12 endif13 end do14 if (Mpool.FreeMemNode) //空閑列表不為空14 then將新內存節(jié)點鏈表加入到FreeMemNode列表15 else{16 Mpool.FreeMemNode = node[1]17 Mpool.from = node[1].data 18 Mpool.to = node[1].data + node_size}19 end if

內存池分配算法如下。

Algorithm 2內存池分配算法輸入:已分配好的內存池變量Mpool,需要申請的內存大小data_size,需要申請空間的指針變量data_point輸出:分配好內存空間的指針data_point1 int node_n, node_size = Mpool.to - Mpool.from2 根據node_size和data_size計算需要分配的節(jié)點數node_n3 void * point = Mpool.FreeMemNode->data4 do i = 1, node_n5 if (Mpool.FreeMemNode == NULL)//當前內存池內沒有空閑節(jié)點6 then 為內存池加入新的內存塊7 endif8 將Mpool.FreeMemNode第一個節(jié)點取出9 在Mpool.AllocatedMemNode加入新分配的節(jié)點10 end do11 data_point = point

從內存池的申請和分配算法中可以看出，只在新的內存節(jié)點申請時用到malloc()函數，內存節(jié)點的分配則是通過傳遞指針和修改鏈表來完成的，減少了malloc()和free()函數的調用次數，從而降低內存申請的時間開銷。

3.3 無后繼任務收集優(yōu)化

無后繼任務列表end_tasks是為了檢測DAG是否執(zhí)行結束而引入的一個任務集，用來記錄應用程序的所有無后繼任務。AceMesh任務調度系統(tǒng)中end_tasks列表的數據結構為unordered_set，利用哈希表實現。哈希表是根據鍵值進行直接訪問的數據結構，通過相應的哈希函數處理關鍵字得到相應的鍵值，鍵值對應著一個特定位置，用該位置來存取相應的信息，能以較快的速度獲取關鍵字的信息，具有可快速查找、刪除和添加的優(yōu)點。在AceMesh構圖機制中，end_tasks列表的收集方法是在每個任務注冊時將其添加到end_tasks，若發(fā)現任務有后繼，再從end_tasks中查找并刪除。

圖7是對航天飛行器應用中部分代碼進行任務劃分后得到的DAG。該部分代碼包含多個循環(huán)計算，通過對循環(huán)的劃分來分配計算任務。每個圓圈代表一個計算任務，圓圈內第一個數字代表并行區(qū)內的循環(huán)的序號，第二個數字代表計算任務在循環(huán)內的序號，每個任務通過箭頭指向其后繼任務，相同顏色的計算任務在同一個計算線程上執(zhí)行。這部分代碼計算的數據訪問很規(guī)則，所以計算任務之間的依賴關系比較簡單，因為計算任務是按照循環(huán)的次序串行提交的，所以該DAG構建時，第一個循環(huán)內的任務(即第一行的任務)首先注冊，并被加入到end_tasks列表中，第二行計算任務注冊時，之前提交的計算任務都被檢測到有后繼任務，end_tasks列表需要將第一個循環(huán)內的任務刪除，第三行計算任務提交后同樣需要刪除第二行計算任務，這就造成了很多不必要的哈希表查找和修改操作。若無后繼任務占比極低，會使得注冊時收集到的任務絕大多數被刪除，導致哈希表相應數據項的操作失去意義，造成不必要的開銷。

圖7 航天飛行器應用規(guī)則部分DAG

對于無后繼任務占比較小的并行區(qū)，通過為用戶提供指定無后繼任務的開關，由用戶直接判斷無后繼任務，從而省去構圖過程中end_tasks列表頻繁修改的開銷。在實現上增加開關SPECIFY_END_TASKS=true(false)和接口acemesh_specify_end_tasks()。如果應用并行區(qū)內無后繼任務占比較小，用戶設置SPECIFY_END_TASKS=true，AceMesh構圖時將不再進行無后繼任務列表end_tasks的收集，由用戶在提交任務時利用接口acemesh_specify_end_tasks() 指定無后繼任務并將其直接放入無后繼任務列表end_tasks中，所有任務提交完成后無后繼任務也收集完畢，避免對end_tasks列表頻繁的插入和刪除操作，提高構圖效率。

4 構圖優(yōu)化測試

航天飛行器應用程序的循環(huán)有6層。外3層循環(huán)為速度空間，內3層循環(huán)為位置空間，外3層循環(huán)在進程級別對程序進行劃分, 本研究只對內3層循環(huán)即位置空間i，j，k的3個維度進行劃分。對航天飛行器應用程序進行分析得到具有代表性的7個計算循環(huán)，每個計算循環(huán)有不同的劃分方向和分塊尺寸，各循環(huán)的劃分方向和分塊尺寸如表1所示。各個循環(huán)在3個維度上的劃分如表1所示。

表1 計算循環(huán)分塊表

將7個計算循環(huán)作為熱點子程序進行性能測試，由于在“神威·太湖之光”平臺上，AceMesh任務調度系統(tǒng)的構圖階段是單線程執(zhí)行的，故無論采用多少計算線程，構圖時間均不變。對各熱點子程序使用執(zhí)行效率最高的線程數，在速度空間32×16×16、位置空間100×19×31、進程網格1×1×1規(guī)模下，對AceMesh任務調度系統(tǒng)的構圖階段測試5次，取5次測試結果的平均值，對比構圖優(yōu)化前后的性能，說明構圖優(yōu)化的效果，如表2所示。

表2中可見，對于不同的熱點程序，構圖優(yōu)化對構圖的性能提升程度不同，但加速比均在4.7以上，其中GaussLegendre的構圖性能表現最好，加速比為7.18。因為AceMesh任務調度系統(tǒng)分為構圖和執(zhí)行兩個依次進行的階段，所以計算線程數對構圖性能無影響。

表2 AceMesh任務調度系統(tǒng)的構圖優(yōu)化性能對比

任務調度系統(tǒng)各優(yōu)化項構圖優(yōu)化貢獻如圖8所示，以優(yōu)化前的構圖作為基準，主、從核通信優(yōu)化、內存池以及無后繼任務收集等優(yōu)化方法對構圖有不同程度的加速貢獻，其中無后繼任務收集優(yōu)化方法的加速貢獻最大，加速比為2.6以上，所有優(yōu)化方法總加速比最高達到8.19。

圖8 AceMesh任務調度系統(tǒng)各優(yōu)化項構圖優(yōu)化加速比

AceMesh任務調度系統(tǒng)構圖優(yōu)化的子程序總性能對比如圖9所示，因為航天飛行器應用的7個子程序的任務數不同，構圖優(yōu)化對7個熱點子程序的總體性能加速表現不同，但均在1.3倍以上，其中GaussLegendre的優(yōu)化加速最好，達到3.13倍；其次是fcta1和fcta2，總性能加速比趨于相同，達到2.6倍以上。

圖9 AceMesh任務調度系統(tǒng)構圖優(yōu)化子程序總性能對比

測試采用“神威·太湖之光”平臺的測試隊列，由于使用權限所致，最大進程數只能為64，運行時間最長為60 min。在速度空間64×64×64，位置空間100×19×31規(guī)模下，測試不同進程數下應用整體性能的提升。并對照神威OpenACC編程語言版本，說明AceMesh任務圖并行化帶來的性能提升，如表3所示。

表3 AceMesh與神威OpenACC版本的航天飛行器應用性能對比

表3數據表明，AceMesh編程語言的DAG并行版本比神威OpenACC的運行效率要高，在不同的進程數下，加速效果都約為OpenACC的1.5倍。究其原因，一是因為亂序執(zhí)行是AceMesh獨有的特性，二是因為AceMesh通過對計算循環(huán)進行多維度的劃分，在保證足夠任務數的同時每個任務有充足的計算量，充分利用訪存帶寬，使得DMA傳輸的效率提高。隨著進程數的增加，AceMesh并行版本和神威OpenACC并行版本的執(zhí)行時間均逐漸減小，在64線程時，運行速度最快，說明AceMesh和神威OpenACC任務并行編程模型都具有良好的擴展性。

5 結論

為提高AceMesh的構圖性能，從主、從核通信優(yōu)化、設計內存池、無后繼任務收集等3個方面對AceMesh的構圖進行優(yōu)化，對航天飛行器應用的7個熱點子程序在“神威·太湖之光”上進行了測試，結果證明優(yōu)化為構圖帶來5倍的性能提升。后兩個方面的優(yōu)化具有普適性，可為所有超算平臺上的優(yōu)化提供參考。以上構圖效率提高的主要原因來自無后繼任務收集的優(yōu)化，進一步可以考慮設計一種更高效的任務收集機制來減少哈希表的查找和修改開銷。