計算機組織與結(jié)構(gòu)：LEC11_多處理器

1、1,高性能計算機系統(tǒng)結(jié)構(gòu),2,多處理器,消息傳遞與共享存儲 常見的共享存儲系統(tǒng) 共享存儲系統(tǒng)的指令相關(guān) 共享存儲系統(tǒng)的訪存事件次序 存儲一致性模型 CACHE一致性協(xié)議,3,消息傳遞與共享存儲,4,消息傳遞與共享存儲,多地址空間 消息傳遞通訊 編程困難、程序移植困難 通用性差 可伸縮性好,單地址空間 共享存儲通訊 編程容易、程序易移植 通用性強 可伸縮性一般,5,共享存儲與消息傳遞的編程復(fù)雜度,任務(wù)劃分與數(shù)據(jù)劃分 共享存儲編程只需劃分任務(wù) 消息傳遞編程除了劃分任務(wù)外，還需劃分?jǐn)?shù)據(jù)和考慮通信 BBS與Email 傳遞復(fù)雜的數(shù)據(jù)結(jié)構(gòu)較困難 多個指針組成的結(jié)構(gòu) struct int *pa; int

2、 pb*; int *pc 動態(tài)通信 for (i,j) x=; y=; aij=bxy; 進(jìn)程遷移及進(jìn)程數(shù)目的變化,6,例子：積分求p,串行程序 h = 1.0/N; pi = 0; for(i=1; i=N; i+) temp = (i-0.5)*h; pi = pi + 4/(1+temp*temp); pi = pi * h; printf pi;,7,積分求p的并行程序,JIAJIA MPI,jia_init(argc,argv); pi=jia_alloc(8); h = 1.0/N; for(i=jiapid+1;i=N;i+=jiahosts) mypi = . jia_loc

3、k(1); pi += mypi; jia_unlock(1); printf pi; jia_exit();,MPI_Init(argc,argv); MPI_Comm_size(); MPI_Comm_rand(); h = 1.0/N; for(i=myid+1;i=N;i+=numprocs) mypi = . MPI_Reduce(mypi,pi,1. ); printf pi; MPI_Finalize();,8,并行程序例子：矩陣乘法,A B = C的過程可分為四個獨立的部分： Ai B = Ci，i = 1, 2, 3, 4 每部分包含的運算可由一臺處理機單獨完成 矩陣較大時，

4、需分開存放，即Ai,Bi,Ci放在結(jié)點i上 每個結(jié)點的工作分為AiB1,AiB2,AiB3,AiB4四個部分,9,矩陣乘法的并行程序,共享存儲 double (*a)N,(*b)N,(*c)N; a=jia_alloc(N*N*8); b=jia_alloc(.); c=jia_alloc(.); if (jiapid=0) for (i.) for (j) aij=1;bij=1; jia_barrier(); begin=N*jiapid/jiahosts; end=N*(jiapid+1)/jiahosts; for (i=begin; iend; i+) for (j=0; jN; j

5、+) for (k=0; kN; k+) cij+=aik*bkj; jia_barrier(); if (jiapid=0) printf C; jia_exit();,消息傳遞 double (*a)N,(*b)N,(*c)N; a=malloc2(N*N*8); b=malloc2(.); c=malloc(.); if (mypid=0) init a,b; send a,b； else recv a,b； for (i=0;iN/hosts;i+) for (j=0; jN; j+) for (k=0; kN; k+) cij+=aik*bkj; if (mypid!=0) send

6、 c; else recv c; printf c;,10,并行程序的例子：圖象糾正,串行程序 for (i=0;ilin2;i+) for (j=0;jcol2;j+) x=P(i,j,); y=P(i,j,); outi,j=inxy; ,共享存儲并行程序 start=lin2/jiahosts*jiapid; end=start+lin2/jiahosts; if (jiapid=jiahosts) end=lin2; for (i=start;iend;i+) for (j=0;jcol2;j+) x=P(i,j,); y=P(i,j,); outi,j=inxy; jia_barri

