第6章 并行處理機(jī)

1、.,第 6 章 并行處理機(jī)和相聯(lián)處理機(jī),并行處理機(jī)也稱(chēng)為陣列處理機(jī)，是通過(guò)重復(fù)設(shè)置大量的處理單元PE，將他們按一定的方式互聯(lián)成陣列，在單一控制部件CU控制下，對(duì)所有分配的不同數(shù)據(jù)并行執(zhí)行同一指令規(guī)定的操作。因此它是操作級(jí)并行的SIMD計(jì)算機(jī)。 相聯(lián)處理機(jī)使用按內(nèi)容訪問(wèn)的存儲(chǔ)器，要求對(duì)存儲(chǔ)器中所存的內(nèi)容進(jìn)行高速并行的訪問(wèn)和處理，它是存儲(chǔ)器操作并行的SIMD處理機(jī)。,.,6.1 并行處理機(jī)原理 6.2 計(jì)算機(jī)互連網(wǎng)絡(luò) 6.3 相聯(lián)處理機(jī),.,6.1 并行處理機(jī)原理,1.組成,通常由1個(gè)控制器(CU)，多個(gè)處理器(PE)，m個(gè)存儲(chǔ)模塊(M)及1個(gè)互連網(wǎng)絡(luò)(IN)組成。,一、基本結(jié)構(gòu),根據(jù)存儲(chǔ)模塊組成

2、方式可有分布式和集中式兩種。,.,2.分布式結(jié)構(gòu),存儲(chǔ)模塊由每個(gè)PE自帶。,3.集中式結(jié)構(gòu),各個(gè)PE共享m個(gè)存儲(chǔ)模塊。,特點(diǎn)：,IN：是單向的，PEPE。,工作流程：,特點(diǎn)：,IN：是雙向的，PEM。,工作流程：,比較：,分布式每個(gè)PE有局部存儲(chǔ)器，集中式共享存儲(chǔ)器。,IN的作用不同：分布式PEPE，集中式PEM。,二、主要特點(diǎn),1.利用資源重復(fù)方法，開(kāi)發(fā)并行性中的同時(shí)性,所有PE操作相同，數(shù)據(jù)不同；,與流水線的方法不同點(diǎn)；（時(shí)間重疊）,側(cè)重向量處理方面；,發(fā)展?jié)摿o(wú)窮。,2.通過(guò)IN進(jìn)行PE間、PE與M間連接，數(shù)據(jù)帶寬較大,IN影響并行算法的實(shí)現(xiàn)方法；,IN的研究成為并行處理的重點(diǎn)問(wèn)題之一。

3、,3.并行算法與并行處理機(jī)結(jié)構(gòu)密切相關(guān),不同結(jié)構(gòu)對(duì)應(yīng)的并行算法的實(shí)現(xiàn)方法不同；,并行算法的研究是并行處理的又一個(gè)重點(diǎn)問(wèn)題。,.,三、陣列處理機(jī)的常用并行算法,1.有限差分問(wèn)題,應(yīng)用：網(wǎng)格覆蓋場(chǎng)；圖像平滑化算法。,結(jié)構(gòu)：IN采用閉合螺旋線陣列。,原理：,實(shí)現(xiàn)：每個(gè)PE存儲(chǔ)和計(jì)算一組結(jié)點(diǎn)，多次迭代，直到誤差小于規(guī)定。,效率：接近N倍（要扣除通訊開(kāi)銷(xiāo)）。,結(jié)點(diǎn)最大間距n-1， 。,.,2.矩陣加,原理：把矩陣中不同位置的分量放到不同的PE中運(yùn)算，提高并行性。,實(shí)現(xiàn)：對(duì)C=A+B，A、B、C同一地址分量放在同一PE不同地址，用三條指令完成：LOAD、ADD、STORE,.,注意點(diǎn)：,如何把數(shù)據(jù)合理分配

4、到PEi。 （存儲(chǔ)單元分配算法）,每個(gè)PE存某列數(shù)據(jù)，其他數(shù)據(jù)通過(guò)播送得到。,如何分配任務(wù)給某個(gè)PEi； （同一地址+屏蔽向量）,3.累加求和,算法：折疊算法。,實(shí)現(xiàn)：,k=0; while (2k N ) PEi+2k += PEi ; /0iN-2k k=k+1; ,注意點(diǎn)：,PE的活躍問(wèn)題：置PE0至PE2k-1為不活躍狀態(tài)；,最終結(jié)果：在PEN-1中；,PE的步距問(wèn)題：2k；,MN時(shí)，采用分組求解方法。,效率：提高N/log2N倍。,一、互連網(wǎng)絡(luò)基本概念,2.性能參數(shù),連接度：某結(jié)點(diǎn)與其它結(jié)點(diǎn)的連接程度。直通點(diǎn)數(shù),延時(shí)性：某結(jié)點(diǎn)到另一結(jié)點(diǎn)的時(shí)間。結(jié)點(diǎn)間距,帶寬：可同時(shí)連接的結(jié)點(diǎn)對(duì)數(shù)。,

