SW26010 眾核任務并行調度系統及其嵌套并行算法應用?

孫 喬,黎雷生,趙海濤,趙 慧,吳長茂

(中國科學院 軟件研究所 并行軟件與計算科學實驗室,北京 100190)

任務并行模式[1,2]是并行程序設計的一種基本設計模式,在并行計算領域中有著廣泛的應用.一個任務是由相關數據及其操作形成的集合[1,3].相互獨立的任務可以同時被分派到不同的處理器得以并行處理,從而使程序獲得較為理想的并行加速比.相對于樸素的數據并行模式,采用任務并行模式可以更高效地并行化諸如快速排序,二叉樹遍歷及凸包計算等一系列具有遞歸結構的算法[4,5].然而在實際應用中,不同任務間往往具有復雜的前驅后繼關系,一些任務還可能需要衍生出其他任務,形成任務嵌套(nested task)[1].因此任務并行程序的正確性不僅依賴于各個任務的正確定義,還依賴于任務間恰當的時序.因此若要全盤考慮上述要素,則任務并行程序的設計和實現會有著相當的難度.從而一個通用的支持任務并行模式的運行時框架[6,7](下稱:任務并行框架)成為程序員開發任務并行程序的必需.

SW26010(申威26010)CPU 是我國自主研發的一款高性能眾核CPU[8].如圖1 所示,一片SW26010 CPU 由4 個CG(core group,核組)構成.每組CG 包括1 個控制核心MPE(management processing unit)和64 個CPE(computing processing element).從本質上講,MPE 是一個通用處理器,負責處理程序的邏輯密集部分和系統資源的控制;眾多CPE 則是一些輕量級計算核心,主要負責加速程序的計算密集部分.64 個CPE 被排布成8×8 陣列,每個CPE 可通過唯一的標識或其在陣列中所處的行(列)號進行索引.每個CPE 有程序可控的64KB 高速LDM(local data memory,本地數據內存)作為其數據緩存.一組CG 中的MPE 和CPE 陣列能夠共享進程的內存空間.除了常規的訪存方式外,單個CPE 與內存間還能通過DMA(direct memory access)機制進行數據塊的高效傳輸.

Fig.1 Architecture of a SW26010 many-core CPU圖1 SW26010 眾核CPU 體系結構

一片SW26010 CPU 的4 組CG 通過片上高速互聯網絡相連,其間實現了緩存一致性協議.但由于每組CG擁有各自臨近的內存空間,因此在常規情況下,一片SW26010 CPU 的4 個CG 需分別運行單獨的進程,以避免延遲較高的遠端內存訪問.運行于SW26010 CPU 的進程由CPE 陣列對計算密集但邏輯簡單的部分進行并行加速處理,從而一系列科學計算類應用能夠得以有效加速.然而隨著計算機應用的日益廣泛,一系列非規整算法也亟待通過并行化得以有效加速.因此本文針對上述情況,面向SW26010 CPU 的單組CG,設計實現任務并行框架SWAN.其對降低SW26010 CPU 的使用難度及擴大平臺的適用性有著重要的現實意義.

本文第1 節將進一步描述對SWAN 的設計實現有著重要影響的目標平臺特性,并針對性地提出SWAN 框架的設計目標.第2 節具體描述SWAN 的靜態結構與和動態行為.第3 節進一步介紹SWAN 框架采用的關鍵技術.第4 節擬通過若干具有代表性的嵌套并行算法對SWAN 的實用性及性能進行測試.第5 節回顧在主流的多(眾)核平臺上常用的諸多任務并行框架,并探討其與SWAN 的區別與聯系.第6 節對本文的工作進行總結.

1 平臺特性

一組CG 的諸多硬件特性對SWAN 框架的設計實現提出了要求.首先,一個CPE 目前只能運行單一線程,無法進行線程切換.因此CPE 上的任務調度環境應當具備上下文切換功能,旨在確保當前任務因依賴關系尚未滿足而掛起導致的CPE 忙等.其次,由于所有CPE 共享統一的內存空間,這雖有利于簡化共享數據結構的設計實現,但若不對共享數據加以適當處理,則會導致大量線程由于對共享數據的爭用而導致的巨額開銷.因此SWAN 框架需對任務池等共享資源進行細粒度劃分以提高SWAN 框架本身的并發性.再次,單個CPE 雖可以通過load/store 指令直接訪問內存單元,但其效率低下.因此為了增大內存吞吐率,CPE 應盡可能地采用DMA 機制傳輸成塊數據.這就意味著SWAN 框架中的關鍵數據結構需有合適的物理結構,能夠通過DMA 進行高效的訪問.最后,SWAN 還需利用各個CPE 的LDM 以緩存任務管理所需的各種信息,以提高任務管理的效率.

