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

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

2、 pb*; int *pc 動(dòng)態(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的過(guò)程可分為四個(gè)獨(dú)立的部分： Ai B = Ci，i = 1, 2, 3, 4 每部分包含的運(yùn)算可由一臺(tái)處理機(jī)單獨(dú)完成 矩陣較大時(shí)，

4、需分開(kāi)存放，即Ai,Bi,Ci放在結(jié)點(diǎn)i上 每個(gè)結(jié)點(diǎn)的工作分為AiB1,AiB2,AiB3,AiB4四個(gè)部分,9,矩陣乘法的并行程序,共享存儲(chǔ) 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; ,共享存儲(chǔ)并行程序 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,常見(jiàn)的共享存儲(chǔ)系統(tǒng),12,常見(jiàn)的共享存儲(chǔ)系統(tǒng)體系結(jié)構(gòu),無(wú)CACHE結(jié)構(gòu) 集中式共享存儲(chǔ)，無(wú)CACHE一致性問(wèn)題，可伸縮性有限，CRAY-XMP，YMP-C90 共享總線結(jié)構(gòu) 集中式共享存儲(chǔ)，偵聽(tīng)總線維護(hù)一致性，可伸縮性有限，DEC，SUN，SEQUENT，SGI等公司的SMP產(chǎn)品 CC-NUMA結(jié)構(gòu) 分布式共享存儲(chǔ)，通過(guò)目錄協(xié)議等維護(hù)一致性，DASH, Alewife, Origin 2000等 NCC-NUMA結(jié)構(gòu) 以Cray-T3D及T3E為代表，硬件提供共享存儲(chǔ)，但不負(fù)責(zé)維護(hù)一致性，可伸縮性好，可達(dá)上千個(gè)處理機(jī) COMA結(jié)構(gòu) 存儲(chǔ)單元與物理地址分離，數(shù)據(jù)可以動(dòng)態(tài)地在各結(jié)

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

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

10、儲(chǔ)系統(tǒng)的指令相關(guān),15,在單機(jī)系統(tǒng)中，只要保持程序中的數(shù)據(jù)相關(guān)性，就可以保證執(zhí)行正確。在多處理機(jī)系統(tǒng)中，不僅要考慮單機(jī)內(nèi)的數(shù)據(jù)相關(guān)，而且要考慮多機(jī)之間的數(shù)據(jù)相關(guān) 為了執(zhí)行的正確性，每個(gè)處理機(jī)都必須根據(jù)程序序來(lái)執(zhí)行指令 Process P1 Process P2 STORE a, 1 STORE b, 1 LOAD R1,b LOAD R2,a (Incorrect Result: R1=0,R2=0),一致性問(wèn)題,16,一致性問(wèn)題（cont.）,即使每個(gè)處理機(jī)都根據(jù)程序序執(zhí)行指令，仍可能導(dǎo)致錯(cuò)誤結(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 什么是寫(xiě)可分割系統(tǒng)中正確的執(zhí)行？ 存儲(chǔ)一致性模型和Cache一致性協(xié)議,17,什么是正確的執(zhí)行？,正確性標(biāo)準(zhǔn)：符合程序員的直覺(jué) 正確性規(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”. 如果在多處理機(jī)環(huán)境下的一個(gè)并行執(zhí)行的結(jié)果等于同一程序在單處理機(jī)多進(jìn)程環(huán)境下的一個(gè)執(zhí)行的結(jié)果，則此并行程序執(zhí)行正確,18,并行程序模型,程序模型 一個(gè)進(jìn)程P是一個(gè)二元組，其中V(P)是LOAD和STORE指令的集合，PO(P)是V(P)上的一個(gè)全序關(guān)系 由N個(gè)進(jìn)程P1,P2,Pn組成的程序PRG(P1,P2,Pn)是一個(gè)二元組，其中V(PRG)=V(P1) V(P2).V(Pn)是程序PRG的指令集，PO(PRG)=PO(P1) P

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

14、共享存儲(chǔ)系統(tǒng)的訪存事件次序,22,滿足順序一致的訪存事件次序,順序一致的一個(gè)充分條件（GPPO條件） 在共享存儲(chǔ)多處理機(jī)中，若任一處理機(jī)都嚴(yán)格按照訪存指令在進(jìn)程中出現(xiàn)的次序執(zhí)行，且在當(dāng)前訪存指令徹底執(zhí)行完之前不能開(kāi)始執(zhí)行下一條訪存指令，則此共享存儲(chǔ)系統(tǒng)是順序一致的 一個(gè)存數(shù)操作“徹底完成”指的是它所引起的值的變化已被所有處理機(jī)所接受， 一個(gè)取數(shù)操作徹底完成是指它取回的值已確定，且寫(xiě)此值的存數(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、存模型,寫(xiě)可分割系統(tǒng)的訪存事件模型 系統(tǒng)中有N個(gè)處理機(jī), 每個(gè)處理機(jī)執(zhí)行一個(gè)進(jìn)程。 任一訪存操作u被分割成N個(gè)子操作u1,u2,. , un, 其中ui表示u相對(duì)于Pi已執(zhí)行完(performed with respect to Pi)。 GPPO條件的描述 任一處理機(jī)都按訪存指令在進(jìn)程中出現(xiàn)的次序執(zhí)行，且在當(dāng)前訪存指令徹底執(zhí)行完之前不能開(kāi)始執(zhí)行下一條訪存指令 (u,v) PO = ui wi w1i rc wc rc 其中: c為執(zhí)行操作的處理機(jī)號(hào)，i,j=1,2,n 在寫(xiě)可分割系統(tǒng)中，若執(zhí)行E(PRG)滿足GPPO條件，則E(PRG)正確,24,順序一致系統(tǒng)中的亂序執(zhí)行,在順序一致系統(tǒng)中的

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

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

18、模型（Scope Consistency） 單項(xiàng)一致性模型（Entry Consistency） 從某種意義上說(shuō)，存儲(chǔ)一致性模型對(duì)共享存儲(chǔ)系統(tǒng)中多處理機(jī)的訪存次序作了限制，從而影響了性能,常見(jiàn)的存儲(chǔ)一致性模型,28,瞬間一致性模型（Atomic Consistency）,所有訪存操作同時(shí)被所有處理機(jī)觀察到 只有在集中式共享存儲(chǔ)系統(tǒng)中能實(shí)現(xiàn)，如總線結(jié)構(gòu)的系統(tǒng)采用偵聽(tīng)協(xié)議 與順序一致性的區(qū)別,29,順序一致性模型,正確性標(biāo)準(zhǔn)：符合程序員的直覺(jué) 正確性規(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”. 如果在多處理機(jī)環(huán)境下的一個(gè)并行執(zhí)行的結(jié)果等于同一程序在單處理機(jī)多進(jìn)程環(huán)境下的一個(gè)執(zhí)行的結(jié)果，則此并行程序執(zhí)行正確,30,處理機(jī)一致性模型,由 Goodman 提出的處理機(jī)一致性（Processor Consistency）比順序一致性弱，處理機(jī)一致性對(duì)訪存事件發(fā)生次序施加的限制是： 在任一取數(shù)操作 LOAD允許被執(zhí)行之前，所有

20、在同一處理機(jī)中先于這一LOAD 的取數(shù)操作都已完成 在任一存數(shù)操作 STORE允許被執(zhí)行之前，所有在同一處理機(jī)中先于這一STORE 的訪存操作（包括LOAD 和STORE）都已完成 上述條件允許STORE之后的LOAD 越過(guò)STORE而執(zhí)行，放松了順序一致性模型對(duì)訪存次序的限制 實(shí)際上是把Write Buffer變得讓用戶可見(jiàn) 如：Store提交后在Write Buffer，還沒(méi)有寫(xiě)Cache/內(nèi)存，后面的Load已經(jīng)從Cache取回?cái)?shù)據(jù)，此時(shí)收到對(duì)Load訪問(wèn)Cache行的一個(gè)無(wú)效請(qǐng)求,31,同步操作在共享存儲(chǔ)系統(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ū)分開(kāi)來(lái)，只在同步點(diǎn)維護(hù)一致性 沖突訪問(wèn)必須用同步操作保護(hù) 訪存次序 同步操作的執(zhí)行滿足順序一致性條件 在任一普通訪存操作允許被執(zhí)行之前，所有在同一處理機(jī)中先于這一訪存操作的同步操作都已完成 在任一同步操作允許被執(zhí)行之前，所有在同一處理機(jī)中先于這一同步操作的普通訪存操

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

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

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

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

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