5、可靠性與成本：,6.2 計(jì)算機(jī)互連網(wǎng)絡(luò),1.基本功能,互連網(wǎng)絡(luò)主要完成結(jié)點(diǎn)與結(jié)點(diǎn)間的連接，連接和控制方式不同，連接效果不同。,.,3.結(jié)構(gòu)特征,(1)通信方式 同步、異步（多處理機(jī)）,(3)交換方式 線路交換、分組交換（短數(shù)據(jù)信息傳送）,(4)拓?fù)浣Y(jié)構(gòu),(2)控制策略 集中（SIMD）、分散,靜態(tài)：性能與帶寬,動(dòng)態(tài)：沒(méi)有源開(kāi)關(guān)，借助控制信號(hào)重新組合。,單級(jí)循環(huán)網(wǎng)、各種多級(jí)互連網(wǎng)絡(luò)。,4.設(shè)計(jì)思路,根據(jù)應(yīng)用需要（互連網(wǎng)絡(luò)屬性），選擇合理的特征方式，考慮互連網(wǎng)絡(luò)的性能因素，綜合加以合理組合。,目標(biāo)：低成本、高靈活性、高連接度、低延時(shí)、適合VLSI。,5.互連網(wǎng)絡(luò)表示,入端的編碼：x=（bn-1b0

6、) n=log2N,互連函數(shù)為基于bn-1b0的排列、組合、移位、取反等操作的結(jié)果。,互連網(wǎng)絡(luò)的連接特征一般用互連函數(shù)表示。,一個(gè)互連網(wǎng)絡(luò)的連接特征可對(duì)應(yīng)多個(gè)互連函數(shù)。,1.立方體單級(jí)網(wǎng)絡(luò)（交換互連網(wǎng)絡(luò)）,單級(jí)互連網(wǎng)絡(luò)只能實(shí)現(xiàn)有限的幾種連接。,二、單級(jí)互連網(wǎng)絡(luò),出端編碼與連接的入端結(jié)點(diǎn)的編碼有一位相反。,互連函數(shù)：,互連特性：,交換功能-互連函數(shù)可逆；,互連函數(shù)個(gè)數(shù)=log28=3；,最大連接度=log28=3；,結(jié)點(diǎn)最大間距=log28=3。,連接圖：,擴(kuò)展成超立方體：,有n=log2N個(gè)互連函數(shù)；,最大連接度=log2N；,結(jié)點(diǎn)最大間距=log2N。,應(yīng)用：幾種互連函數(shù)反復(fù)調(diào)用，任意結(jié)點(diǎn)間

7、可連接。,2.PM2I單級(jí)網(wǎng)絡(luò)（循環(huán)移數(shù)網(wǎng)絡(luò)）,出端編碼與連接的入端結(jié)點(diǎn)編碼相差2i。,互連函數(shù)：,PM2I+i(j)=(j+2i) mod N； n=log2N,0in-1,PM2I-i(j)=(j-2i) mod N； 0jN-1,共有2n個(gè)互連函數(shù)(2n-1種不同)。,連接圖：,0：順環(huán)圓周連接；,1：順環(huán)內(nèi)接n/2邊形連接；,2：順環(huán)內(nèi)接n/4邊形連接；,(n-1)：順環(huán)內(nèi)直徑連接。,互連特性：,2n個(gè)互連函數(shù)只有一種函數(shù)可逆，其余均不可逆；,最大連接度2n-1；,互連函數(shù)個(gè)數(shù)2n。,應(yīng)用：幾種互連函數(shù)混合，任意結(jié)點(diǎn)間可連接。,實(shí)例：閉合螺旋結(jié)構(gòu)為PM2I+0及PM2In/2互連函數(shù)。

8、,3.混洗交換單級(jí)網(wǎng)絡(luò),全混洗（二混洗）：,三混洗：,全混洗互連函數(shù)：,Shuffle(bn-1bn-2b1b0)=(bn-2b1b0bn-1)；,全“0”或全“1”結(jié)點(diǎn)無(wú)法與其他結(jié)點(diǎn)連接，必須輔以交換互連函數(shù)，方可實(shí)現(xiàn)任意結(jié)點(diǎn)間連接。,最簡(jiǎn)單的交換互連函數(shù)為Cube0，因此混洗交換網(wǎng)絡(luò)由全混洗和交換網(wǎng)絡(luò)組合而成。,交換互連函數(shù)：,混洗交換互連函數(shù)：,連接圖：,互連特性：,互連函數(shù)不可逆；,n次混洗和還原； 與循環(huán)移位REG工作類(lèi)似,最大間距：n次交換，n-1次混洗，共2n-1次；,全混洗最先改變最高位(左移)，交換取反最低位。,應(yīng)用： 多次調(diào)用混洗交換互連函數(shù)，可實(shí)現(xiàn)任意結(jié)點(diǎn)間的連接。,4.