7、er();,11,常見的共享存儲系統(tǒng),12,常見的共享存儲系統(tǒng)體系結(jié)構(gòu),無CACHE結(jié)構(gòu) 集中式共享存儲，無CACHE一致性問題，可伸縮性有限，CRAY-XMP，YMP-C90 共享總線結(jié)構(gòu) 集中式共享存儲，偵聽總線維護(hù)一致性，可伸縮性有限，DEC，SUN，SEQUENT，SGI等公司的SMP產(chǎn)品 CC-NUMA結(jié)構(gòu) 分布式共享存儲，通過目錄協(xié)議等維護(hù)一致性，DASH, Alewife, Origin 2000等 NCC-NUMA結(jié)構(gòu) 以Cray-T3D及T3E為代表，硬件提供共享存儲，但不負(fù)責(zé)維護(hù)一致性，可伸縮性好，可達(dá)上千個處理機 COMA結(jié)構(gòu) 存儲單元與物理地址分離，數(shù)據(jù)可以動態(tài)地在各結(jié)

8、點間移動和復(fù)制，每個結(jié)點的存儲器相當(dāng)于一個大容量CACHE，數(shù)據(jù)一致性也在這一級維護(hù)，KSR，DDM等 虛擬共享存儲系統(tǒng) 在基于消息傳遞的多計算機或機群中，用軟件的方法把多個獨立編址的存儲器轉(zhuǎn)化為一個統(tǒng)一編址的共享虛擬存儲空間，IVY, Midway, Munin, TreadMarks, JIAJIA等,13,共享存儲與消息傳遞發(fā)展趨勢,1970年代到1980年代中期，并行系統(tǒng)主要是SMP與向量機，結(jié)點個數(shù)不多（4-8路），是科學(xué)計算、事務(wù)處理、服務(wù)器領(lǐng)域的主要產(chǎn)品 由于SMP與向量機可伸縮性差，1990年代消息傳遞的MPP興起，主要用于科學(xué)計算，同時NUMA系統(tǒng)的研究全面展開，如DASH，

9、Alewife，KSR-1等 1990年代后期，由于解決了伸縮性問題，以O(shè)rigin 2000為標(biāo)志，中規(guī)模和大規(guī)模的共享存儲興起，SUN的Starfile，Compaq的Wildfire, 及IBM的NUMA-Q 目前主流的服務(wù)器均采用共享存儲，低端服務(wù)器由處理器提供直接互連形成2-4路系統(tǒng)；高端服務(wù)器通過橋片連接形成幾十路的系統(tǒng) 以科學(xué)計算為目的大規(guī)模MPP系統(tǒng)仍以消息傳遞為主，幾千到上萬個處理機，隨著帶寬的增加與用戶級通信的發(fā)展，機群系統(tǒng)與MPP系統(tǒng)的界限越來越模糊 主流商業(yè)片內(nèi)多核都采用共享存儲系統(tǒng)，甚至分布式共享存儲系統(tǒng)；片內(nèi)眾核（幾百到上千核）如GPU結(jié)構(gòu)采用獨立內(nèi)存,14,共享存

10、儲系統(tǒng)的指令相關(guān),15,在單機系統(tǒng)中，只要保持程序中的數(shù)據(jù)相關(guān)性，就可以保證執(zhí)行正確。在多處理機系統(tǒng)中，不僅要考慮單機內(nèi)的數(shù)據(jù)相關(guān)，而且要考慮多機之間的數(shù)據(jù)相關(guān) 為了執(zhí)行的正確性，每個處理機都必須根據(jù)程序序來執(zhí)行指令 Process P1 Process P2 STORE a, 1 STORE b, 1 LOAD R1,b LOAD R2,a (Incorrect Result: R1=0,R2=0),一致性問題,16,一致性問題（cont.）,即使每個處理機都根據(jù)程序序執(zhí)行指令，仍可能導(dǎo)致錯誤結(jié)果 Process P1 Process P2 Process P3 STORE a,1 LOAD

11、 R1,a LOAD R2,b STORE b,1 LOAD R3,a (Incorrect result: R1=1,R2=1, R3=0) 起因：從Write Nonatomic到Write Atomic 什么是寫可分割系統(tǒng)中正確的執(zhí)行？ 存儲一致性模型和Cache一致性協(xié)議,17,什么是正確的執(zhí)行？,正確性標(biāo)準(zhǔn)：符合程序員的直覺 正確性規(guī)范：順序一致性 Sequential consistency defines a correct execution as the one “whose result is the same as if the operations of each in