在平臺的軟件特性方面,單個CG 的線程控制、DMA 機制等功能通過調用“athread”庫實現.athread庫提供基本的線程發起(“athread_spawn()”)和線程集合(“athread_join()”)接口操縱CPE 陣列.單個CPE 上,athread_get()/athread_put()接口通過DMA 實現數據在LDM 和內存間的交換.另外,單個CPE 上擁有可作用于從核陣列的“取并加一(fetch-and-add)”原子操作.從現有API 上看,目前單個CG 可方便地部署以“Fork-and-Join”方式并行的程序,但對具有嵌套并行特性的算法,平臺尚未向程序員提供更高層的接口及更高級的細粒度線程同步手段,如鎖和信號量等.

綜上所述,在SW26010 上實現通用的支持任務并行的運行時框架,需以現有的并行接口為基礎,采用軟件方式跨越硬件限制并充分利用平臺的各種資源.因此SWAN 框架的設計和實現具有相當的難度.

2 相關工作

雖然SWAN 框架為SW26010 眾核核組定制,結合了諸多平臺的軟硬件特性,但當今國內外在任務并行模式及任務并行框架方面的研究對SWAN 框架的設計與實現有著重要的借鑒意義.

任務并行模式主要應用在 SMP(對稱多處理器)或 NUMA(非對稱多處理器)環境下[1].在這種環境下OpenMP[4,5,9,10]是一套指導性編譯處理標準,用戶能夠通過編譯制導語句方便地對程序實施并行化.OpenMP 標準已被廣泛接受,在學術界及開源社區有著眾多實現,比如OpenUH[11].早先,OpenMP 被廣泛應用于并行化大型科學計算程序中結構規整的循環,但由于在版本3.0 之前,OpenMP 并不支持任務并行,因此其應用范圍受到了極大的制約.在版本3.0 之后,OpenMP 集成了任務并行功能[12],用戶可以通過編譯制導語句方便地實施任務并行及任務嵌套并行.遺憾的是,OpenMP 在當前SW26010 核組上沒有得到有效支持.因此本文中提出的支持任務并行及任務嵌套并行的SWAN 框架能夠有效地拓展SW26010 核組在任務并行領域的應用.于2012 年提出的OpenMP 4.0 標準增加了以任務間依賴有向無環圖為基礎的任務調度策略[13],這亦為SWAN 框架的進一步發展指明了方向.除OpenMP 之外,在當前主流的多核、眾核平臺上還有一些專門支持任務并行的并行編程框架.Cilk[14,15]及Cilk-5[16]是由MIT 于2001 年提出的多核平臺任務并行解決方案.與OpenMP 不同,Cilk 擴展了C語言關鍵字以實現任務并行及任務嵌套并行.Cilk 采用了經典的工作竊取[17]調度策略并對其性能和內存使用行為進行了理論評估.本文結合SW26010 平臺的特性,將工作竊取策略整合于SWAN 框架中,構成任務管控邏輯的核心.相似地,X10[18,19]定義了新的并行語言,能夠使程序員高效地表達程序的并行性.X10 主要面向NUMA 架構,以庫所(place)概念為核心管理程序數據,緩解由平臺訪存不均勻性帶來的程序性能損耗.Intel TBB[20]及Microsoft 推出的TBL[21]以C++語言為基礎,為程序員提供了豐富的并行模板及數據結構.它們的出現標志著任務并行編程模型走入了工業界.但是它們主要面向C++程序,其實現也結合了諸多面向對象特性,因此它們的高效使用需要程序員對C++語言中的模板、泛型等概念有著深刻的理解.