9、總結(jié),(1)單級(jí)互連網(wǎng)絡(luò)特性,任一單級(jí)互連網(wǎng)絡(luò)可實(shí)現(xiàn)部分結(jié)點(diǎn)(一對(duì)或幾對(duì))間的連接，不能實(shí)現(xiàn)任意多對(duì)結(jié)點(diǎn)間的同時(shí)連接。,單級(jí)互連網(wǎng)絡(luò)含義：某些連接方法或拓?fù)浣Y(jié)構(gòu)。,(2)單級(jí)互連網(wǎng)絡(luò)應(yīng)用,利用單級(jí)互連網(wǎng)絡(luò)的特性作為實(shí)際IN的拓?fù)浣Y(jié)構(gòu)；,通過(guò)交換開(kāi)關(guān)作為IN的可變因素；,通過(guò)交換開(kāi)關(guān)多次控制實(shí)現(xiàn)IN的結(jié)點(diǎn)間任意互連。,三、多級(jí)互連網(wǎng)絡(luò),目標(biāo)：完成某結(jié)點(diǎn)與其它任一結(jié)點(diǎn)的連接；,同時(shí)完成多對(duì)結(jié)點(diǎn)的連接。,方法：從時(shí)間性和空間性方面開(kāi)發(fā)。,1.循環(huán)互連網(wǎng)絡(luò)（時(shí)間性）,組成：DTRin、DTRout、MUX、IN。,結(jié)構(gòu)： 一個(gè)單級(jí)IN+MUX。,特點(diǎn)： 節(jié)省了設(shè)備， 增加了時(shí)間， 每個(gè)MUX可單獨(dú)控制

10、。,2.多級(jí)互連網(wǎng)絡(luò)（空間性）,組成：DTRin、DTRout、交換開(kāi)關(guān)、拓?fù)浣Y(jié) 構(gòu)(IN)。,交換開(kāi)關(guān)：具有傳送或播送功能。,拓?fù)浣Y(jié)構(gòu)：不同級(jí)開(kāi)關(guān)間連接方式(單級(jí)IN的連接功能)。,控制方式：級(jí)控制、部分級(jí)控制、單元控制。,DTRin、DTRout：PE或M，可為同一類(lèi)型。,.,分類(lèi)：根據(jù)拓?fù)浣Y(jié)構(gòu)進(jìn)行分類(lèi),多級(jí)立方體網(wǎng)絡(luò) 多級(jí)混洗交換網(wǎng)絡(luò) 多級(jí)PM2I網(wǎng)絡(luò),3.多級(jí)立方體網(wǎng)絡(luò),有STARAN(級(jí)控制和部分級(jí)控制)和間接二進(jìn)制n立方體(單元控制)兩種網(wǎng)絡(luò)。,以STARAN網(wǎng)絡(luò)為例介紹。,返回35頁(yè),返回下頁(yè),交換開(kāi)關(guān)：二功能（直通和交換）,拓?fù)浣Y(jié)構(gòu)：第i級(jí)為Cubei；,為什么只有三級(jí)？,(1

11、)交換功能,控制：級(jí)控制(開(kāi)關(guān)為1時(shí)交換功能，否則為直通),返回下頁(yè),轉(zhuǎn)上頁(yè),應(yīng)用：對(duì)集中式處理機(jī)同時(shí)數(shù)據(jù)傳輸作用很大。,交換功能：組間次序不變，組內(nèi)元素鏡像。,Cube0：4組2元交換， Cube1：2組4元交換+4組2元交換， Cube2：1組8元交換+2組4元交換。,功能：控制信號(hào)不同，功能不同。,(2)移位功能,控制：部分級(jí)控制（第i級(jí)有i+1種控制信號(hào)）,功能：控制信號(hào)不同，功能不同。,應(yīng)用：,不同的Mod，可用作不同的分組操作。,移數(shù)功能很適合于累加求和算法實(shí)現(xiàn)；,(3)帶寬問(wèn)題,STARAN可同時(shí)多對(duì)結(jié)點(diǎn)連接，尚不能同時(shí)任意組合。,(4)例題,例1：編號(hào)0F的PE間，要實(shí)現(xiàn)下列通

12、信配對(duì)： (7,D),(6,C),(5,F),(4,E),(3,9),(2,8),(1,B),(0,A) 畫(huà)出互連網(wǎng)絡(luò)結(jié)構(gòu)圖，寫(xiě)出控制方式級(jí)各開(kāi)關(guān)狀態(tài)。,答：因需實(shí)現(xiàn)雙向交換功能，選擇STARAN的交換網(wǎng)絡(luò)(級(jí)控制方式）可滿足要求。,因共有16個(gè)結(jié)點(diǎn)，編碼需要4位，所以開(kāi)關(guān)共4級(jí)。,網(wǎng)絡(luò)結(jié)構(gòu)圖如下頁(yè)：,拓?fù)浣Y(jié)構(gòu)：不同級(jí)完成地址不同位取反功能。,注意：有交換開(kāi)關(guān)的拓?fù)浣Y(jié)構(gòu)的實(shí)現(xiàn)。,結(jié)果：03 8B，47 CF,因01的結(jié)點(diǎn)與AB的結(jié)點(diǎn)配對(duì)，故需4組4元交換；,因0結(jié)點(diǎn)與A結(jié)點(diǎn)配對(duì)，故需8組2元交換。,相加 Cube1+ Cube3,各級(jí)開(kāi)關(guān)狀態(tài)：k3k2k1k0=(1010),因7的結(jié)點(diǎn)需與7的

