基于多核處置器的常見(jiàn)計(jì)算任務(wù)分析與優(yōu)化

1、基于多核處置器的常見(jiàn)計(jì)算任務(wù)分析與優(yōu)化摘要本文介紹了三種常見(jiàn)計(jì)算任務(wù)中針對(duì)多核處置器的性能分析與優(yōu)化設(shè)計(jì)的新技術(shù)，這三種常見(jiàn)計(jì)算任務(wù)別離是：普遍用于組合搜索與優(yōu)化的動(dòng)態(tài)計(jì)劃算法(DP,DynamicProgramming),普遍用于科學(xué)計(jì)算的矩陣計(jì)算，和集群(Cluster)如此傳統(tǒng)的并行計(jì)算技術(shù)。針對(duì)動(dòng)態(tài)計(jì)劃算法，從其一樣形式入手，介紹非持續(xù)多元?jiǎng)討B(tài)計(jì)劃算法在多核處置器環(huán)境下的一系列優(yōu)化技術(shù)；針對(duì)矩陣計(jì)算，介紹針對(duì)多核處置器環(huán)境的亂序調(diào)度算法；針對(duì)多核集群，分析了多核處置器對(duì)傳統(tǒng)集群技術(shù)帶來(lái)的性能，專門是通信性能上的阻礙。關(guān)鍵詞：多核、動(dòng)態(tài)計(jì)劃、集群、矩陣計(jì)算1引言人們追求計(jì)算能力的腳步從沒(méi)

2、有放緩，過(guò)去數(shù)十年的進(jìn)展證明了摩爾定律一一微處置器的性能將以指數(shù)方式增加，即每?jī)赡攴环??？墒悄壳暗募夹g(shù)已經(jīng)難以通過(guò)提高頻率來(lái)維持這種增加速度，一個(gè)要緊的問(wèn)題確實(shí)是過(guò)度產(chǎn)熱(overheat)問(wèn)題，和能耗問(wèn)題。因此，多核處置器設(shè)計(jì)應(yīng)運(yùn)而生，即在同一塊芯片上放置兩個(gè)乃至更多處置核心，通過(guò)將應(yīng)用程序的工作復(fù)雜分擔(dān)到不同的核心來(lái)提高應(yīng)用程序性能。這種處置器也被稱為片內(nèi)多處置器(CMP,ChipMultiprocessor)。本文2至4章將介紹多核處置器對(duì)三種常見(jiàn)計(jì)算任務(wù)的性能阻礙與相應(yīng)計(jì)算任務(wù)的優(yōu)化設(shè)計(jì)。這三種計(jì)算任務(wù)別離是普遍用于組合搜索與優(yōu)化的動(dòng)態(tài)計(jì)劃算法(DP,DynamicProgrammi

3、ng),普遍用于科學(xué)計(jì)算的矩陣計(jì)算，和集群(Cluster)如此傳統(tǒng)的并行計(jì)算技術(shù)。針對(duì)動(dòng)態(tài)計(jì)劃算法，從其一樣形式入手，介紹非持續(xù)多元?jiǎng)討B(tài)計(jì)劃算法在多核處置器環(huán)境下的一系列優(yōu)化技術(shù)；針對(duì)矩陣計(jì)算，介紹針對(duì)多核處置器環(huán)境的亂序調(diào)度算法；針對(duì)多核集群，分析了多核處置器對(duì)傳統(tǒng)集群技術(shù)帶來(lái)的性能，專門是通信性能上的阻礙。2動(dòng)態(tài)計(jì)劃算法的分析與優(yōu)化動(dòng)態(tài)計(jì)劃算法簡(jiǎn)介動(dòng)態(tài)計(jì)劃算法(DynamicProgramming,DP)是一種經(jīng)典的，且為人熟知的算法，用于解決各類組合搜索與優(yōu)化問(wèn)題，普遍應(yīng)用于任務(wù)調(diào)度、資源治理、自動(dòng)操縱、VLSI設(shè)計(jì)與生物醫(yī)學(xué)等應(yīng)用中。動(dòng)態(tài)計(jì)劃算法的核心是動(dòng)態(tài)計(jì)劃方程(組)，依照方程組