隨著異構平臺的流行,任務并行編程的應用得到了進一步拓展.如Intel 為MIC 協處理器定制的OpenMP 擴展編譯器,能夠通過分載(offload)子句將任務指派到MIC 協處理上予以執行[22].另外,StarPU[23]是一套支持主流異構平臺(如CPU+MIC 和CPU+GPGPU)上的通用任務并行的編程框架.StarPU 需要將任務透明地通過互聯總線映射到協處理器予以計算.由于SW26010 的MPE 與CPE 陣列能夠統一訪存,因此SWAN 框架無需負責任務在不同設備間的來回傳輸.值得一提的是,在典型的SIMD 平臺GPGPU 上,任務并行也日漸受到重視,文獻[24]闡述了如何在GPGPU 平臺上以線程束(warp)為邏輯處理器核心,實現多任務并行的實現機制.由于GPGPU 和SW26010 在處理器架構,內存層次結構和訪存特性上有較大差異,因此在GPGPU 上實現的任務并行框架難以在本文的目標平臺上予以直接應用.

3 SWAN 框架的結構與行為

如圖 2 所示,SWAN 系統由4 個模塊組成,分別是CI(concurrent infrastructure,并發基礎結構)模塊、MC-Modeling(MPE/CPE modeling,MPE/CPE 建模)模塊、QPP(queuing and parallelization policy、排隊及并行策略)模塊和UI(user interface,用戶接口)模塊.其中,CI 模塊與MC-Modeling 模塊描述SWAN 框架的靜態結構,QPP模塊定義SWAN 框架的動態行為,UI 模塊為用戶提供API 以屏蔽底層的并行處理的細節.

Fig.2 Software architecture of SWAN圖2 SWAN 軟件體系結構

3.1 SWAN框架的靜態結構

鑒于當前CPE 陣列缺少靈活的細粒度線程同步機制,CI 模塊基于平臺的“取并加一”原子操作實現面向CPE陣列全體的互斥鎖.由于被鎖保護的臨界區一次只能容納一個CPE 線程進行訪問和CPE 無法進行線程切換等原因,其余想要訪問該臨界區的CPE 不得不處于“忙等”狀態——反復讀取并判別存儲在內存中的同步信號以獲取臨界區訪問權限.大量線程的忙等導致訪存量劇增,極大地影響了臨界區中工作線程的訪存能力.因此,為了減少加鎖導致的冗余訪存,CI 模塊中的互斥鎖還具備睡眠功能:獲取鎖訪問權限失敗的線程將進入“睡眠”狀態以避免對內存的高頻訪問.睡眠時間可由程序員自主調優.此外,CI 模塊中包含了能夠讓眾多CPE 線程并發申請內存空間的內存管理子模塊.在互斥鎖和內存管理子模塊基礎上,CI 模塊中還使用泛型技術實現了并發循環隊列和并發Hash表等關鍵數據結構.出于性能考慮,這些并發數據結構需結合平臺特性予以實現,具體內容在第3.2 節中詳述.

在CI 模塊基礎上,本文對單組CG 的MPE 和各個CPE 分別進行建模,形成SWAN-MPE 和SWAN-CPE,旨在使得一組CG 的所有處理核心形成一個具有生產、交換、維護和處理任務的有機整體.由于程序的主進程運行于MPE 上,SWAN-MPE 對象需要管理整個SWAN 框架.因此,其需要包含一個由指定數量的SWAN-CPE 對象形成的集合和諸多共享數據:任務總量及完成任務總量,任務參數總表及各個SWAN-CPE 線程的內存使用量、處理器時間等運行時信息以為SWAN 框架的負載均衡行為提供依據.SWAN-CPE 對象用來對一個CPE 進行建模,其包括了若干私有及公共的數據結構.其中,就緒任務隊列負責存放當前已經就緒的可執行任務,在必要情況下,就緒任務隊列中的任務可以被其他線程偷取[17,19,25],以保證負載平衡.掛起任務隊列屬于一個SWAN-CPE 的私有隊列,當一個任務由于依賴關系未被滿足而中止時,該SWAN-CPE 將其加入掛起隊列并獲取其他任務繼續執行.待某一時刻該任務的所有前驅依賴關系全部滿足后,SWAN-CPE 可將該任務再度放入就緒任務隊列中等待執行.每個SWANCPE 還有私有的已完成任務集,在該集合中的任務需要進一步被處理,以解除它們所有后繼任務的依賴.每個SWAN-CPE 還負責記錄自己的內存使用量及處理器運行時間,在其空閑時更新SWAN-MPE 對象中對應數據條目.一個進程的所有共享內存空間被劃分成若干部分,使得每個SWAN-CPE 線程擁有獨立的私有內存空間來存放相應的數據結構.在私有內存空間不足的情況下,一個SWAN-CPE 可將自己的內存分配請求發送給其他SWAN-CPE.這樣,SWAN 框架在充分利用內存資源的同時還能有效地避免多個線程爭相申請內存而帶來的開銷.綜上所述,MC-Modeling 模塊的設計分散了SWAN 框架的關鍵數據結構,盡可能地避免了共享資源的爭用.