12、dividual processor appear in this sequence in the order specified by the program”. 如果在多處理機環(huán)境下的一個并行執(zhí)行的結(jié)果等于同一程序在單處理機多進(jìn)程環(huán)境下的一個執(zhí)行的結(jié)果，則此并行程序執(zhí)行正確,18,并行程序模型,程序模型 一個進(jìn)程P是一個二元組，其中V(P)是LOAD和STORE指令的集合，PO(P)是V(P)上的一個全序關(guān)系 由N個進(jìn)程P1,P2,Pn組成的程序PRG(P1,P2,Pn)是一個二元組，其中V(PRG)=V(P1) V(P2).V(Pn)是程序PRG的指令集，PO(PRG)=PO(P1) P

13、O(P2).PO(Pn)是程序PRG的程序序 沖突訪問的概念 如果兩個訪存操作訪問的是同一單元且其中至少有一個是存數(shù)操作, 則稱這兩個訪存操作是沖突的。 C(PRG)=(u,v)|(u,v)V(PRG)(u,v是沖突訪問)稱為程序PRG中沖突訪問對集,19,程序執(zhí)行的正確性,執(zhí)行的概念 在在一個并行執(zhí)行中，一旦互相沖突的訪問的執(zhí)行次序確定了。那么執(zhí)行結(jié)果也就確定了 在程序PRG中, 對沖突訪問對集C(PRG)的任一無圈定序稱為程序PRG的一個執(zhí)行，記為E(PRG)。 執(zhí)行的正確性 程序PRG的執(zhí)行E(PRG)正確的充要條件是E(PRG) PO(PRG)無圈。,20,正確與錯誤的程序執(zhí)行,21,

14、共享存儲系統(tǒng)的訪存事件次序,22,滿足順序一致的訪存事件次序,順序一致的一個充分條件（GPPO條件） 在共享存儲多處理機中，若任一處理機都嚴(yán)格按照訪存指令在進(jìn)程中出現(xiàn)的次序執(zhí)行，且在當(dāng)前訪存指令徹底執(zhí)行完之前不能開始執(zhí)行下一條訪存指令，則此共享存儲系統(tǒng)是順序一致的 一個存數(shù)操作“徹底完成”指的是它所引起的值的變化已被所有處理機所接受， 一個取數(shù)操作徹底完成是指它取回的值已確定，且寫此值的存數(shù)操作已“徹底完成” Process P1 Process P2 Process P3 STORE a,1 LOAD R1,a LOAD R2,b STORE b,1 LOAD R3,a,23,分布式系統(tǒng)的訪

15、存模型,寫可分割系統(tǒng)的訪存事件模型 系統(tǒng)中有N個處理機, 每個處理機執(zhí)行一個進(jìn)程。 任一訪存操作u被分割成N個子操作u1,u2,. , un, 其中ui表示u相對于Pi已執(zhí)行完(performed with respect to Pi)。 GPPO條件的描述 任一處理機都按訪存指令在進(jìn)程中出現(xiàn)的次序執(zhí)行，且在當(dāng)前訪存指令徹底執(zhí)行完之前不能開始執(zhí)行下一條訪存指令 (u,v) PO = ui wi w1i rc wc rc 其中: c為執(zhí)行操作的處理機號，i,j=1,2,n 在寫可分割系統(tǒng)中，若執(zhí)行E(PRG)滿足GPPO條件，則E(PRG)正確,24,順序一致系統(tǒng)中的亂序執(zhí)行,在順序一致系統(tǒng)中的

16、亂序執(zhí)行 如果訪存操作u和v是同一進(jìn)程Pi的兩個訪存操作且u在v之前，則在如下條件下v可先于u執(zhí)行而不影響程序正確性：在v發(fā)出之后u“徹底完成”之前的這段時間內(nèi)，沒有其他對v所訪問單元的訪問相對于Pi完成（如v所訪問單元在Pi中的備份不被更新） 例：Process 1 Process2 STORE a,1 STORE b,1 LOAD R1,b LOAD R2,a 亂序執(zhí)行的實現(xiàn)方法：猜測執(zhí)行 先往下執(zhí)行，收到相應(yīng)的invalidate信號再反悔,25,存儲一致性模型,26,存儲一致性模型（Memory Consistency）,歷史的觀點: Hardware-Centric 對多個處理機訪問