4、，若是每一個(gè)子問(wèn)題的解Di只依托于與其直接相鄰的子問(wèn)題的解，那么稱其為持續(xù)的(Serial),不然，若Di依托于多個(gè)非直接相鄰的子問(wèn)題的解，那么稱其為非持續(xù)的(Non-serial)；若是Di的函數(shù)式中只包括一個(gè)遞歸項(xiàng)，即形如Di=Max卞if(Dj),那么稱其為一元的(Monadic),不然，假設(shè)包括多于一個(gè)遞歸項(xiàng)的，那么稱其為多元的(Polyadic)。由此，咱們能夠?qū)?dòng)態(tài)計(jì)劃算法做出一下分類2:一元持續(xù)動(dòng)態(tài)計(jì)劃算法(serialmonadic),如單求解源最短路問(wèn)題的Dijkstra算法、0/1背包問(wèn)題；多元持續(xù)動(dòng)態(tài)計(jì)劃算法(serialpolyadic),如求解全數(shù)點(diǎn)對(duì)之間最短路的Fl

5、oyd;一元非持續(xù)動(dòng)態(tài)計(jì)劃算法(nonserialmonadic),如最長(zhǎng)公共子序列問(wèn)題、尋覓序列最優(yōu)相似比較的Smith-Waterman;多元非持續(xù)動(dòng)態(tài)計(jì)劃算法(nonserialpolyadic),如最優(yōu)矩陣添括號(hào)問(wèn)題、RNAC級(jí)結(jié)構(gòu)預(yù)測(cè)所利用的Zuker算法。在這種分類方式中，多元非持續(xù)動(dòng)態(tài)計(jì)劃算法最具有可并行性，一元非持續(xù)動(dòng)態(tài)計(jì)劃和多元持續(xù)動(dòng)態(tài)計(jì)劃算法次之，一元持續(xù)動(dòng)態(tài)計(jì)劃算法幾乎不具有可并行計(jì)算的部份。關(guān)于一元持續(xù)動(dòng)態(tài)計(jì)劃算法，咱們只能依托處置器內(nèi)部實(shí)現(xiàn)的動(dòng)態(tài)調(diào)度算法來(lái)實(shí)現(xiàn)簡(jiǎn)單的指令級(jí)并行，而關(guān)于多元非持續(xù)動(dòng)態(tài)計(jì)劃算法，那么能夠充分利用多核處置器的特性來(lái)提高其性能，2.2-2.6中

6、將介紹多元非持續(xù)動(dòng)態(tài)計(jì)劃算法在多核處置器上的一種優(yōu)化方式。動(dòng)態(tài)計(jì)劃方程(組)Zuker是非持續(xù)多元?jiǎng)討B(tài)計(jì)劃算法的一個(gè)典型例子，它是預(yù)測(cè)RNA二級(jí)結(jié)構(gòu)的基對(duì)最大化算法。對(duì)給定的RNA序列，令S(i,j)表示自索引i至j的RNA子序列折疊結(jié)果，其數(shù)值表示折疊后的最高基對(duì)數(shù)量或是最小自由能。其對(duì)應(yīng)的動(dòng)態(tài)計(jì)劃方程組如下：S(i+1,j-1)+1S(i,j) = S(i + 1,j)S(i ,j - 1)(2.1)max?S(i,k)+S(k+1,j)在那個(gè)方程組中，最后一個(gè)求最大值的等式確實(shí)是一個(gè)非持續(xù)多元?jiǎng)討B(tài)計(jì)劃計(jì)算進(jìn)程那個(gè)方程組所描述的子問(wèn)題間依托關(guān)系如圖所示S-1J-SC.2iSU.4jSflT

7、4-圖Zuker算法中子問(wèn)題計(jì)算依托關(guān)系為了方便進(jìn)行一樣性描述，能夠?qū)⒎浅掷m(xù)動(dòng)態(tài)計(jì)劃的動(dòng)態(tài)計(jì)劃方程組做寫作等式的樣子：(2.2)(2.3)r._mini?mi,j,nii,k+nik+B,j,0&i?mli,ja(i),i=j為了便于以后的描述，將那個(gè)地址的B設(shè)定為1,那么等式變成:mini4?ni,j,ni,k+mk+1,j,0i?mi,ja(i),i=j核外并行算法多核處置器繼承了傳統(tǒng)通用運(yùn)算機(jī)的存儲(chǔ)器結(jié)構(gòu)，處置器核心直接訪問(wèn)獨(dú)立的一級(jí)緩存，同一芯片上的處置器核心之間共享二級(jí)緩存，二級(jí)緩存之外是內(nèi)存和外部存儲(chǔ)。相鄰兩級(jí)存儲(chǔ)之間的速度相差了幾乎一個(gè)數(shù)量級(jí)，因此，低速存儲(chǔ)設(shè)備的訪問(wèn)速度可能造成

