《并行計(jì)算機(jī)系統(tǒng)》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(jì)算機(jī)系統(tǒng)（80頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,第八章 并行計(jì)算機(jī)系統(tǒng),第一節(jié) 并行計(jì)算機(jī)系統(tǒng)的分類,第二節(jié) 共享存儲(chǔ)器系統(tǒng),第三節(jié) 消息傳遞型系統(tǒng),第一節(jié) 并行計(jì)算機(jī)系統(tǒng)分類,向量機(jī)系統(tǒng),流水式向量機(jī)系統(tǒng),陣列式向量機(jī)系統(tǒng),多處理機(jī)系統(tǒng),共享存儲(chǔ)器型,消息傳遞型,并行性的層次,操作級(jí),流水,數(shù)據(jù)并行,指令級(jí),相關(guān)性分析,指令調(diào)度,循環(huán)級(jí),展開(kāi),推測(cè)執(zhí)行,路徑調(diào)度,線程級(jí),并行多線程、多核與多處理器,數(shù)據(jù)緩存的一致性,同步與互斥的有效性,系統(tǒng)結(jié)構(gòu)分類,Flyn,分類,向量流水,部件級(jí)流水,一條指令完成大量計(jì)算,對(duì)應(yīng)于一個(gè)循環(huán),每個(gè)數(shù)據(jù)元素的計(jì)算與其他數(shù)

2、據(jù)元素?zé)o關(guān),適合于深度流水,訪存按一定模式,一次訪問(wèn)大量數(shù)據(jù),向量流水計(jì)算機(jī),向量指令,向量-向量指令,ADDV V1,V2,V3,向量-標(biāo)量指令,ADDV V1,F2,V3,向量-存儲(chǔ)器指令,LV V1,R1,向量歸約指令,MAX F0,V1,收集-擴(kuò)展指令,（,Gather-Scatter）,屏蔽指令,SENSV F0,V1,向量流水計(jì)算機(jī)的例子,Cray-1,陣列并行計(jì)算機(jī)系統(tǒng),基本結(jié)構(gòu),分布式存儲(chǔ)器,集中式存儲(chǔ)器,運(yùn)行方式,用一條指令同時(shí)對(duì)許多運(yùn)算單元中的數(shù)據(jù)進(jìn)行運(yùn)算,基本構(gòu)成,控制單元,CU,執(zhí)行串行指令，并行指令廣播各個(gè),PE；,處理單元,PE,以同步方式執(zhí)行指令,存儲(chǔ)器模塊,互連

