任務(wù)并行編程模型

任務(wù)并行編程模型電信學(xué)部 ——1任務(wù)并行編程模型概述傳統(tǒng)的并行編程模型主要有數(shù)據(jù)并行和消息傳遞,數(shù)據(jù)并行編程模型的編程級別比較高,編程相對簡單,但它僅適用于數(shù)據(jù)并行問題;消息傳遞編程模型的編程級別相對較低,但消息傳遞編程模型可以有更廣泛的應(yīng)用范圍。任務(wù)并行編程模型把任務(wù)作為并行的基本單位,提供任務(wù)劃分和同步的編程接口,把任務(wù)劃分和同步工作

交給程序員完成,用戶可以把應(yīng)用程序劃分出大量細粒度任務(wù).然而,具體到每個任務(wù)到底是并行執(zhí)行還是串行執(zhí)行、在哪個物理核上執(zhí)行以及如何實現(xiàn)任務(wù)之間的同步則由運行時系統(tǒng)完成.運行時系統(tǒng)通過基于有向無環(huán)圖(DAG)的任務(wù)竊取調(diào)度算法來管理任務(wù)的執(zhí)行。2任務(wù)并行編程模型優(yōu)點為程序員提供了兩類并行控制結(jié)構(gòu),分別是支持規(guī)則并行的循環(huán)并行控制結(jié)構(gòu)和支持非規(guī)則并行的嵌套并行控制結(jié)構(gòu).邏輯任務(wù)與物理線程分離,程序員只需考慮如何劃分邏輯任務(wù),使用合適的并行控制結(jié)構(gòu)并行邏輯任務(wù)運行時系統(tǒng)負責(zé)任務(wù)調(diào)度,采用任務(wù)竊取調(diào)度算法獲得負載平衡,提高多核的使用效率3內(nèi)容提綱1.關(guān)鍵技術(shù)挑戰(zhàn)

并行性表達

數(shù)據(jù)管理

任務(wù)調(diào)度2.針對挑戰(zhàn)的最新研究成果

并行性表達

數(shù)據(jù)管理

任務(wù)調(diào)度3.未來的展望

41.關(guān)鍵技術(shù)挑戰(zhàn)1.1該模型的編程接口能支持的并行模式有限,需要豐富編程接口,表達多種多樣的并行性嵌套并行控制結(jié)構(gòu)

循環(huán)級并行無條件原子塊結(jié)構(gòu)有條件原子塊結(jié)構(gòu)1.2該模型把數(shù)據(jù)分為共享和私有兩種,通過共享數(shù)據(jù)進行通信.但有些數(shù)據(jù)是部分任務(wù)共享,或者一個線程內(nèi)執(zhí)行的所有任務(wù)共享,因此需要對數(shù)據(jù)進一步區(qū)分共享范圍,需要研究如何高效實現(xiàn)不同級別的共享數(shù)據(jù);1.3降低運行時系統(tǒng)開銷52.最新研究成果