8、并行處置的瓶頸，即數(shù)據(jù)傳輸無(wú)法知足并行計(jì)算的吞吐量需求，致使處置器長(zhǎng)時(shí)刻空閑。在那個(gè)動(dòng)態(tài)計(jì)劃算法的設(shè)計(jì)中，內(nèi)存與二級(jí)緩存之間的傳輸速度會(huì)造成最要緊的性能缺失，因此需要一個(gè)核外(Out-of-Core)調(diào)度算法，或稱片外調(diào)度算法來(lái)解決數(shù)據(jù)傳輸?shù)膯?wèn)題。等式所描述的動(dòng)態(tài)計(jì)劃算法的子問(wèn)題解mi,j能夠表示為一個(gè)核外二維數(shù)組(Out-of-CoreArray,OCA),那個(gè)數(shù)組超級(jí)龐大，無(wú)法直接寄存在二級(jí)緩存中，需要置于內(nèi)存中。處置器核心計(jì)算時(shí)只需要那個(gè)數(shù)組中的一個(gè)片段即可，那個(gè)片段并非大，能夠直接寄存在二級(jí)緩存中，稱為(In-of-CoreArray,ICA)2。傳統(tǒng)的并行執(zhí)行模型是加載-計(jì)算-存儲(chǔ)(

9、Load-Compute-Store),即每一個(gè)核心先加載所需要的數(shù)據(jù)到二級(jí)緩存，然后計(jì)算，最后將計(jì)算結(jié)果存回內(nèi)存，其流程如圖所示。plloadcomputestorecomputei一loadcomputestoreloadcnimputeslire旌A9cuiiipuiestoreloadctmipuieiLureluadcuinpuic*即一pnllloadslureluadcumpLitc虱urcloadcompuRstoneloadconiputesiorc1Atime圖LoadComputeStore計(jì)算模型由于各個(gè)核心都獨(dú)立地向內(nèi)存索取數(shù)據(jù)，如此能夠帶來(lái)兩個(gè)問(wèn)題：1、內(nèi)存并發(fā)訪問(wèn)

10、能力不足以應(yīng)付所有核心并發(fā)的訪問(wèn)請(qǐng)求；2、不同核心需要相同數(shù)據(jù)時(shí)冗余的加載操作。為了解決那個(gè)問(wèn)題，算法中引入了輔助線程(helperthread)來(lái)解決那個(gè)問(wèn)題，即通過(guò)而外的線程來(lái)對(duì)內(nèi)存做統(tǒng)一調(diào)度來(lái)加速數(shù)據(jù)的吞吐。具體地說(shuō)，增加兩個(gè)輔助線程pn-1和pn來(lái)負(fù)責(zé)數(shù)據(jù)的調(diào)度，其流程如圖所示。plcompuiecomputecompute一compufecomputep2compuiecompulecom|xite.一compurecompute*：*-.pn-1loadJoadLoadload一IcuidSitorestore.一storestoreinp口Alime圖LocalReplaceme

11、ntModel計(jì)算模型其中，線程pn-1負(fù)責(zé)加載數(shù)據(jù)，線程像負(fù)責(zé)將計(jì)算結(jié)果寫回內(nèi)存圖所展現(xiàn)的計(jì)算模型被稱作本地替換模型(LocalReplacementModel)2,其含義是負(fù)責(zé)計(jì)算的核心不需要考慮數(shù)據(jù)的加載與存儲(chǔ)，只需要從二級(jí)緩存(本地)中讀取數(shù)據(jù)，計(jì)算并寫回二級(jí)緩存（替換）即可，一個(gè)同步周期終止時(shí)，輔助線程Pn-1會(huì)將下一次計(jì)算所需要的數(shù)據(jù)預(yù)備好，同時(shí)Pn會(huì)將這次計(jì)算的結(jié)果寫回（替換）內(nèi)存。采納新的計(jì)算模型會(huì)帶來(lái)兩個(gè)益處：1、縮短計(jì)算時(shí)刻，參考圖與圖，新的計(jì)算模型通過(guò)借助空閑的線程單元（ThreadUnit）統(tǒng)一調(diào)度，幸免計(jì)算線程之間由于資源爭(zhēng)搶帶來(lái)的性能損失，通過(guò)對(duì)同步周期內(nèi)計(jì)算任務(wù)粒

12、度的合理設(shè)置，能夠使得Load/Store與Compute能在幾乎相同的時(shí)刻內(nèi)完成，使計(jì)算任務(wù)能充分并行化。2、由于Load與Store操作是并行執(zhí)行的，能夠保證Compute任務(wù)在一個(gè)同步周期終止后無(wú)需等待就能夠進(jìn)入下一周期的執(zhí)行，這等效于將二級(jí)緩存中可用于計(jì)算的核內(nèi)數(shù)組ICA的大小增加兩倍。那個(gè)地址假定二級(jí)緩存足夠大，至少三倍于一個(gè)周期內(nèi)所需ICA的大小，那么在每一個(gè)周期中，二級(jí)緩存內(nèi)有一份ICA正從內(nèi)存中加載入二級(jí)緩存，有一份ICA正在用于計(jì)算，還有一份ICA正被寫回內(nèi)存（pn線程不需要Store整份ICA,只需要將計(jì)算結(jié)果相關(guān)的部份寫回）。數(shù)據(jù)依托性的改良關(guān)于并行矩陣運(yùn)算，分塊（Blo

