SW26010 眾核任務(wù)并行調(diào)度系統(tǒng)及其嵌套并行算法應(yīng)用?

孫 喬,黎雷生,趙海濤,趙 慧,吳長(zhǎng)茂

(中國(guó)科學(xué)院 軟件研究所 并行軟件與計(jì)算科學(xué)實(shí)驗(yàn)室,北京 100190)

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

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

Fig.1 Architecture of a SW26010 many-core CPU圖1 SW26010 眾核CPU 體系結(jié)構(gòu)

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

本文第1 節(jié)將進(jìn)一步描述對(duì)SWAN 的設(shè)計(jì)實(shí)現(xiàn)有著重要影響的目標(biāo)平臺(tái)特性,并針對(duì)性地提出SWAN 框架的設(shè)計(jì)目標(biāo).第2 節(jié)具體描述SWAN 的靜態(tài)結(jié)構(gòu)與和動(dòng)態(tài)行為.第3 節(jié)進(jìn)一步介紹SWAN 框架采用的關(guān)鍵技術(shù).第4 節(jié)擬通過若干具有代表性的嵌套并行算法對(duì)SWAN 的實(shí)用性及性能進(jìn)行測(cè)試.第5 節(jié)回顧在主流的多(眾)核平臺(tái)上常用的諸多任務(wù)并行框架,并探討其與SWAN 的區(qū)別與聯(lián)系.第6 節(jié)對(duì)本文的工作進(jìn)行總結(jié).

1 平臺(tái)特性

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

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

綜上所述,在SW26010 上實(shí)現(xiàn)通用的支持任務(wù)并行的運(yùn)行時(shí)框架,需以現(xiàn)有的并行接口為基礎(chǔ),采用軟件方式跨越硬件限制并充分利用平臺(tái)的各種資源.因此SWAN 框架的設(shè)計(jì)和實(shí)現(xiàn)具有相當(dāng)?shù)碾y度.

2 相關(guān)工作

雖然SWAN 框架為SW26010 眾核核組定制,結(jié)合了諸多平臺(tái)的軟硬件特性,但當(dāng)今國(guó)內(nèi)外在任務(wù)并行模式及任務(wù)并行框架方面的研究對(duì)SWAN 框架的設(shè)計(jì)與實(shí)現(xiàn)有著重要的借鑒意義.

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

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

3 SWAN 框架的結(jié)構(gòu)與行為

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

Fig.2 Software architecture of SWAN圖2 SWAN 軟件體系結(jié)構(gòu)

3.1 SWAN框架的靜態(tài)結(jié)構(gòu)

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

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

3.2 SWAN動(dòng)態(tài)行為

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

Fig.3 Process of task dependency resolvement in SWAN圖3 SWAN 任務(wù)依賴關(guān)系解析過程

3.3 SWAN用戶接口

SWAN 向用戶提供了方便的編程API,程序員并不需要顯示操作“任務(wù)”這一數(shù)據(jù)結(jié)構(gòu).附錄1 和附錄2 分別展現(xiàn)了由SWAN API 編寫的并行快速排序和并行凸包求解程序,用戶可以與函數(shù)調(diào)用相似的方式向SWAN 框架動(dòng)態(tài)地插入任務(wù),程序的并行細(xì)節(jié)對(duì)程序員來說是透明的.

4 SWAN 框架的關(guān)鍵技術(shù)

4.1 任務(wù)掛起和上下文保存

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

4.2 基于DMA和LDM的循環(huán)隊(duì)列

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

4.3 負(fù)載均衡策略

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

5 實(shí) 驗(yàn)

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

5.1 N-皇后問題

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

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

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

5.2 二叉樹遍歷

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

如圖5 所示,以SWAN 框架實(shí)現(xiàn)的并行二叉樹遍歷程序的性能大幅度高于MPE 串行版本,隨著樹的規(guī)模的增大,加速比可提高到35 倍左右.這一方面由于SWAN 能夠?qū)⒂?jì)算負(fù)載分配到各個(gè)CPE 進(jìn)行并行處理,另一方面是因?yàn)樵诟鱾€(gè)任務(wù)的訪存量較大,DMA 機(jī)制傳輸效率高.我們還發(fā)現(xiàn),在問題規(guī)模較小的測(cè)試條件下(樹高度小于15 時(shí)),基于運(yùn)行時(shí)信息的工作竊取策略優(yōu)于基于輪詢的工作竊取策略.在此用例中,我們還發(fā)現(xiàn)使用LDM緩沖的并發(fā)循環(huán)隊(duì)列能夠使性能進(jìn)一步提高約30%.經(jīng)過進(jìn)一步測(cè)試我們還發(fā)現(xiàn)即便在非規(guī)整的數(shù)據(jù)結(jié)構(gòu)上,整個(gè)并行程序的負(fù)載均衡率也到達(dá)了85 以上,這說明SWAN 框架有著較強(qiáng)的負(fù)載均衡能力.

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

5.3 快速排序

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

如圖6 所示,在同樣的測(cè)試數(shù)據(jù)序列上,以SWAN 為基礎(chǔ)實(shí)現(xiàn)的并行快速排序相對(duì)qsort 有高于13 倍的加速比.由于SWAN 為程序員屏蔽了并行調(diào)度的細(xì)節(jié),程序員可以集中注意力于核心排序函數(shù)的性能優(yōu)化上.比如在當(dāng)前算例中,我們對(duì)長(zhǎng)度小于K 的整型數(shù)據(jù)子列采用查表的方式進(jìn)行排序,可使計(jì)算復(fù)雜度變?yōu)榫€性.經(jīng)過計(jì)算核心的優(yōu)化,基于SWAN 的并行排序算法的性能又提升了大約2 倍.與此類似,對(duì)于其他數(shù)據(jù)類型的排序,還可以使用向量化等手段提高排序核心函數(shù)的性能,在此不贅述.

Fig.6 Speedup of the parallel quick-sort algorithm against the sequential qsort in C standard library圖6 并行版快速排序算法對(duì)C 標(biāo)準(zhǔn)庫中串行qsort 函數(shù)的加速比

5.4 凸包求解

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

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

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

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

6 結(jié)論及未來的工作

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

今后的工作將從兩個(gè)方面展開.一方面,基于SWAN 框架,我們將在SW26010 眾核核組上進(jìn)一步研究各類嵌套并行算法,在此過程中設(shè)計(jì)新穎的動(dòng)態(tài)負(fù)載均衡策略以提高程序的執(zhí)行效率.另一方面,我們將進(jìn)一步豐富和完善SWAN 框架的功能,將基于任務(wù)有向無環(huán)圖的任務(wù)調(diào)度技術(shù)整合于SWAN 框架中以拓展其使用領(lǐng)域.

附錄1:基于SWAN 框架實(shí)現(xiàn)的并行快速排序

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

Fig.A Parallel quick sort programme using SWAN framework圖A 用SWAN 實(shí)現(xiàn)的并行快速排序程序

附錄2:基于SWAN 實(shí)現(xiàn)的并行凸包求解算法

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

Fig.B Parallel conve-hull programme using SWAN framework圖B 使用SWAN 實(shí)現(xiàn)的并行凸包程序