13、結(jié)點(diǎn)配對(duì)，故需1組16元交換；,因03的結(jié)點(diǎn)與8B的結(jié)點(diǎn)配對(duì)，故需2組8元交換；,結(jié)果：01 BA，23 98,例2：并行處理機(jī)有16個(gè)PE，實(shí)現(xiàn)相當(dāng)于4 組4元交換，然后2組8元交換，再1組16元交 換功能。寫(xiě)出互連函數(shù)一般式、各級(jí)交換開(kāi) 關(guān)狀態(tài)。,答：因需實(shí)現(xiàn)交換功能，故選擇STARAN的 交換網(wǎng)絡(luò)(級(jí)控制方式）。,相加 Cube0+Cube1 +Cube3,各級(jí)開(kāi)關(guān)狀態(tài)：k3k2k1k0=(1011),4.多級(jí)混洗交換網(wǎng)絡(luò)（網(wǎng)絡(luò)）,交換開(kāi)關(guān)：四功能（允許實(shí)現(xiàn)一對(duì)多的連接）,拓?fù)浣Y(jié)構(gòu)：不同級(jí)相同，均為全混洗結(jié)構(gòu)；,控制方式：級(jí)控制、部分級(jí)控制、單元控制；,連接圖：第n-1級(jí)靠近入端；,功能

14、：,級(jí)控制且開(kāi)關(guān)為二功能： 是STARAN交換網(wǎng)絡(luò)的逆網(wǎng)絡(luò)； （F、G交換位置）,部分級(jí)控制且開(kāi)關(guān)為二功能： 是STARAN移數(shù)網(wǎng)絡(luò)的逆網(wǎng)絡(luò)；,單元控制：可實(shí)現(xiàn)更強(qiáng)大的功能。,利用交換開(kāi)關(guān)的播送功能實(shí)現(xiàn)一對(duì)多的連接。,應(yīng)用（累加求和）：,用循環(huán)逆混洗網(wǎng)絡(luò)加循環(huán)移位網(wǎng)絡(luò)實(shí)現(xiàn)。,逆混洗(重排序)：和混洗剛好相反，起聚合作用。,循環(huán)移位(累加)：縱向相鄰結(jié)點(diǎn)相加。,.,5.全排列網(wǎng)絡(luò),多級(jí)網(wǎng)絡(luò)比較,靈活性(低高)：STARAN、間接二進(jìn)制n方體、 Omega()、ADM(混洗四功能),成本(低高)：同上,用途： STARAN、Omega PEM,間接二進(jìn)制n方體 PEPE,功能：只能實(shí)現(xiàn)同時(shí)部分多對(duì)

15、多功能。,全排列網(wǎng)絡(luò),定義：所有入端、出端的連接均不發(fā)生沖突的網(wǎng)絡(luò)，又稱(chēng)非阻塞型網(wǎng)絡(luò)，即：N入N出有N！種排列。,互連網(wǎng)絡(luò)要求：全排列網(wǎng)絡(luò)(非阻塞型網(wǎng)絡(luò))。,STARAN等網(wǎng)絡(luò)屬于阻塞型網(wǎng)絡(luò)。,證明：對(duì)n=log2N級(jí)網(wǎng)絡(luò)，開(kāi)關(guān)數(shù)=N/2n。,排列數(shù),全排列網(wǎng)絡(luò)實(shí)現(xiàn)：,原有多級(jí)網(wǎng)絡(luò)通過(guò)鎖存器運(yùn)行兩次即可。,兩個(gè)log2N網(wǎng)絡(luò)背靠背串聯(lián)。,思想：N!NN/2NN/2NN。,四、BSP并行處理機(jī)系統(tǒng),1.結(jié)構(gòu),管理計(jì)算機(jī)：負(fù)責(zé)編譯、調(diào)度、通信、外圍管理；,BSP：并行處理機(jī)、控制處理機(jī)、文件存儲(chǔ)系統(tǒng)。,利用流水線方式，提高并行性；,PE、PEM、IN1、IN2、控制部件5級(jí)流水；,超長(zhǎng)向量分段、重

16、疊處理；,流水線建立時(shí)間重疊。,2.特點(diǎn),多體交叉存儲(chǔ)器，提高存儲(chǔ)帶寬；,兩個(gè)對(duì)準(zhǔn)網(wǎng)絡(luò)，實(shí)現(xiàn)讀、寫(xiě)的并行操作；,標(biāo)量指令處理與向量處理重疊，標(biāo)量浮點(diǎn)作為長(zhǎng)度為1的向量處理，簡(jiǎn)化標(biāo)量；,指令系統(tǒng)效率高，與高級(jí)語(yǔ)言語(yǔ)義差別不大；,編譯程序向量化功能強(qiáng)，并行性識(shí)別能力高。,第四節(jié) 并行存儲(chǔ)器無(wú)沖突訪問(wèn),一、訪問(wèn)需求,并行存取向量中各分量信息；,可按行、列、對(duì)角線等方法存取(步長(zhǎng)不一致)。,二、存在問(wèn)題,存儲(chǔ)器帶寬限制存儲(chǔ)器帶寬達(dá)不到向量帶寬；,訪存方式(步長(zhǎng))不同，產(chǎn)生訪存沖突。,三、解決方法,1.采用多體交叉存儲(chǔ)器-增加MEM帶寬,2.對(duì)向量分組操作-解決MEM帶寬小于向量帶寬問(wèn)題,.,3.選擇適