3、網(wǎng)絡(luò),IN,集中式控制，并行電路交換,陣列并行指令,向量運(yùn)算，數(shù)據(jù)尋徑，屏蔽操作,陣列并行計(jì)算機(jī)系統(tǒng),陣列并行計(jì)算機(jī)系統(tǒng),特點(diǎn),專用,應(yīng)用算法相關(guān),適合于規(guī)則數(shù)據(jù)運(yùn)算,不適合于條件分支程序,發(fā)展緩慢的原因,指令廣播瓶頸,數(shù)據(jù)歸約相關(guān)性,存儲(chǔ)器速度難以提高,陣列機(jī)的程序設(shè)計(jì),例：64個(gè),PE,的陣列機(jī)中進(jìn)行64000個(gè)數(shù)據(jù)的累加。,第一步，64個(gè)子集數(shù)據(jù)分配，數(shù)據(jù),A,分配后的每個(gè)子集為,A1。,第二步，求部分累加和：,sum=0;,for(i=0;i=half,if(Pn1);,/*exit with final sum */,多處理機(jī)系統(tǒng)結(jié)構(gòu),多處理機(jī)系統(tǒng)的結(jié)構(gòu)分類,UMA,tightly

4、coupled,SMP,symmetrical multiprocessor,non SMP,NUMA,DSM,MPP,loosely coupled,UMA,Uniform memory access,可編程性,兼容性,簡(jiǎn)單的程序設(shè)計(jì)模型,通信開(kāi)銷小,可擴(kuò)展性,共享存儲(chǔ)器結(jié)構(gòu)使得存儲(chǔ)器成為瓶頸,訪存速度要求,每個(gè)數(shù)據(jù)都來(lái)自共享的存儲(chǔ)器,UMA,的實(shí)現(xiàn),集中式存儲(chǔ)器,問(wèn)題,訪存沖突,網(wǎng)絡(luò)帶寬,解決方案,多體交叉,本地指令存儲(chǔ)器,本地,cache,NUMA,DSM,distributed shared memory,用硬件機(jī)制將分布的存儲(chǔ)器構(gòu)成一個(gè)邏輯上統(tǒng)一的共享存儲(chǔ)器,cache,及其一致性問(wèn)

5、題,CC-NUMA,cache coherent NUMA,COMA,cache only memory access,MPP,massively parallel processors,大規(guī)模并行處理機(jī)系統(tǒng),消息傳遞,顯式數(shù)據(jù)交換,程序設(shè)計(jì)較難,NUMA,的實(shí)現(xiàn),分布式存儲(chǔ)器,本地存儲(chǔ)器延遲較小,擴(kuò)展性較好,性價(jià)比高,數(shù)據(jù)一致性問(wèn)題,編程復(fù)雜,DSM,的結(jié)點(diǎn),CC-NUMA,本地,cache,失效時(shí)數(shù)據(jù)將根據(jù)地址從本地存儲(chǔ)器中或者遠(yuǎn)程存儲(chǔ)器訪問(wèn),Cache,命中率低,COMA,增加每個(gè)數(shù)據(jù)塊的命中標(biāo)志信息和狀態(tài)信息,數(shù)據(jù)塊可遷移,多處理機(jī)系統(tǒng)的結(jié)構(gòu)分類,按硬件層次,芯片級(jí),芯片多處理器,CM

6、P,板級(jí),多,CPU,芯片主板,機(jī)架級(jí),網(wǎng)絡(luò)級(jí),網(wǎng)格,Bus,2 MB L2 Cache,Core1,Core2,芯片級(jí)并行性,特點(diǎn),獨(dú)立的控制流,分離的內(nèi)部狀態(tài),沒(méi)有共享的功能部件,分類,同構(gòu)多核,Core 2 Duo,異構(gòu)多核,Cell,處理器,網(wǎng)絡(luò)處理器,EXE Core,FP Unit,EXE Core,FP Unit,L2 Cache,L1 Cache,L1 Cache,System Bus,(667MHz,5333MB/s),Intel Core 2 Duo,Xeon,Core 2,Dual Core Server Processor Evolution,Core 2 Proces

7、sor Block Diagram,系統(tǒng)總線,指令預(yù)取,/,預(yù)譯碼,指令隊(duì)列,L2 Cache,和控制,指令譯碼,微碼,ROM,寄存器更名分配,調(diào)度器,FPU,ROB,ALU,ALU,ALU,LD,ST,L1 D-cache,和,D-TLB,指令預(yù)取,/,預(yù)譯碼,指令隊(duì)列,指令譯碼,微碼,ROM,ROB,寄存器更名分配,調(diào)度器,ST,LD,ALU,ALU,ALU,FPU,L1 D-cache,和,D-TLB,Intel Quad-core,Intel Core 2 Extreme,Intel Flash,Intels,tera,-scale chip,Cell,Sony-IBM,網(wǎng)絡(luò)處理器（,

8、IXP2400,）,多處理機(jī)系統(tǒng)的性能,執(zhí)行時(shí)間,串行執(zhí)行時(shí)間,+,并行執(zhí)行時(shí)間,+,通信時(shí)間,加速比,處理機(jī)數(shù),例,8-1,1,個(gè)計(jì)算任務(wù)在單個(gè)核的計(jì)算機(jī)上運(yùn)行的啟動(dòng)時(shí)間為,1,秒，運(yùn)算時(shí)間為,10,秒，數(shù)據(jù)結(jié)果匯總的時(shí)間為,1,秒。如果將該計(jì)算任務(wù)放在多核處理器的計(jì)算機(jī)上運(yùn)行，將運(yùn)算部分分解成多個(gè)線程并行執(zhí)行。,（,1,）假如任務(wù)的啟動(dòng)和數(shù)據(jù)匯總操作不能并行執(zhí)行，任務(wù)之間的通信量可以忽略，問(wèn)在核的數(shù)量分別為,2,、,4,、,8,、,16,時(shí)的任務(wù)執(zhí)行時(shí)間和加速比。,（,2,）上述情況下，假如每?jī)蓚€(gè)處理器核之間的通信時(shí)間為,0.1,秒，每對(duì)處理器核的通信串行進(jìn)行，問(wèn)在核的數(shù)量分別為,2,、,