13、ck）技術(shù)是一種常規(guī)優(yōu)化技術(shù)，它是利用空間局部性來(lái)優(yōu)化程序性能，同時(shí)，合理的分塊也能作為并行計(jì)算任務(wù)的粒度大小。依照等式，其計(jì)算時(shí)的依托關(guān)系如圖所示。黑點(diǎn)表示所要計(jì)算的mi,j,連線表示計(jì)算中涉及的數(shù)對(duì)（pair）,注意紅點(diǎn)和灰點(diǎn)的散布就會(huì)發(fā)覺(jué)那個(gè)地址顯現(xiàn)了跨塊引用（CrossBlockReference）問(wèn)題。圖傳統(tǒng)動(dòng)態(tài)計(jì)劃算法計(jì)算依托關(guān)系在理想情形下，計(jì)算一個(gè)mi,j所只涉及橫向與縱向各n個(gè)塊，可是由于公式中B的存在，會(huì)顯現(xiàn)計(jì)算mi,j涉及橫向n個(gè)塊和縱向n+1個(gè)塊。由于計(jì)算進(jìn)程中，計(jì)算所需要的數(shù)據(jù)是通過(guò)輔助線程以塊為單位加載入二級(jí)緩存，那個(gè)額外的一個(gè)塊會(huì)增加輔助線程pni的工作量（pn只

14、需要寫回計(jì)算結(jié)果所在的塊），因此需要做一次數(shù)據(jù)依托轉(zhuǎn)換（datadependencetransformation）,以減小計(jì)算時(shí)的數(shù)據(jù)傳輸量。具體地說(shuō)，關(guān)于等式，咱們對(duì)矩陣內(nèi)個(gè)元素的坐標(biāo)做以下轉(zhuǎn)換：(2.4)(i,j)=f(i,j)：i=i,j=j+1取得新的動(dòng)態(tài)計(jì)劃方程組:minj +1詠 ? mi ,j , mi ,k + mk,j , 0&i a(i ), i = j ? 2:U包口 L_Oti.iRi0f2.inc2.2_。吧1口1 ijE&產(chǎn) i,叱函，口 g,。/函，口 1g ,g j ,。 口鼻11皿也門】再 門三；2二。2再門2,0 g 1 ,J * ， m；加Ca.2 一02

15、,1門2After Erst 口pmtionfter third oprrHtionAfter sixth operationInhi/oul仃i刀M0f2.0 Vcei,oOfi.l v0tl門北Ci l v,Of?;2fTtl.lQljf2.lCt2,jr2,2ft2,2Inln/out門 1. L %，a i式 Vj門a iV豆”V鼠.Lt3,1Ct2,lt3,2aj.sInJn/out.Cl-丁PriJf2l l/32,1門工2 /g2圖Tomasulo算法應(yīng)用于對(duì)一個(gè)3x3的向量矩陣進(jìn)行Cholesky分解的例如。Tomasulo算法成立一張表用于保留所有的計(jì)算操作，和操作所需要的輸