17、當(dāng)?shù)拇鎯?chǔ)體數(shù)m-達(dá)到無(wú)沖突訪問(wèn),一維向量：順序存放，防止步長(zhǎng)與m成比例；,m取質(zhì)數(shù)，且與步長(zhǎng)互質(zhì)。,多維向量：錯(cuò)位存放，滿足行、列、對(duì)角線等方式；,當(dāng)m大于每次訪問(wèn)向量元素個(gè)數(shù)時(shí)，,m=22P+1，1=2P，同一列不同行錯(cuò)開(kāi)距離 2=1，同一行不同列錯(cuò)開(kāi)距離,對(duì)Aab，體號(hào)： j=(a1+b2+C) mod m 體內(nèi)序號(hào)：i=a,.,當(dāng)向量元素不固定，或非nn時(shí)，,將多維變換成一維數(shù)組S，再對(duì)S進(jìn)行處理。,通過(guò)浪費(fèi)少量存儲(chǔ)帶寬和空間來(lái)避免沖突。 浪費(fèi)比例：(m-n)/m，一般n=m-1。,常用方法：存儲(chǔ)體數(shù)為質(zhì)數(shù)，將向量變換成一維數(shù)組S，再對(duì)S進(jìn)行處理。,.,第五節(jié) MMX技術(shù),一、多媒體數(shù)據(jù)

18、處理方案,選擇專(zhuān)用芯片和制作專(zhuān)用插卡，在主板上 擴(kuò)充功能；,改善總線結(jié)構(gòu)與性能，如提高總線帶寬、總線時(shí)鐘頻率及使用AGP端口等；,將重要的多媒體和通信支持技術(shù)融入到CPU芯片中：,全新設(shè)計(jì)CPU結(jié)構(gòu)(標(biāo)量、向量處理器)； Vecomp701,在原有CPU基礎(chǔ)上，擴(kuò)充多媒體指令。 Pentium,.,二、MMX技術(shù),MMX技術(shù)基礎(chǔ)：,64位的數(shù)據(jù)帶寬可同時(shí)處理多個(gè)多媒體 數(shù)據(jù)(SIMD)。,MMX應(yīng)用基礎(chǔ)：,OS向下兼容，不引進(jìn)新的狀態(tài)、控制REG和條件碼。,MMX技術(shù)體現(xiàn)：,4種新的數(shù)據(jù)類(lèi)型； 8個(gè)64位寬的MMX寄存器； 57條新指令。需要數(shù)據(jù)類(lèi)型和寄存器支持,1.MMX數(shù)據(jù)類(lèi)型與寄存器,M

19、MX數(shù)據(jù)類(lèi)型：三種打包類(lèi)型和一種64位長(zhǎng) 的數(shù)據(jù)類(lèi)型。,緊縮字節(jié)類(lèi)型：8個(gè)字節(jié)打包成64位長(zhǎng)的 數(shù)據(jù)； 緊縮字類(lèi)型：4個(gè)字打包成64位長(zhǎng)的數(shù)據(jù)； 緊縮雙字類(lèi)型：2個(gè)雙字打包成64位長(zhǎng)的數(shù)據(jù)； 四字類(lèi)型：1個(gè)64位數(shù)據(jù)。,MMX指令根據(jù)不同數(shù)據(jù)類(lèi)型進(jìn)行不同的SIMD處理。,MMX寄存器：8個(gè)64位寬的寄存器NM0-NM7,利用浮點(diǎn)處理單元的8個(gè)浮點(diǎn)數(shù)據(jù)寄存器，通過(guò)別名方法實(shí)現(xiàn)。不增加新的硬件和條件碼,.,2.MMX指令集,MMX指令類(lèi)型（共7組）：,算術(shù)指令、比較指令、轉(zhuǎn)換指令、邏輯 指令、移位指令、數(shù)據(jù)傳送指令和清除MMX 狀態(tài)(EMMS)指令。,MMX指令先進(jìn)性能體現(xiàn)：,SIMD結(jié)構(gòu)：一次并

20、行處理多個(gè)不相關(guān)小型數(shù)據(jù)；,飽和運(yùn)算方式：溢出時(shí)不做異常處理，其值為極限值；,積和運(yùn)算方式：點(diǎn)積功能，即 ， 適用于矩陣、離散余弦變換、濾波操作等方面；,.,比較指令：比較結(jié)果為0-假1-真，不建 立標(biāo)志位， 后跟一條邏輯操作，能并行處理數(shù)據(jù)， 避免猜測(cè)；,轉(zhuǎn)換指令：即緊縮或解緊縮指令，完成 數(shù)據(jù)轉(zhuǎn)換， 用于像點(diǎn)間插值、矩陣轉(zhuǎn)置、色彩空間轉(zhuǎn)換等。,.,第六節(jié) 多處理機(jī)系統(tǒng)結(jié)構(gòu),并行處理機(jī)屬SIMD結(jié)構(gòu)，較適合向量處理；,一、多處理機(jī)與并行處理機(jī)區(qū)別,多處理機(jī)屬M(fèi)IMD結(jié)構(gòu)，可進(jìn)行更高層次的并行處理。,1.結(jié)構(gòu)與通用性,SIMD：?jiǎn)沃噶盍飨到y(tǒng)，并行操作相同，一個(gè)CU，控制、數(shù)據(jù)通訊簡(jiǎn)單，通用性較