9、4,、,8,、,16,時(shí)的任務(wù)執(zhí)行時(shí)間和加速比。,解,（,1,）,任務(wù)在單個(gè)核的計(jì)算機(jī)上運(yùn)行時(shí)間為,12,秒；,在雙核計(jì)算機(jī)上的運(yùn)行時(shí)間為,1+10/2+1=7,秒，,加速比為,12/7=1.71,；,在,4,核計(jì)算機(jī)上的運(yùn)行時(shí)間為,1+10/4+1=4.5,秒，,加速比為,12/4.5=2.67,；,在,8,核計(jì)算機(jī)上的運(yùn)行時(shí)間為,1+10/8+1=3.25,秒，,加速比為,12/3.25=3.69,；,在,16,核計(jì)算機(jī)上的運(yùn)行時(shí)間為,1+10/16+1=2.63,秒，,加速比為,12/2.63=4.56,。,解（,2,）,任務(wù)在單個(gè)核的計(jì)算機(jī)上沒(méi)有通信時(shí)間，,運(yùn)行時(shí)間為,12,秒；,在雙

10、核計(jì)算機(jī)上的通信時(shí)間為,1,0.1,，,運(yùn)行時(shí)間為,1+10/2+1+0.1=7.1,秒，加速比為,12/7.1=1.69,；,在,4,核計(jì)算機(jī)上的通信時(shí)間為,6,0.1=0.6,，,運(yùn)行時(shí)間為,1+10/4+1+0.6=5.1,秒，加速比為,12/5.1=2.35,；,在,8,核計(jì)算機(jī)上的通信時(shí)間為,28,0.1=2.8,，,運(yùn)行時(shí)間為,1+10/8+1+2.8=6.05,秒，加速比為,12/6.05=1.98,；,在,16,核計(jì)算機(jī)上的通信時(shí)間為,120,0.1=12,，,運(yùn)行時(shí)間為,1+10/16+1+12=14.63,秒，加速比為,12/14.63=0.82,，,即比單核計(jì)算機(jī)的計(jì)算時(shí)

11、間更長(zhǎng),如果采用并行通信？,處理器芯片的性能障礙,訪存,Memory wall,功耗,散熱問(wèn)題,移動(dòng)計(jì)算機(jī)的電池問(wèn)題,主頻,長(zhǎng)流水線,功耗,第二節(jié) 共享存儲(chǔ)器多處理機(jī)系統(tǒng),多核處理器系統(tǒng),系統(tǒng)中包含一個(gè)多核的處理器芯片,每個(gè)處理器核能夠獨(dú)立運(yùn)行程序,單核多處理器系統(tǒng),多個(gè)單核的處理器構(gòu)成的系統(tǒng),處理器之間的通信延遲時(shí)間較長(zhǎng),多核多處理器系統(tǒng),多個(gè)多核處理器構(gòu)成的并行系統(tǒng),兩個(gè)并行處理的層次,多處理機(jī)系統(tǒng)的結(jié)構(gòu)分類,按程序特征,MIMD,SPMD,代替,SIMD,按處理機(jī)特征,同構(gòu),homogenius,異構(gòu),heterogenius,核,獨(dú)立的指令執(zhí)行和控制單元,獨(dú)立的功能部件,獨(dú)立的控制器,