16、入與對(duì)應(yīng)的輸出，一旦輸入或輸出可歷時(shí)就以，標(biāo)記。當(dāng)所有參數(shù)都檢查有效時(shí)，操作就會(huì)被調(diào)度執(zhí)行，當(dāng)執(zhí)行完成后，操作的輸出變量就會(huì)被標(biāo)記為有效，而且在整個(gè)表中查找是不是有其他操作以那個(gè)輸出變量作為計(jì)算參數(shù)，將其標(biāo)記為可用。顯然，Tomasulo算法將程序變成一個(gè)亂序(Out-of-Order)執(zhí)行的操作序列。Tomasulo算法為計(jì)算提供了系統(tǒng)級(jí)的并行性支持，而且這種支持是不考慮算法具體以何種方式實(shí)現(xiàn)，是基于標(biāo)量的仍是基于塊的。但是對(duì)矩陣計(jì)算的亂序調(diào)度執(zhí)行盡管也是提供了系統(tǒng)級(jí)支持，但必需是以塊為方式來(lái)計(jì)算，因?yàn)檎{(diào)度算法是在軟件層面實(shí)現(xiàn)的，以標(biāo)量作為計(jì)算單位顯然不是一個(gè)合理的粒度。目前的矩陣計(jì)算亂序調(diào)

17、度算法大體是沿用了Tomasulo算法，將原有的以塊為單位的計(jì)算函數(shù)稍做修改，改對(duì)直接子矩陣塊的計(jì)算為加入一個(gè)等待計(jì)算隊(duì)列，由軟件層的調(diào)度算法來(lái)動(dòng)態(tài)分派計(jì)算資源，對(duì)多核處置器來(lái)講確實(shí)是分派處置器核心或線程單元。仿照?qǐng)D中的Tomasulo算法的表形式，基于塊的算法的亂序調(diào)度進(jìn)程如圖所示。OriginstableAfter first operationAfter third uperatianOperationIrbJln/outInIn mHLnInI ；HOL(40,o)題2中,2a。,。/氏加田/14 TRII1(4i,o l.nJ1.(?di，J1.011J】一“王 1. 11 1 .H

18、l用1 l,U2,0白IQ J4a.iV.4士 - -1 J.n-4j.tjL-h.fj-2.2 /1二二J達(dá)JCHOLt4i.J1.1W J且 ,】Hi.l事,3.1公1p2.3-la.L-2.3. la工hole./2,2 _3x2電,2nln/out-41.11/JH,2.1T,Jl/Ha，修丸aAfter sixth operation圖針對(duì)基于塊的3X3矩陣Cholesky分解算法的Tomasulo調(diào)度算法例如3與Tomasulo算法相同，這種調(diào)度算法在混合了動(dòng)態(tài)調(diào)度和亂序執(zhí)行的同時(shí)，也保證了計(jì)算中的數(shù)據(jù)依托關(guān)系對(duì)函數(shù)庫(kù)的開(kāi)發(fā)者與利用者都是透明的，類似于一種檢查者-執(zhí)行者（inspe

19、ctor-executor）模式的并行方式。新的調(diào)度算法將矩陣并行計(jì)算的并行性從傳統(tǒng)的操縱流并行（受到代碼中操作順序的限制）提升到數(shù)據(jù)流并行，使計(jì)算僅僅受到真數(shù)據(jù)有關(guān)和資源可用性的阻礙。4多核處置器對(duì)集群性能的阻礙在過(guò)去的數(shù)十年間，集群（Cluster）已經(jīng)成為最流行的并行計(jì)算模型，隨著多核體系結(jié)構(gòu)的進(jìn)展，集群也被帶入了多核領(lǐng)域。目前，愈來(lái)愈多的集群采納多核處置器構(gòu)建，2006年11月發(fā)布的全世界超級(jí)運(yùn)算機(jī)Top500中，已經(jīng)有20%勺處置器采納Intel和AMD制造的多核處置器。多核技術(shù)的引入為集群的性能帶來(lái)了新的阻礙1。多核集群NUMAl*based DesignIntra-CMP 由CM

20、PBus-based DesignIntra-CMP1CoreL2匚且由省GoreIL2Coto GotL2 CactieCoto CoreL2 CacheDll a Cb liJMemoryMemoiyMemoryIf tr-NodeJNetwork圖典型多核集群，左側(cè)為基于NUMANon-UniformMemoryAccess,非一致內(nèi)存訪問(wèn)）CM呦置器，右邊為基于總線的共享的CM呦置器目前，采納多核處置器的集群運(yùn)算機(jī)有兩種設(shè)計(jì)：基于NUMNE一致內(nèi)存訪問(wèn)的設(shè)計(jì)與基于總線的設(shè)計(jì)。兩種設(shè)計(jì)的不同在于，在基于NUMA勺設(shè)計(jì)中，每一個(gè)處置器核心擁有獨(dú)立的二級(jí)緩存，每一個(gè)處置器用用獨(dú)立的內(nèi)存；而在

21、基于總線的設(shè)計(jì)中，每一個(gè)處置器中的計(jì)算核心共享一個(gè)二級(jí)緩存，同一個(gè)節(jié)點(diǎn)（同一臺(tái)計(jì)算）內(nèi)的處置器共享內(nèi)存。在整個(gè)集群內(nèi)，能夠混合利用基于不同設(shè)計(jì)的運(yùn)算機(jī)。采納多核處置器的集群系統(tǒng)中，一共包括三層通信，如圖所示。在同一處置器上不同核心之間的通信稱作CMP內(nèi)通信(intra-CMPcommunication),在同一節(jié)點(diǎn)內(nèi)不同處置器之間的通信稱作CMPW通彳B(inter-CMPcommunication),CM訥通彳t與CMPi通信合稱為節(jié)點(diǎn)內(nèi)通信，而在集群內(nèi)的不同節(jié)點(diǎn)間的通信稱作節(jié)點(diǎn)間通信(inter-nodecommunication)。與傳統(tǒng)的集群系統(tǒng)相較，多核集群增加了CMP內(nèi)通信，對(duì)中間

22、件軟件與應(yīng)用軟件的設(shè)計(jì)提出了新的挑戰(zhàn)1。多核集群的性能測(cè)試測(cè)試環(huán)境測(cè)試?yán)肕PI作為編程模型，MPI是一個(gè)事實(shí)上的工業(yè)標(biāo)準(zhǔn)(defactostandard)，測(cè)試中利用基于InfiniBand和其他支持遠(yuǎn)程直接內(nèi)存訪問(wèn)(RDMA,RemoteDirectMemoryAccess)互聯(lián)技術(shù)的高性能的MPI-2實(shí)現(xiàn)MVAPICH2乍為MPI類庫(kù)。測(cè)試環(huán)境為以InfiniBand互聯(lián)的IntelBensley系統(tǒng)，每一個(gè)節(jié)點(diǎn)配置了兩顆雙核2.6GHzWoodcrest處置器，每顆處置器上的兩個(gè)核心之間共享4M屋級(jí)緩存，整體結(jié)構(gòu)類似圖中右邊所示的基于總線的設(shè)計(jì)。采納的InfiniBand主機(jī)通道適配器

23、(HCA,HostChannelAdapter)為MellanoxMT25208DDR,利用的操作系統(tǒng)是。測(cè)試中，咱們采納pxq來(lái)表示集群配置，p表示集群內(nèi)的節(jié)點(diǎn)數(shù)量，q表示每一個(gè)節(jié)點(diǎn)內(nèi)的計(jì)算核心數(shù)量。延時(shí)與帶寬測(cè)試延時(shí)與帶寬測(cè)試的要緊項(xiàng)目是標(biāo)準(zhǔn)的乒乓延遲(Ping-pongLatency)與帶寬，同時(shí)測(cè)試多核集群中的三級(jí)通信：CMP內(nèi)、CMP間與節(jié)點(diǎn)內(nèi)。圖中顯示了被測(cè)多核集群中MPI在三級(jí)通信中的延遲與帶寬。小消息的延時(shí)別離是：CMP內(nèi)、CMP間和節(jié)點(diǎn)間，對(duì)應(yīng)的峰值帶寬別離是6684MB/s、1258MB/s和1532MB/s。Mmagv 5n即Mi+1 ntra-CMP t-卜帕 N5HP

24、 t-I RFde11H黜如蚓|一1而 ra 工 MP MrlvCMP1 r.l 一 囿除CMP(c) BandwidihSmall Mcssuje LalcncyL;i停 Message Liilciicy圖多核集群中三級(jí)通信的延時(shí)與帶寬，（a）小消息延時(shí)，（b）大消息延時(shí)，（c）帶寬1從圖中能夠發(fā)覺(jué)，借助Woodcrest處置器的共享二級(jí)緩存，中小尺寸消息的CM吶通信的性能明顯優(yōu)于CMP間通信和節(jié)點(diǎn)間通信，因?yàn)閷?duì)這種消息，若是通行緩存已經(jīng)位于Cache的話，CMP內(nèi)通信只需要兩個(gè)Cache操作即可。同時(shí)也不難發(fā)覺(jué)，盡管內(nèi)存的性能優(yōu)于網(wǎng)絡(luò)性能，可是對(duì)大尺寸消息的CMP可通信性能并非會(huì)好于節(jié)點(diǎn)