3.2 SWAN動態行為

SWAN 支持任務的動態生成及依賴關系的解析,這一關鍵過程被實現在SWAN 的QPP 模塊中.如圖3 所示,一個簡單的尾遞歸程序的并行執行由“任務-0”開始.初始時,任務-0 被“SWAN-CPE 0”執行,在執行過程中,由于任務-0 的進一步執行依賴于由它產生的兩個子任務(“任務-1”和“任務-2”)的完成.因而,任務-0 被SWAN-CPE 0 掛起(加入掛起任務隊列).同時,衍生出的任務-1 和任務-2 被加入0 號SWAN-CPE 的就緒任務隊列中.此時,由于SWAN-CPE x 處于線程饑餓狀態,由上文所述,它能夠在SWAN-CPE 0 的就緒任務隊列中竊取某一任務(假設為任務-1)以進行處理.當任務-1 和任務-2 被各個SWAN-CPE 執行完畢之后,它們被放入相應的終止任務隊列,等待后續處理.處理一個已被完成的任務包括釋放其占用的內存資源及解除與它相關的任務依賴關系.此時在 SWAN-CPE 0 的中掛起的任務-0 由于其所有的依賴條件皆被滿足,它將被重新放回SWAN-CPE 0 的就緒隊列中得以進一步執行.

Fig.3 Process of task dependency resolvement in SWAN圖3 SWAN 任務依賴關系解析過程

3.3 SWAN用戶接口

SWAN 向用戶提供了方便的編程API,程序員并不需要顯示操作“任務”這一數據結構.附錄1 和附錄2 分別展現了由SWAN API 編寫的并行快速排序和并行凸包求解程序,用戶可以與函數調用相似的方式向SWAN 框架動態地插入任務,程序的并行細節對程序員來說是透明的.

4 SWAN 框架的關鍵技術

4.1 任務掛起和上下文保存

在嵌套并行程序中,父任務的執行往往依賴其子任務執行的結果,在這種情況下父任務不得不暫停以等待所有子任務的完成.在沒有線程切換功能的CPE 上,SWAN 框架為用戶提供了任務斷點以中止當前任務的繼續執行.在該任務的所有依賴關系被滿足后,SWAN-CPE 可從任務斷點開始繼續處理先前被掛起的任務.在任務掛起之前,用戶還能將LDM 中的關鍵數據移交至SWAN 框架進行保存,以便在任務恢復執行時取回LDM 加以使用.我們發現,任務的掛起和重啟功能不僅能妥善處理任務間的依賴關系,在一些算法(如凸包求解算法,見附錄2)中還有利于提高算法的并發度.

4.2 基于DMA和LDM的循環隊列

在運行時,SWAN-CPE 需要不斷地從就緒任務隊列或掛起任務隊列中獲得任務進行執行,因此SWAN-CPE對這些隊列的訪問效率將影響SWAN 框架本身的性能.由于目標平臺擁有DMA 高速訪存機制和程序可控LDM,我們采用了具有線性存儲結構的環形鏈表,并將處于表頭和表尾部分的若干任務指針緩存于擁有這些隊列SWAN-CPE 的LDM 中,形成緩存結構.該SWAN-CPE 若需要獲得位于表頭的任務時,事先會向該隊列的LDM緩存進行索取;若獲取失敗,則使用DMA 將批量任務指針加載到緩存.與此類似,若該SWAN-CPE 需要向隊尾插入任務時,可直接將該任務的指針放入進隊緩存;當緩存隊列放滿時,則使用DMA 向位于內存中的隊尾進行批量插入.由于工作竊取機制的存在,某一就緒任務隊列在運行時將可能被多個SWAN-CPE 并發訪問.為了保持隊列中數據的一致性,我們限定來自其他SWAN-CPE 的工作竊取請求只能作用于未被緩存入LDM 的任務,而當前處于緩存中的任務被認為是當前SWAN-CPE 私有的.值得注意的是,任意循環隊列的都有指定的容量,因此SWAN-CPE 不能無限制地向某一隊列加入任務而不及時獲取任務進行處理.