2.1并行性表達尾端嚴格的特性循環(huán)級并行表達原子塊結(jié)構(gòu)移相器62.1.1尾端嚴格的特性尾端嚴格的特性任務(wù)同步對應(yīng)的依賴關(guān)系在任務(wù)之間產(chǎn)生join邊,DAG任務(wù)圖中每條join邊都是從一個任務(wù)的最后一條指令指向其派生樹的某祖先完全嚴格的join邊總是從派生樹的某節(jié)點指向父親節(jié)點7依賴圖滿足的嚴格特性82.1.2循環(huán)級并行表達Cilk++cilk_for關(guān)鍵詞支持循環(huán)級并行,任務(wù)圖采用DFS(深度優(yōu)先搜索)具體實現(xiàn)方法采用分治法切分迭代空間,把循環(huán)并行轉(zhuǎn)換為嵌套并行,從而把任務(wù)壓入或彈出任務(wù)隊列OpenUH任務(wù)圖采用BFS(廣度優(yōu)先搜索)TBB(ThreadingBuildingBlocks)一個C++并行模板庫,通過parallel_for、parallel_do等關(guān)鍵詞表達并行,底層實現(xiàn)運用了Cilk的任務(wù)竊取調(diào)度算法92.1.3原子塊結(jié)構(gòu)X10語言支持無條件原子塊結(jié)構(gòu)atomicS和有條件原子塊結(jié)構(gòu)when(E)S.當(dāng)條件E不為真時,有條件原子塊結(jié)構(gòu)when(E)S只能被掛起具體方法是:每一個庫所(通常指一個緩存一致性的計算單元)共享一個額外隊列存放被掛起的有條件的原子塊;當(dāng)執(zhí)行到when結(jié)構(gòu)時,E為假,就把這個原子塊放入額外隊列中,掛起該原子塊,成為空閑線程.當(dāng)線程執(zhí)行完某個原子塊時,把共享的額外隊列中所有原子塊放入自己的任務(wù)隊列中,這樣,每一個被掛起的原子塊的條件都會重新再計算一遍.102.1.4移相器2008年,Rice大學(xué)借鑒X10的任務(wù)并行結(jié)構(gòu)提出HabaneroJava任務(wù)并行語言,引入了移相器(phaser)及其累加器(accumulator)這兩個概念,目的是降低柵障和規(guī)約的開銷移相器是X10中同步鐘的一個擴展,它是一個同步對象,支持4種操作:創(chuàng)建、注冊、退出和推進.移相器與其累加器相結(jié)合把集合操作劃分為數(shù)據(jù)發(fā)送、計算、結(jié)果取回和同步,支持計算和通信的重疊112.2數(shù)據(jù)管理數(shù)據(jù)屬性表達并發(fā)數(shù)據(jù)結(jié)構(gòu)鎖外協(xié)助122.2.1數(shù)據(jù)屬性表達基于共享存儲的任務(wù)并行編程模型用全局變量進行通信和同步.全局變量在串行程序中用于簡化編程,但在并行程序中會導(dǎo)致數(shù)據(jù)競爭.用鎖避免對共享數(shù)據(jù)的競爭會影響并行度,從而不能獲得高性能Cilk++提供超級對象(hyperobjects)來描述數(shù)據(jù)屬性.運行時系統(tǒng)保證每個線程有全局變量的私有拷貝,線程訪問私有拷貝,這樣,在不需要鎖的情況下消除了線程間競爭的可能性132.2.2并發(fā)數(shù)據(jù)結(jié)構(gòu)一個并發(fā)數(shù)據(jù)結(jié)構(gòu)允許多個線程并發(fā)訪問和更新數(shù)據(jù)結(jié)構(gòu)中的元素,它往往使用細粒度鎖或lock-free技術(shù)等方法加以實現(xiàn),在保證線程安全的同時得到并行加速比,但是復(fù)雜,難理解,而且有明顯的實現(xiàn)開銷.Cilk++利用reducer超級對象實現(xiàn)了這樣一個快速訪問的并發(fā)集合bag,多個線程可以同時向集合bag中增加或刪除數(shù)據(jù)142.2.2并發(fā)集合這個并發(fā)集合是一個指針數(shù)組,每個數(shù)組元素是一棵

二叉樹.指針數(shù)組相當(dāng)于一個二進制數(shù),表明集合中元素的個數(shù).例如,指針數(shù)組A[]是010111,表示有23個節(jié)點,A[0]是有1個節(jié)點的二叉樹,A[1]是有2個節(jié)點的二叉樹,A[2]是有4個節(jié)點的二叉樹,A[3]和A[5]沒有節(jié)點,A[4]是有16個節(jié)點的二叉樹.當(dāng)有兩個線程需要共同訪問這個并發(fā)集合時,這個指針數(shù)組A能夠快速分裂成兩個大小相同的指針數(shù)組,兩個線程分別訪問不同的數(shù)組;sync之后,也能快速地把兩個指針數(shù)組合并成一個數(shù)組.這種無鎖的并發(fā)集合比基于鎖的并發(fā)集合性能好很多.152.2.3鎖外協(xié)助臨界區(qū)是用于防止多個線程同時執(zhí)行一段特定代碼的機制,常用鎖對臨界區(qū)進行保護,每次只能有一個線程執(zhí)行臨界區(qū)內(nèi)的代碼.假設(shè)線程1獲得鎖L,開始執(zhí)行臨界區(qū)A.這時,線程2也想獲得鎖L,它只能被阻塞helplock:當(dāng)線程2不能獲得鎖L時,線程2不是阻塞,而是掛起自己的任務(wù),幫助線程1去執(zhí)行臨界區(qū)A的任務(wù).這樣,線程2沒有忙等,充分利用了計算資源.這種helplock非常適合臨界區(qū)較大的程序162.3任務(wù)調(diào)度