25、間通信，二者超級(jí)接近。這是由于節(jié)點(diǎn)內(nèi)通信（CMP內(nèi)與CMP間）采納的是共享緩沖，每次通信需要兩次內(nèi)存拷貝，另一方面，節(jié)點(diǎn)間通信利用InfiniBand與rendezvous協(xié)議提供的遠(yuǎn)程直接內(nèi)存訪問(wèn)操作，該協(xié)議提供了零拷貝與高性能方案。從測(cè)試結(jié)果額能夠看出，優(yōu)化節(jié)點(diǎn)內(nèi)通信的方式有兩種，其一是提高二級(jí)緩存的利用率，盡可能使通信緩存位于二級(jí)緩存內(nèi)，其二是通過(guò)適當(dāng)?shù)牟呗詼p少內(nèi)存拷貝。消息分發(fā)消息分發(fā)從兩個(gè)維度進(jìn)行測(cè)量，一個(gè)維度是通信通道，如在CMP內(nèi)通信、CMP間通信和節(jié)點(diǎn)間通信在整體通信中各自占的百分比，另一個(gè)維度是消息的大小。對(duì)消息分發(fā)性能的分析對(duì)操縱消息分發(fā)的中間件軟件開(kāi)發(fā)者來(lái)講是超級(jí)重要的，