21、差；,MIMD：多指令流系統(tǒng)，并行操作不同，多個(gè)CU，控制、數(shù)據(jù)通訊復(fù)雜，通用性較強(qiáng)。,.,2.程序并行性,SIMD：操作級(jí)并行（數(shù)據(jù)并行）， 識(shí)別：隱式識(shí)別和向量指令， 支持：編譯程序和硬件；,MIMD：任務(wù)級(jí)并行（數(shù)據(jù)、功能并行）， 識(shí)別：顯式指令、編譯程序、OS和硬件等， 支持：專(zhuān)用指令，OS對(duì)任務(wù)的分派和調(diào)度。,3.任務(wù)派生,SIMD：向量指令表示及控制，隱式并行、效率低；,MIMD：專(zhuān)用指令表示及控制，顯式并行、效率高。,.,4.進(jìn)程同步,SIMD：?jiǎn)我籆U控制，自然同步；,MIMD：多個(gè)CU控制，需采取特殊措施同步 （等待、信號(hào)燈等）。,5.資源分配和任務(wù)調(diào)度,SIMD：屏蔽手段，

22、無(wú)需調(diào)度；,MIMD：軟件手段（排隊(duì)器、觸發(fā)等）分配及調(diào)度。,.,6.效率,SIMD：延遲槽、猜測(cè)法等手段，效率低；,MIMD：同時(shí)多路執(zhí)行，效率高。,IF語(yǔ)句,無(wú)相關(guān)語(yǔ)句,結(jié)果：TSIMD TMIMD。,.,二、多處理機(jī)需解決問(wèn)題,模塊互連，并行性開(kāi)發(fā)，任務(wù)分解，同 步，調(diào)度。,三、多處理機(jī)結(jié)構(gòu),1.緊耦合系統(tǒng)(TCS),特點(diǎn)：通過(guò)共享主存實(shí)現(xiàn)機(jī)間通訊。,互連網(wǎng)絡(luò)：實(shí)現(xiàn)PEPEM、PEI/O通道、 PE中斷信號(hào)間的連接。,系統(tǒng)屬性：,同構(gòu)/異構(gòu)-PE類(lèi)型相同/不同；,對(duì)稱(chēng)/非對(duì)稱(chēng)每個(gè)PE與部分/全部的I/O通道連接。,常見(jiàn)結(jié)構(gòu)：同構(gòu)對(duì)稱(chēng)式和異構(gòu)非對(duì)稱(chēng)式多機(jī)系統(tǒng)。,限制：PE數(shù)量不能很多。為什

23、么？,主存帶寬、IN帶寬、同步開(kāi)銷(xiāo)限制了PE的數(shù)量。,訪存沖突解決方案：,采取多體交叉訪問(wèn)方式，增加PEM數(shù)量；,每個(gè)PE自帶小容量局部存儲(chǔ)器，存放核心代碼、OS表格等，減少PE訪存次數(shù)；,每個(gè)PE自帶一個(gè)Cache，減少PE訪存次數(shù)。,2.松耦合系統(tǒng)(LCS),特點(diǎn)：通過(guò)消息傳送系統(tǒng)實(shí)現(xiàn)機(jī)間通訊；,每個(gè)模塊是一個(gè)獨(dú)立的處理機(jī)，整個(gè)系統(tǒng)可看成是一個(gè)分布系統(tǒng)。,互連網(wǎng)絡(luò)：MTS有總線、環(huán)形、多級(jí)網(wǎng)絡(luò)等種類(lèi)；,結(jié)構(gòu)：有層次和非層次兩種結(jié)構(gòu)。,與計(jì)算機(jī)網(wǎng)絡(luò)區(qū)別：,單一的系統(tǒng)物理地址空間；,每個(gè)PE的存儲(chǔ)器均可被其它PE訪問(wèn)，通過(guò)CAS實(shí)現(xiàn)。,層次結(jié)構(gòu)訪存實(shí)現(xiàn)：,Cm內(nèi)部局部開(kāi)關(guān)slocal功能：確定

24、PE地址的訪問(wèn)路線。,開(kāi)關(guān)控制器KMap功能：傳送地址訪問(wèn)請(qǐng)求 及結(jié)果。,構(gòu)成：三個(gè)處理器和一個(gè)共享存儲(chǔ)器。,Kbus：總線管理器，仲裁對(duì)Map的請(qǐng)求。,Linc：管理KMap間的通訊。,Pmap：映象處理器，響應(yīng)Kbus及Linc的請(qǐng)求。,.,Pmap設(shè)計(jì)可有8個(gè)并發(fā)請(qǐng)求，對(duì)等待返 回的請(qǐng)求，則切換到另一任務(wù)請(qǐng)求，以達(dá)到 最佳性能。,工作流程：分模塊組內(nèi)訪存和模塊組 間訪存兩種。,.,3.多處理機(jī)中Cache的一致性,軟件方法： （回避方法）,共享信息只存放在主存，借助于編譯程序完成；,判斷數(shù)據(jù)何時(shí)可放在Cache中。,總線監(jiān)聽(tīng)機(jī)制： （只適合于總線結(jié)構(gòu)）,每個(gè)PE的Cache設(shè)置一個(gè)監(jiān)聽(tīng)部