任務(wù)并行編程模型提供隱式的任務(wù)映射機制,運行時系統(tǒng)采用任務(wù)竊取調(diào)度算法,把邏輯任務(wù)映射到物理線程上去執(zhí)行.提高執(zhí)行效率是運行時系統(tǒng)的核心任務(wù)任務(wù)竊取調(diào)度算法局部性敏感的調(diào)度算法異構(gòu)系統(tǒng)調(diào)度算法控制任務(wù)粒度172.3.1任務(wù)竊取調(diào)度算法任務(wù)竊取調(diào)度算法的實現(xiàn)方法是每個處理器核對應(yīng)一個線程,每個線程維護一個雙端隊列存放任務(wù)狀態(tài)信息,這個狀態(tài)信息包括任務(wù)中的局部變量、PC值、子任務(wù)的個數(shù)等,用于恢復(fù)被掛起任務(wù)或執(zhí)行被竊取的任務(wù).每個線程從自己雙端隊列的尾部壓入準備好的任務(wù)或彈出已經(jīng)執(zhí)行完的任務(wù);當(dāng)自己雙端隊列為空時,從其他線程的雙端隊列頭部竊取任務(wù),首先恢復(fù)竊取的任務(wù)狀態(tài),然后根據(jù)狀態(tài)跳轉(zhuǎn)到相應(yīng)的的指令開始執(zhí)行182.3.2局部性敏感的調(diào)度算法任務(wù)竊取采用最早任務(wù)優(yōu)先竊取策略,該策略的“深度優(yōu)先執(zhí)行”能夠提高cache的利用率.但隨機選擇線程進行任務(wù)竊取,而沒有考慮處理器架構(gòu)特點,對于局部性敏感的應(yīng)用會有影響.局部性敏感的調(diào)度算法主要關(guān)注如何選擇要竊取的線程.19Cache親密性調(diào)度每個線程除了任務(wù)隊列外還有一個郵箱(mailbox),用于存放與該線程親密的任務(wù).當(dāng)線程1產(chǎn)生一個與線程2有親密性的任務(wù)時,線程1把指向該任務(wù)的指針放入線程2的郵箱中.當(dāng)線程2完成自己任務(wù)隊列中的任務(wù)時,先檢查自己的郵箱,執(zhí)行郵箱中的任務(wù),最后再竊取任務(wù).20多路多核處理器架構(gòu)上的局部性敏感調(diào)度目前,服務(wù)器基本上都是多路多核架構(gòu),處理器包含多個多核芯片,片內(nèi)多核共享L3cache,片間多核共享內(nèi)存,提供cache一致性.任務(wù)竊取調(diào)度策略是隨機選擇一個線程進行任務(wù)竊取,沒有區(qū)分片內(nèi)和片間的線程,而對于局部性敏感的應(yīng)用,這種隨機任務(wù)竊取調(diào)度策略降低了cache利用率,從而也導(dǎo)致性能下降.根據(jù)硬件結(jié)構(gòu)對線程進行分組,片內(nèi)的線程分為一組,每個線程有一個組內(nèi)任務(wù)隊列,每個組有一個組間任務(wù)隊列.運行時系統(tǒng)順著調(diào)用樹把任務(wù)分成組內(nèi)任務(wù)和組間任務(wù),然后放入相應(yīng)的任務(wù)隊列中.線程執(zhí)行完自己的組內(nèi)任務(wù)隊列中的任務(wù)后,隨機選取同組其他線程進行任務(wù)竊取;當(dāng)一個組的所有組內(nèi)任務(wù)隊列為空時,從本組的組間任務(wù)隊列中竊取任務(wù);當(dāng)一個組的所有組內(nèi)任務(wù)隊列和組間任務(wù)隊列都為空時,就從其他組的組間任務(wù)隊列中竊取任務(wù).212.3.3異構(gòu)系統(tǒng)調(diào)度算法假設(shè)共享存儲系統(tǒng)中各個處理器的執(zhí)行速度不同,在這種異構(gòu)系統(tǒng)中,執(zhí)行速度快的處理器可以打斷執(zhí)行速度慢的處理器,并把它正在執(zhí)行的任務(wù)竊取過來執(zhí)行222.3.4控制任務(wù)粒度運行時系統(tǒng)用軟件實現(xiàn)任務(wù)竊取調(diào)度算法是有代價的,產(chǎn)生大量的細粒度任務(wù)會加重系統(tǒng)開銷;相反地,產(chǎn)生少量的粗粒度任務(wù)會造成負載不平衡,從而使性能下降.由此可見,系統(tǒng)開銷與任務(wù)數(shù)量成正比,而負載平衡與任務(wù)數(shù)量成反比,合適的任務(wù)粒度是在系統(tǒng)開銷和負載平衡兩個因素之間加以權(quán)衡.如何獲得合適的任務(wù)粒度是任務(wù)并行編程模型的一個重要問題.23控制任務(wù)粒度的調(diào)度算法自適應(yīng)任務(wù)粒度自適應(yīng)任務(wù)粒度的核心思想是,當(dāng)所有線程都繁忙時就不產(chǎn)生任務(wù),直到有線程空閑需要任務(wù)時,繁忙線程再產(chǎn)生任務(wù)Cut-Off策略Cut-Off策略通常指定在派生樹(或函數(shù)調(diào)用樹)上的一個遞歸深度,當(dāng)超過這個深度時,不產(chǎn)生

任務(wù)24Cut-Off策略的5種實現(xiàn)方法方法1.程序員提供一個cut-off遞歸深度,或運行時系統(tǒng)設(shè)置一個缺省的深度.這種方法簡單,但不能適應(yīng)環(huán)境變化.方法2.運行時系統(tǒng)根據(jù)當(dāng)前任務(wù)隊列的大小設(shè)置cut-off深度,從而控制任務(wù)粒度.但是這種方法需要程序員設(shè)置串行程序的閾值,并且進行手動的性能調(diào)優(yōu)25Cut-Off策略的5種實現(xiàn)方法方法3.首先進行工作集輪廓信息收集,然后用收集后的信息執(zhí)行cut-off方法4.運行時系統(tǒng)支持的自適應(yīng)cut-off技術(shù)

運行時系統(tǒng)收集每一層產(chǎn)生的任務(wù)數(shù),如果任務(wù)數(shù)大于