4.3 負載均衡策略

任務并行框架需要采取一定的任務調度策略[26,27]確保程序的并發度和處理單元的負載均衡.SWAN 目前提供兩種工作竊取[17,19,25,28,29]手段保證CPE 陣列的動態負載均衡:輪詢竊取及基于動態信息的竊取.輪詢竊取策略的實現相對簡單:每個SWAN-CPE 持有一個私有的輪詢計數器,每次線程饑餓時對計數器指定的SWANCPE 進行任務竊取并使計數器指向下一個SWAN-CPE 的線程標志.輪詢竊取機制實現簡單,運行時開銷較小并能夠確保SWAN 框架產生的所有竊取行為均勻地分布于所有SWAN-CPE.基于動態信息的竊取機制需要SWAN-CPE 動態地維護自身運行時信息,如已執行的任務數.需要竊取任務的SWAN-CPE 通過向SWAN-MPE對象查詢以得知至此最為繁忙(已完成任務數量最大)的SWAN-CPE,并在它的就緒任務隊列中竊取任務.基于動態信息的工作竊取機制由于需要維護全局運行信息,因此開銷較大,但其竊取行為目標較為明確.一般而言,基于動態信息的工作竊取在任務粒度較大時具有較高調度效率,而輪詢竊取在任務粒度較小但數量多時效率較高.

5 實 驗

我們在SW26010 CPU 的一組CG 上對SWAN 的可用性和性能進行測試.一組CG 擁有大小為7.7GB 的內存空間.MPE 的主頻為1.25GHz,理論帶寬大約為5GB/s.單個CPE 的主頻為1.45GHz,DMA 的理論聚合帶寬為34GB/s(實際峰值為22GB/s).實驗所使用的程序均采用sw5cc 編譯器編譯,產生相應的MPE 代碼及CPE 代碼,所有編譯過程均采用“-O3”優化選項.我們在多個任務并行基準測試集如Barcelona OpenMP Task Suite[5]和Clik Task Suite[14?16]中選取了4 個具有代表性的嵌套并行算法(算例),并使用SWAN 框架在CPE 陣列上實現它們.這4 個算例分別是N-皇后問題,二叉樹遍歷,快速排序和凸包求解.我們采用運行在MPE 上的各個算法的串行版本作為性能參考基準,來衡量使用SWAN 框架并行化帶來的性能提高.并行程序運行的負載均衡率由運行時單個CPE 處理的平均任務數量和單個CPE 處理的最大任務數量的比決定[22].對于SWAN 的可用性,我們擬在附錄1 和附錄2 中分別展示使用SWAN 實現的具有尾遞歸特點的并行快速排序算法和具有首遞歸特點的并行凸包求解算法.

5.1 N-皇后問題

N-皇后問題要求在一個N×N的國際象棋棋盤上放置N個“皇后”棋子,并保證每個皇后不能直接攻擊其他任意一個皇后.根據國際象行棋的規則,這些皇后棋子不能同時處于同一行、列及斜對角線.由于下一步棋子擺放的方式依賴于當前已擺放的棋子的形態,因此N-皇后問題通常使用遞歸方式進行求解.然而在具體的算法執行過程中,該算法有著大量的并行性值得挖掘:假設已經成功擺放了K–1 個棋子,那么驗證第K個棋子的各種擺放方法是否合法的計算間是相互獨立的.通過SWAN 可以讓該算法的并行性充分地實現在CPE 核組上.

對棋子合法性進行判斷的計算代碼可以得到針對性的簡化,但這并不影響SWAN 框架的使用.因此在圖4中我們分別展示了使用經過計算簡化的程序和未經計算簡化的程序的可擴展性.但該算法無論是否經過計算簡化,CPE 陣列并行版本相對于使用同樣計算代碼的MPE 串行版本都有顯著的加速比.而且加速比隨著問題規模的增大而顯著提高.這是因為隨著問題規模的增大,更多獨立的任務能夠被分配到各個CPE 得以并行處理.進一步的測試表明在執行14-queens算法的過程中,各個從核的負載均衡率能夠達到了91%.但值得我們注意的是:第一,計算簡化對MPE 串行程序帶來了更優的加速效果,進而使得對應的并行加速比整體較低.第二,雖然在實驗中我們開啟了64 個CPE 線程,但程序整體的并行加速比并不超過4.5.這是因為一方面MPE 的數據緩存能夠容納整張棋盤,因此MPE 串行實現的訪存效率很高;另一方面,每一個CPE 任務的訪存規模太小而導致眾核并行版訪存時DMA 性能較低.