25、件，一旦在Cache中的單元的聽(tīng)到寫(xiě)操作，作相應(yīng)處理（修改或作廢）。,目錄表法： （非總線結(jié)構(gòu)）,主存設(shè)置目錄表數(shù)據(jù)塊地址，指示器、標(biāo)志位，某PE寫(xiě)Cache時(shí)，通知指示器中的PE處理。,四、機(jī)間互連形式,1.總線形式 （時(shí)間分配） 最常見(jiàn),PE、PEM、I/O通道均連在總線上，采用分時(shí)或多路轉(zhuǎn)換技術(shù)實(shí)現(xiàn)數(shù)據(jù)傳遞，是最簡(jiǎn)單的連接方式。,總線仲裁算法：靜態(tài)優(yōu)先級(jí)算法、平等算法、動(dòng)態(tài)優(yōu)先級(jí)算法、先來(lái)先服務(wù)算法等。,對(duì)外設(shè)一般采用優(yōu)先級(jí)算法；對(duì)PE采用均等算法。,實(shí)現(xiàn)方法：,集中式：由總線控制器控制；,分布式：中機(jī)構(gòu)分散到各PE中。,提高總線效率方法：,改善傳輸介質(zhì)和增加總線數(shù)量。,總線互連方式不適

26、宜連接過(guò)多的處理機(jī)。,.,2.交叉開(kāi)關(guān)形式 （空間分配）,是總線形式的極端，總線數(shù)=PE數(shù)+PEM數(shù) +I/O通道數(shù)，是一種全相聯(lián)形式，控制、仲 裁、轉(zhuǎn)換機(jī)構(gòu)均在開(kāi)關(guān)中。,改進(jìn)：用一系列較小開(kāi)關(guān)串聯(lián)或并聯(lián)，形 成多級(jí)交叉開(kāi)關(guān)，減少其復(fù)雜性。,交叉開(kāi)關(guān)方式不適宜連接過(guò)多的處理機(jī)。,3.多端口存儲(chǔ)器形式,將控制、仲裁、轉(zhuǎn)換機(jī)構(gòu)移到存儲(chǔ)器中。,每個(gè)端口與一個(gè)PE或I/O通道相連。,多端口存儲(chǔ)器形式不適宜連接過(guò)多的處理機(jī)。,4.多級(jí)互連網(wǎng)絡(luò)形式,是介于總線(N)與交叉開(kāi)關(guān)(N2) 中間的一種(Nlog2N)。,對(duì)互連網(wǎng)絡(luò)I與O數(shù)不一致時(shí)，可采用榕樹(shù)形網(wǎng)絡(luò)。,多級(jí)互連網(wǎng)絡(luò)適宜于PE數(shù)較多的系統(tǒng)。,ab交

27、叉開(kāi)關(guān),a入b出，輸入基于a編碼，輸出基于b編碼。,入端出端受阻后，重新申請(qǐng)，性能受建立時(shí)間限制；設(shè)置緩沖器性能有所改善，適合于包交換網(wǎng)絡(luò)。,anbn互連網(wǎng)絡(luò),交叉開(kāi)關(guān)為ab開(kāi)關(guān)，由n級(jí)構(gòu)成。,比較：交叉開(kāi)關(guān)時(shí)結(jié)點(diǎn)數(shù)為anbn，多級(jí)互連網(wǎng)絡(luò)時(shí)結(jié)點(diǎn)數(shù)為abn2，明顯降低了復(fù)雜性。,.,5.開(kāi)關(guān)樞紐形式,將互連結(jié)構(gòu)設(shè)置在PE或其接口內(nèi)部，組成分布結(jié)構(gòu)(松耦合)。,開(kāi)關(guān)樞紐：由仲裁單元和開(kāi)關(guān)單元組成，端口數(shù)不能多。,結(jié)構(gòu)：由開(kāi)關(guān)樞紐組成各種結(jié)構(gòu)，如樹(shù)形結(jié)構(gòu)。,開(kāi)關(guān)樞紐網(wǎng)絡(luò)適宜于PE數(shù)較多的系統(tǒng)。,6.蟲(chóng)孔互連和尋徑技術(shù),原理：采用流水技術(shù)解決互連網(wǎng)絡(luò)傳輸延遲問(wèn)題。,傳輸延遲原因：,存儲(chǔ)-轉(zhuǎn)發(fā)結(jié)構(gòu)使傳