17、共享存儲器的次序的一些限制 弱一致性模型：放松限制來提高性能 程序員必須考慮訪存次序 系統(tǒng)設(shè)計者沒有優(yōu)化余地 正確的觀點: Programmer-Centric 結(jié)構(gòu)設(shè)計者與應(yīng)用程序員之間的一種約定 給出正確程序的標(biāo)準(zhǔn) 程序員不用考慮訪存次序 系統(tǒng)設(shè)計者有更多的提高性能的空間,27,常見的存儲一致性模型 瞬間一致性模型（Atomic Consistency） 順序一致性模型（Sequential Consistency） 處理器一致性模型（Processor Consistency） 弱一致性模型（Weak Ordering） 釋放一致性模型（Release Consistency） 域一致性

18、模型（Scope Consistency） 單項一致性模型（Entry Consistency） 從某種意義上說，存儲一致性模型對共享存儲系統(tǒng)中多處理機的訪存次序作了限制，從而影響了性能,常見的存儲一致性模型,28,瞬間一致性模型（Atomic Consistency）,所有訪存操作同時被所有處理機觀察到 只有在集中式共享存儲系統(tǒng)中能實現(xiàn)，如總線結(jié)構(gòu)的系統(tǒng)采用偵聽協(xié)議 與順序一致性的區(qū)別,29,順序一致性模型,正確性標(biāo)準(zhǔn)：符合程序員的直覺 正確性規(guī)范：順序一致性 Sequential consistency defines a correct execution as the one “who

19、se result is the same as if the operations of each individual processor appear in this sequence in the order specified by the program”. 如果在多處理機環(huán)境下的一個并行執(zhí)行的結(jié)果等于同一程序在單處理機多進(jìn)程環(huán)境下的一個執(zhí)行的結(jié)果，則此并行程序執(zhí)行正確,30,處理機一致性模型,由 Goodman 提出的處理機一致性（Processor Consistency）比順序一致性弱，處理機一致性對訪存事件發(fā)生次序施加的限制是： 在任一取數(shù)操作 LOAD允許被執(zhí)行之前，所有

20、在同一處理機中先于這一LOAD 的取數(shù)操作都已完成 在任一存數(shù)操作 STORE允許被執(zhí)行之前，所有在同一處理機中先于這一STORE 的訪存操作（包括LOAD 和STORE）都已完成 上述條件允許STORE之后的LOAD 越過STORE而執(zhí)行，放松了順序一致性模型對訪存次序的限制 實際上是把Write Buffer變得讓用戶可見 如：Store提交后在Write Buffer，還沒有寫Cache/內(nèi)存，后面的Load已經(jīng)從Cache取回數(shù)據(jù)，此時收到對Load訪問Cache行的一個無效請求,31,同步操作在共享存儲系統(tǒng)中的作用,積分求p jia_init(argc,argv); pi=jia_a

21、lloc(8); h = 1.0/N; pi = 0; for(i=jiapid+1;i=N;i+=jiahosts) mypi = . jia_lock(1); pi += mypi; jia_unlock(1); printf pi; jia_exit();,矩陣乘法 double (*a)N,(*b)N,(*c)N; a=jia_alloc(N*N*8); b=jia_alloc(.); c=jia_alloc(.); if (jiapid=0) for (i.) for (j) aij=1;bij=1; jia_barrier(); begin=N*jiapid/jiahosts; e

22、nd=N*(jiapid+1)/jiahosts; for (i=begin; iend; i+) for (j=0; jN; j+) for (k=0; kN; k+) cij+=aik*bkj; jia_barrier(); if (jiapid=0) printf C; jia_exit();,32,把同步操作和普通訪存操作區(qū)分開來，只在同步點維護(hù)一致性 沖突訪問必須用同步操作保護(hù) 訪存次序 同步操作的執(zhí)行滿足順序一致性條件 在任一普通訪存操作允許被執(zhí)行之前，所有在同一處理機中先于這一訪存操作的同步操作都已完成 在任一同步操作允許被執(zhí)行之前，所有在同一處理機中先于這一同步操作的普通訪存操

