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

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

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

并行性表達(dá)

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

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

并行性表達(dá)

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

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

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

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

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

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

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

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

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