26、對(duì)MPI的實(shí)現(xiàn)者來(lái)講，確實(shí)是優(yōu)化應(yīng)用程序的關(guān)鍵通信通道分派與消息尺寸。測(cè)試在4X4的配置下進(jìn)行。出5S尊韓陽(yáng)明口 I 口降QMP - Irter-CM1 O Infermfe egrallMessage Size (Bytes)O InfraXM1 , InferMP LJlntef-rode Qwal imaOdP - InisrCMP 口喻力0曲01(b I 口;山L VblUJlWNumberofMessages圖NAM星準(zhǔn)測(cè)試程序的消息分發(fā)1(a)NumberofMessages(b)Data%h)ine圖HPL基準(zhǔn)測(cè)試程序的消息分發(fā)1圖與圖為消息分發(fā)測(cè)試的測(cè)試結(jié)果，假定在應(yīng)用程序運(yùn)行

27、進(jìn)程中，一共有n個(gè)消息被傳輸，其中有m個(gè)消息在范圍(a,b之間，而在這m個(gè)消息內(nèi)，有ml個(gè)通過(guò)CM吶通信傳輸，有m2個(gè)通過(guò)CMPi通信傳輸，有m3個(gè)通過(guò)節(jié)點(diǎn)間通信傳輸，那么有：mlBarIntra-CMPa,b=mm2BarInter-CMpa,b=一mm3BarInter-node(a,b=mmPointOverall(a,b=n從圖中，咱們能夠看到NAM謨準(zhǔn)測(cè)試程序的大部份消息尺寸介于4KB與64KB之間，占總消息數(shù)量與字節(jié)數(shù)量的90蛆上，因此，優(yōu)化對(duì)中等尺寸消息的分發(fā)性能對(duì)NAMD準(zhǔn)測(cè)試程序的性能有總要阻礙。在4KB至64KB之間的消息中，有大約10%!過(guò)CM訥通信傳輸，30惱過(guò)CMP可

28、通信傳軍而有60%!過(guò)節(jié)點(diǎn)間通信傳輸。這種結(jié)果直觀地告知咱們，在集群環(huán)境下，一個(gè)進(jìn)程擁有的節(jié)點(diǎn)間對(duì)(peer)的數(shù)量多余節(jié)點(diǎn)內(nèi)對(duì)。關(guān)于圖中的測(cè)試樣例來(lái)講，一個(gè)進(jìn)程擁有1個(gè)CM訥對(duì)，2個(gè)CMPi對(duì)和15個(gè)節(jié)點(diǎn)間對(duì)，若是一個(gè)進(jìn)程與其他進(jìn)程通信的機(jī)遇都是相等的話，那么理論上CMP內(nèi)對(duì)、CMP間對(duì)和節(jié)點(diǎn)間對(duì)占的通信比例應(yīng)該別離是6.7%,13.3麻口80%可是與實(shí)際測(cè)試結(jié)果相較，會(huì)發(fā)覺(jué)節(jié)點(diǎn)內(nèi)通信占據(jù)的比例會(huì)高于理論數(shù)值，這說(shuō)明在集群環(huán)境內(nèi)對(duì)類似NAMD的應(yīng)用程序，優(yōu)化節(jié)點(diǎn)內(nèi)通信與優(yōu)化節(jié)點(diǎn)間通行一樣重要。從圖中能夠看出HPL基準(zhǔn)測(cè)試程序的大部份消息都是小尺寸消息，介于256B至4KB之間，可是大于256

29、KB的消息在數(shù)據(jù)總量(DataVolume)上卻占據(jù)了更多的份額。消息中的大部份是通過(guò)節(jié)點(diǎn)內(nèi)通信傳輸?shù)?。在HPL程序內(nèi)，每一個(gè)進(jìn)程處置同一列與同一行內(nèi)的數(shù)據(jù)，在集群環(huán)境中，這些行與列的數(shù)據(jù)都被映射到同一個(gè)節(jié)點(diǎn)內(nèi)，因此，大部份通信集中在節(jié)點(diǎn)內(nèi)。優(yōu)化節(jié)點(diǎn)內(nèi)通信的性能對(duì)類似HPL基準(zhǔn)測(cè)試程序的應(yīng)用程序來(lái)講，優(yōu)化節(jié)點(diǎn)內(nèi)通信對(duì)性能有更大的阻礙。潛在的緩存與內(nèi)存搶奪別離在1X4、2X2和4X1的配置下運(yùn)行基準(zhǔn)測(cè)試程序，以檢查系統(tǒng)中潛在的瓶頸。測(cè)試結(jié)果如圖所示，所有的執(zhí)行時(shí)刻依照在配置4X 1配置下的執(zhí)行時(shí)刻標(biāo)準(zhǔn)化fl)圖4進(jìn)程應(yīng)用程序在不同配置下的性能1在圖5中，大部份基準(zhǔn)測(cè)試程序在1X4配置的運(yùn)行情形不

30、如2X2與4X1配置是的情形，這是因?yàn)樵?x4配置時(shí)，所有的核心都被激活運(yùn)行。IntelBensley利用的Woodcrest核心之間共享二級(jí)緩存與內(nèi)存操縱器，因此緩存和內(nèi)存競(jìng)爭(zhēng)就組成了一個(gè)潛在瓶頸。內(nèi)存競(jìng)爭(zhēng)對(duì)位于不同芯片上的處置器來(lái)講不是問(wèn)題，因?yàn)镮ntelBensley系統(tǒng)特殊的總線結(jié)構(gòu)能夠讓每一個(gè)芯片具有更大的內(nèi)存帶寬，這確實(shí)是什么緣故2X2與4X1配置運(yùn)行的差不多。一樣的趨勢(shì)也出此刻圖中，在那個(gè)樣例中，咱們別離在同芯片上的核心上、兩個(gè)芯片間和兩個(gè)節(jié)點(diǎn)間這三種環(huán)境中運(yùn)行一個(gè)雙進(jìn)程的應(yīng)用程序。咱們能夠看到，CMP間與節(jié)點(diǎn)間的性能相當(dāng)，同時(shí)高于CMP內(nèi)執(zhí)行的性能。這組測(cè)試結(jié)果標(biāo)明，想要充分發(fā)