23、作都已完成,弱存儲一致性模型（Weak Ordering）,33,釋放一致性模型（Release Consistency）,把同步操作進(jìn)一步分成獲取操作ACQUIRE和釋放操作RELEASE 沖突訪問必須用REL-ACQ對隔開 訪存次序 同步操作的執(zhí)行滿足順序一致性條件 在任一普通訪存操作允許被執(zhí)行之前，所有在同一處理機中先于這一訪存操作的ACQUIRE操作都已完成 在任一RELEASE操作允許被執(zhí)行之前，所有在同一處理機中先于這一RELEASE的普通訪存操作都已完成,34,域一致性模型（Scope Consistency）,沖突訪問必須用同一把鎖保護(hù),35,單項一致性模型（Entry Con

24、sistency）,必須為每一個共享變量指定相應(yīng)的鎖 加重了程序員的負(fù)擔(dān) 有利于性能,36,存儲一致性模型的一個框架模型,基本思想 對訪存事件的一個分類C一種同步機制SYN 對同步操作的一個定向稱為一個執(zhí)行E 正確的條件：由確定的訪存操作的偏序與程序序的并集無環(huán)路 對正確的實現(xiàn)的條件：所有執(zhí)行都正確 在順序一致性模型中，把普通訪存操作看作同步操作，則前面關(guān)于順序一致性的理論是該框架模型的一個特例,37,CACHE一致性協(xié)議,38,共享存儲多處理機中的Cache一致性問題,Cache在共享存儲系統(tǒng)中的作用 彌補CPU與主存間的速度差距 減少訪存沖突以及對互連網(wǎng)絡(luò)帶寬的需求 Cache一致性問題

25、如何保持?jǐn)?shù)據(jù)在Cache及主存中的多個備份的一致性,39,Cache一致性協(xié)議,Cache一致性協(xié)議（Cache Coherence Protocol）：一種把新寫的值傳播到其他處理機的機制 如何傳播新值：Write Invalidate vs. Write Update 誰可以產(chǎn)生新值：Single Writer vs. Multiple Writer 何時開始傳播新值：Early vs. Delayed Propagation 向何處傳播新值：Snoopy vs. Directory Protocol Cache一致性協(xié)議決定系統(tǒng)為維護(hù)一致性所做的具體動作，因而直接影響系統(tǒng)性能,40,Wr

26、ite-Invalidate和Write Update,Write-Invalidate 當(dāng)一個處理機更新某共享單位（如存儲行或存儲頁）時（之前或之后），通過某種機制使該共享單位的其它備份無效，當(dāng)其它處理機訪問該共享單位時，訪問失效，再取得有效備份 Write-Update 當(dāng)一個當(dāng)一個處理機更新某共享單位時，把更新的內(nèi)容傳播給所有擁有該共享單位備份的處理機 比較 Write Update: 重復(fù)更新已不再使用的行 Write Invalidate: 假共享導(dǎo)致乒乓問題,41,單寫和多寫,單寫：任一時刻只有一個處理機能寫某共享單位 多寫：多個處理機同時寫某共享單位的不同部分,42,急切更新與懶

27、惰更新,普通RC：邊寫邊傳輸寫操作 Eager RC：把寫操作延遲到Release時一起發(fā)出 Lazy RC：進(jìn)一步延遲到下一個Acquire時再傳輸 ERC和LRC是RC的不同實現(xiàn)，不是不同的一致性模型,43,偵聽協(xié)議,通過廣播維護(hù)一致性 寫數(shù)的處理機把新寫的值或所需的存儲行地址廣播出去 其他處理機偵聽廣播，當(dāng)廣播中的內(nèi)容與自己有關(guān)時，接受新值或提供數(shù)據(jù) 存儲器和每個處理機的Cache只維護(hù)狀態(tài)信息 適合于總線結(jié)構(gòu)的SMP系統(tǒng)中 總線是一種廉價而有效的廣播工具 可伸縮性有限 總線是一種獨占性資源 總線延遲隨處理機數(shù)的增加而增加：仲裁、總線長度、總線阻抗,44,基于目錄的協(xié)議,每個存儲行對應(yīng)一個目錄項 記錄擁有該行的一個副本的那些處理機 當(dāng)某個處理機寫該行時,根據(jù)目錄項的內(nèi)容傳播數(shù)據(jù) 在COMA結(jié)構(gòu)中，記錄該行的Owner 由于避免了廣播，目錄協(xié)議有一定的伸縮性 目錄需要大量存儲空間,