Fig.4 Speedup of the parallel N-Queens problem against the serial reference on the MPE圖4 并行版N-皇后問題相對于MPE 串行版的加速比

5.2 二叉樹遍歷

二叉樹遍歷算法要求(并行地)訪問二叉樹的每一個節點,并保證每個節點僅被訪問一次.在實際應用中各個二叉樹的節點可代表不一樣的處理邏輯.不失一般性,我們擬統計二叉樹各個節點所含字符串中含有給定字符的數量.在本例中,我們采用二叉樹的后根遍歷算法,以驗證SWAN 框架確保任務執行順序的能力.為了讓SWAN 框架體現其在大規模計算中帶來的加速效果,各個節點的字符串的長度被設置為5 000～10 000;為了進一步驗證SWAN 框架的負載均衡能力,對于每一個節點,我們產生隨機長度的字符串并使其左右子節點的字符串總長度的比值達到30%.

如圖5 所示,以SWAN 框架實現的并行二叉樹遍歷程序的性能大幅度高于MPE 串行版本,隨著樹的規模的增大,加速比可提高到35 倍左右.這一方面由于SWAN 能夠將計算負載分配到各個CPE 進行并行處理,另一方面是因為在各個任務的訪存量較大,DMA 機制傳輸效率高.我們還發現,在問題規模較小的測試條件下(樹高度小于15 時),基于運行時信息的工作竊取策略優于基于輪詢的工作竊取策略.在此用例中,我們還發現使用LDM緩沖的并發循環隊列能夠使性能進一步提高約30%.經過進一步測試我們還發現即便在非規整的數據結構上,整個并行程序的負載均衡率也到達了85 以上,這說明SWAN 框架有著較強的負載均衡能力.

Fig.5 Speedup of parallel binary tree traversal against the MPE sequential binary tree traversal圖5 并行版二叉樹遍歷程序相對于MPE 串行版的加速比

5.3 快速排序

快速排序在目標數據集中選取一個“主元(pivot)”之后,將原數據序列以該主元為基準按照大小關系一分為二.對劃分出的數據子列以同樣的方式處理,直到子列只含有不多于1 個元素.原始無序數據序列在經過如是處理之后變為有序.在實際的應用中,我們還可以設定一個閾值K,當數據子列的長度小于K之后,使用高效的串行排序核心處理當前數據子列,以避免任務粒度過小.為考察使用SWAN 實現的并行排序在實際應用中的性能表現,我們選取實現在C 語言標準庫中的快速排序(函數qsort)作為性能對比基準.

如圖6 所示,在同樣的測試數據序列上,以SWAN 為基礎實現的并行快速排序相對qsort 有高于13 倍的加速比.由于SWAN 為程序員屏蔽了并行調度的細節,程序員可以集中注意力于核心排序函數的性能優化上.比如在當前算例中,我們對長度小于K 的整型數據子列采用查表的方式進行排序,可使計算復雜度變為線性.經過計算核心的優化,基于SWAN 的并行排序算法的性能又提升了大約2 倍.與此類似,對于其他數據類型的排序,還可以使用向量化等手段提高排序核心函數的性能,在此不贅述.

Fig.6 Speedup of the parallel quick-sort algorithm against the sequential qsort in C standard library圖6 并行版快速排序算法對C 標準庫中串行qsort 函數的加速比

5.4 凸包求解

在一個實數向量空間V中,對于給定點集X,所有包含X的凸集的交集S被稱為X的凸包.本文只討論二維空間中點集的情況.圖7 中紅色連線確定了一個含有12 個點的平面點集形成的凸包.圖7(a)～圖7(f)分步展示了該凸包的快速求解算法的遞歸步驟:首先確定含有最小橫坐標值和最大橫坐標值的點a和b并進入遞歸步驟:以有向線段ab為基準,分別在其兩側進一步確定凸包中的其他點.以ab上側為例,點c為距離ab最遠點,將c加入凸包并由此形成有向線段ac和cb.之后分別以ac和cb為基準線段,分別在它們外側進一步尋找凸包中的點.