31、揮多核體系結(jié)構(gòu)的又是，通信中間件與應(yīng)用程序都需要針對(duì)多核環(huán)境進(jìn)行設(shè)計(jì)，即multi-coreaware的設(shè)計(jì)，以減少緩存與內(nèi)存的爭(zhēng)用情形。通信中間件需要幸免盡可能緩存污染(cachepollution),如增加通信緩沖(communicationbuffer)的重用，利用緩存旁路內(nèi)存拷貝(cachebypassmemorycopy),活著排除中間緩沖(intermediatebuffer)。應(yīng)用程序那么需要通過(guò)優(yōu)化增加數(shù)據(jù)的局部性。數(shù)據(jù)分塊(datatiling)是一種常見(jiàn)的減少非必需內(nèi)存?zhèn)鬏數(shù)募夹g(shù)。若是一個(gè)大數(shù)據(jù)緩沖需要被多次處置，那么能夠?qū)⑵洳鸱殖尚K后對(duì)小塊數(shù)據(jù)進(jìn)行處置，如此能夠幸免每次

32、都對(duì)整個(gè)數(shù)據(jù)緩沖進(jìn)行處置，而小塊數(shù)據(jù)能夠在多次處置進(jìn)程中始終保留在緩存內(nèi)8。1400電一Q2 一0 .IS FT CG MG LU NAMD HPLBenafmarf口intnbCMPinHCMP口Htenocfe圖2進(jìn)程應(yīng)用程序在不同配置下的性能1數(shù)據(jù)分塊(DataTiling)的優(yōu)勢(shì)圖顯示出數(shù)據(jù)分塊技術(shù)在不同配置情形下對(duì)性能的阻礙。被測(cè)應(yīng)用程序?qū)σ唤M64MB的數(shù)據(jù)進(jìn)行多次迭代處置，執(zhí)行進(jìn)程中，每一個(gè)進(jìn)程對(duì)其所有的數(shù)據(jù)進(jìn)行向量乘法，將結(jié)果發(fā)送向右邊的相鄰節(jié)點(diǎn)，并從左側(cè)的相鄰節(jié)點(diǎn)接收數(shù)據(jù)，然后進(jìn)行計(jì)算的下一次迭代。傳統(tǒng)的算法中，數(shù)據(jù)塊的大小是64MB而在數(shù)據(jù)分塊策略中，數(shù)據(jù)被拆分到256KB,以適應(yīng)二級(jí)緩存的大小。2 1 8 6 4 2 t a ft ft ft 爰1 558d noz0口Original DataTingi圖 數(shù)據(jù)分塊(Data Tiling )的成效從圖的結(jié)果能夠看出，數(shù)據(jù)分塊技術(shù)顯著縮短的執(zhí)行時(shí)刻，這是由于在節(jié)點(diǎn)內(nèi)通信利用基于CPU(CPU-based)的內(nèi)存拷貝，的256KB大小的數(shù)據(jù)在通信進(jìn)程中已經(jīng)預(yù)先加載入二級(jí)緩存中。引用LeiChaietal.UnderstandingtheImpactofMulti-CoreA