12、完整的指令流水線,獨(dú)立的或者共享的,cache,單線程或,SMT,多核處理器分類,單核多線程處理器,單核,CPU,構(gòu)成,多核處理器,多核芯片構(gòu)成,多核多線程處理器,每個(gè)核都是多線程的,多核處理器的分類,CU:CPU state+Interrupt logic,CU,Cache,EU,CU,Cache,EU,CU,CU,Cache,EU,CU,EU,Cache,CU,Cache,EU,CU,CU,EU,CU,Cache,單核單線程處理器,單核多線程處理器,多核處理器,多核多線程處理器,多核處理機(jī),單芯片多處理器,CMP,均勻,cache,訪問(wèn),UCA,非均勻,cache,訪問(wèn),NUCA,CU,E

13、U,CU,EU,Cache,CU,EU,CU,EU,共享存儲(chǔ)器,單核多處理機(jī)系統(tǒng),CU,Cache,EU,CU,Cache,EU,共享存儲(chǔ)器,CU,Cache,EU,互連網(wǎng)絡(luò),多核多處理機(jī)系統(tǒng),CU,EU,CU,EU,Cache,CU,EU,CU,EU,CU,EU,CU,EU,Cache,CU,EU,CU,EU,CU,EU,CU,EU,Cache,CU,EU,CU,EU,CU,EU,CU,EU,Cache,CU,EU,CU,EU,共享存儲(chǔ)器,互連網(wǎng)絡(luò),多處理機(jī)系統(tǒng)的構(gòu)成,多核,共享,cache,多芯片,共享存儲(chǔ)器,多板卡,共享存儲(chǔ)器,消息傳遞,多機(jī)架,消息傳遞,網(wǎng)絡(luò)通信,網(wǎng)格,網(wǎng)絡(luò)通信,Web

14、,服務(wù),核,核,核,核,多芯片多核處理機(jī),一塊主板上集成多個(gè)多核芯片,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,多板卡多處理機(jī),多芯片板卡,多核芯片,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,核,多機(jī)架多處理機(jī),多板卡機(jī)架,多芯片板卡,多核芯片,超級(jí)計(jì)算機(jī),多核面臨的挑戰(zhàn),片內(nèi)互連網(wǎng)絡(luò),UCA,NUCA,大容量多端口的共享,cache,難以實(shí)現(xiàn),UCA,訪存瓶頸,高

15、效同步機(jī)制,虛擬化,多核處理器的發(fā)展,多核處理器的發(fā)展,3,維堆疊芯片,多處理機(jī)中的虛擬機(jī),應(yīng)用級(jí),操作系統(tǒng)級(jí),硬件平臺(tái)級(jí),固件級(jí),CU,Cache,EU,CU,CU,EU,CU,Cache,虛擬機(jī),1,虛擬機(jī),2,虛擬機(jī),3,虛擬機(jī),4,虛擬機(jī),5,多處理機(jī)中的虛擬機(jī),Intra Core,Inter Core,Inter Board,Inter Rack,Grid,Virtualization of distributed processors,共享存儲(chǔ)器系統(tǒng)程序設(shè)計(jì)例子,8個(gè)處理機(jī)，單總線連接,sumPn=0;,for(i=8000*Pn;i8000*(Pn+1);i=i+1),sumP

16、n=sumPn+Ai;,/*sum the assigned areas */,half=8;,/*8 processors in single-bus MIMD */,do,synch();/*wait for completion of partial sums */,half=half/2;,/*dividing line on two sums */,if(Pn1);/*exit with final sum in sum0 */,其中,synch(),函數(shù)是一個(gè)屏障同步函數(shù)。,練習(xí)：多線程程序設(shè)計(jì),在,4,個(gè)處理器核的計(jì)算機(jī)中執(zhí)行下列循環(huán)程序，試改寫(xiě)這個(gè)程序，將其分成多個(gè)線程以提高執(zhí)行速度。,for(i=0;i,numPixels,;i+),pGrayScalBitmapi,=(unsigned BYTE),(,pRGBBitmapi.red,*0.299+,pRGBBitmapi.green,*0.587+,pRGBBitmapi.blue,*0.114);,線程的同步問(wèn)題,共享數(shù)據(jù)的讀寫(xiě)相關(guān)性,如上述例子中的部分和的讀寫(xiě)操作,共享數(shù)據(jù)的寫(xiě)寫(xiě)相關(guān)性,數(shù)據(jù)競(jìng)爭(zhēng),同步,給線程執(zhí)