Fig.7 Demonstration of the recursive convex-hull algorithm圖7 凸包問題的遞歸求解算法示意

給定一條基準線段和對應點集,將源任務定義為求在基準線外側距該基準線段距離最遠的點.以源任務為基礎使用SWAN 可輕易實現并行的凸包求解程序(附錄2).但由圖7 可以看到,在算法的初始階段,由于有向基準線段的數量較少導致了程序的并行度很低.但在該階段,少量的線程需要計算大量的點到基準線段的距離,因此形成了程序的性能瓶頸.針對這種情況,我們使用SWAN 的任務掛起和上下文保存功能,使程序在初始階段就派生諸多距離計算子任務以使更多的處理核心參與計算.在所有距離計算子任務結束后,由源任務進行歸約產生目標點.如圖8 所示,在初始階段提高并發度后,凸包求解程序的性能最終達到MPE 串行版本性能的23.6 倍.

Fig.8 Speedup of the parallel convex-hull algorithm against the MPE sequential convex-hull algorithm圖8 并行版凸包算法相對于MPE 串行版算法的加速比

6 結論及未來的工作

在新興的SW26010 眾核處理器上,本文提出并實現了支持任務并行模式的SWAN 框架,并成功將之應用于若干典型的嵌套并行算法.在目標平臺上,SWAN 框架為用戶實現任務并行提供了高層次的抽象,能夠大幅度降低用戶開發任務并行程序的難度.在現有CPE 功能的基礎上,SWAN 能夠掛起并恢復任務的執行,使得具有遞歸特性的嵌套并行算法能夠得以有效并行.結合SW26010 的訪存特性,SWAN 框架中關鍵數據結構采用了高效的DMA 訪存機制和LDM 緩存以有效地降低框架本身的執行開銷.在并行程序執行過程中,SWAN 還能夠確保任務在各個處理單元上的負載平衡以充分發揮眾核陣列的計算效能.實驗表面,在若干典型嵌套并行程序算例中,SWAN 能夠有效加速目標程序,并隨著問題規模的增大,加速效果更加明顯.值得一提的是,通過對SWAN 框架的靈活應用,我們可將集中在凸包問題初始階段的大量計算負載均分到各個可用的CPE 核心上,縮短程序執行的關鍵路徑長度以大幅度提高程序的性能.

今后的工作將從兩個方面展開.一方面,基于SWAN 框架,我們將在SW26010 眾核核組上進一步研究各類嵌套并行算法,在此過程中設計新穎的動態負載均衡策略以提高程序的執行效率.另一方面,我們將進一步豐富和完善SWAN 框架的功能,將基于任務有向無環圖的任務調度技術整合于SWAN 框架中以拓展其使用領域.

附錄1:基于SWAN 框架實現的并行快速排序

在圖A 中,我們展示了使用SWAN 框架編寫的并行快速排序程序.圖A 中文件“Qsort_SWAN_MPE.c”和“Qsort_SWAN_CPE.c”分別記錄了運行于MPE 和CPE 上的代碼.紅色高亮部分的語句是SWAN 框架提供的API.我們看到SWAN 可以幫助用戶清晰地表達程序邏輯,使得并行快速排序的整體代碼結構與串行遞歸程序高度相仿.

Fig.A Parallel quick sort programme using SWAN framework圖A 用SWAN 實現的并行快速排序程序

附錄2:基于SWAN 實現的并行凸包求解算法

在圖B 中,我們展現了使用SWAN 框架實現的并行凸包程序.與附錄1 中的并行快速排序類似,SWAN 幫助程序員并行化了凸包求解算法的遞歸結構.但值得注意的是,在圖B 展現的“SWAN_ Convex_Hull_CPE.c”文件中,為了提高程序的并行性,當前任務slave_convex_hull_task 需要派生眾多子任務去尋找距當前基準有向線段距離最遠點(行17).此時,父任務需掛起并等待所有子任務的完成.通過調用SWAN 框架負責上下文保存及任務掛起的接口(行14～行19),該過程能夠得以實現.在掛起任務之前,用戶使用“swan_save_variable()”函數記錄關鍵上下文信息(行16).當該任務被重新執行時,程序控制流將從行14 直接跳轉到行18 繼續執行,并取回上下文信息(行19).

Fig.B Parallel conve-hull programme using SWAN framework圖B 使用SWAN 實現的并行凸包程序