28、輸延遲與結(jié)點(diǎn)間距成正比。,延時(shí)分析：,存儲(chǔ)-轉(zhuǎn)發(fā)：T=(L/W)(D+1)；,.,蟲(chóng)孔尋徑：LF時(shí)TWH與結(jié)點(diǎn)間距D無(wú)關(guān)。,控制原理：,存儲(chǔ)-轉(zhuǎn)發(fā)：軟件控制；,蟲(chóng)孔尋徑：硬件控制，采用握手式的異 步流水方式，形成虛擬通道，使一個(gè)物理通 道為多個(gè)虛擬通道所共享。,拓?fù)浣Y(jié)構(gòu)：,存儲(chǔ)-轉(zhuǎn)發(fā)：尋求最短結(jié)點(diǎn)間距的互連網(wǎng)絡(luò)；,蟲(chóng)孔尋徑：傳統(tǒng)的二維或三維結(jié)構(gòu)，不采用多維結(jié)構(gòu)。,.,第七節(jié) 多處理機(jī)中并行性開(kāi)發(fā),一、并行性開(kāi)發(fā),1.相關(guān)類(lèi)型,數(shù)據(jù)相關(guān)RAW相關(guān)，數(shù)據(jù)反相關(guān)WAR相關(guān)， 數(shù)據(jù)輸出相關(guān)WAW相關(guān)，控制相關(guān)條件語(yǔ)句。,2.并行性檢測(cè) -伯恩斯坦準(zhǔn)則,Ii讀單元集，Oi寫(xiě)單元集， P1、P2可并行條件

29、：,I1O2=，并且I2O1=，并且O1O2=。,3.數(shù)據(jù)相關(guān)避免,主要解決反相關(guān)和輸出相關(guān)，由編譯程序自動(dòng)完成。,重命名方法：,S：A=B+C T：D=A+E U：A=A+D V：IF X0 THEN G=F+A,U：AA=A+D V：IF X0 THEN G=F+AA,標(biāo)量擴(kuò)充方法：,for i=1 to n do if A(i)0 then X=B(i); else X=C(i); D(i)=X+1;,for i=1 to n do b(i)=A(i)0; X(i)=B(i) when b(i); X(i)=C(i) when not b(i); D(i)=X(i)+1;,存在數(shù)據(jù)相關(guān)、

30、反相關(guān)、輸出相關(guān)、控制相關(guān)。,消除了數(shù)據(jù)反相關(guān)、輸出相關(guān)。,消除反相關(guān)、輸出相關(guān),.,forall和pipeling變換：改善循環(huán)體中相關(guān),將循環(huán)體中語(yǔ)句重排序(無(wú)環(huán)路和有環(huán)路語(yǔ)句)，,forall：不同PE執(zhí)行不同次循環(huán)； pipeling：不同PE執(zhí)行各次循環(huán)中同一語(yǔ)句塊。,二、并行程序設(shè)計(jì)語(yǔ)言,1.開(kāi)發(fā)方式,語(yǔ)言形成方式：擴(kuò)充語(yǔ)言功能、重新設(shè)計(jì)并行語(yǔ)言,對(duì)語(yǔ)言的要求：靈活性、效率,程序設(shè)計(jì)方式：顯式、隱式,2.擴(kuò)展語(yǔ)言中三種并行結(jié)構(gòu),FORK-JOIN：不同機(jī)器有不同形式，效果相同,FORK A： 派生一個(gè)進(jìn)程，當(dāng)前進(jìn)程繼續(xù)，,FORK A,J： FORK A功能外，地址J計(jì)數(shù)器+1，,

31、FORK A,J,N：FORK A功能外，地址J計(jì)數(shù)器值為N；,JOIN J： 地址J處計(jì)數(shù)器減1，當(dāng)計(jì)數(shù)器值為零時(shí)，啟動(dòng)J+1處進(jìn)程，否則，結(jié)束該進(jìn)程，釋放PE。,例：3個(gè)PE并行處理88矩陣乘法。,DO 10 J=0，6 10 FORK 20，60 /*派生處理第06列進(jìn)程*/ J=7 /*當(dāng)前進(jìn)程處理第7列*/ 20 DO 40 I=0，7 /*處理07行*/ C(I,J)=0 DO 30 K=0,7 /*處理C(I,J)*/ 30 C(I,J)=C(I,J)+A(I,K)*B(K,J) 40 CONTINUE JOIN 60 60 ,塊結(jié)構(gòu)語(yǔ)言：,把可并行執(zhí)行的進(jìn)程用cobegin-coend括起來(lái)處理,最后一條語(yǔ)句執(zhí)行完成后，方可執(zhí)行后續(xù)語(yǔ)句。,該語(yǔ)句可嵌套；可使用共享變量，但不允許修改。,.,parfor語(yǔ)句：,parfor語(yǔ)句原語(yǔ)：,例：C(n1)=A(nn)B(n1),parfor i=1, p for j=(i-1)*s+1, s*i /*s=n/p*/ c(j)=0 for k=1, n c(j)=c(j)+A(j,k)*B(j) ,P1:1s;P2:s+12s;Pp:n-sn,并行程序設(shè)計(jì)語(yǔ)言必須處理好因共享變量導(dǎo)致的進(jìn)程間通訊與同步問(wèn)題。,三、并行算法,分為同步并行