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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、：,I1O2=，并且I2O1=，并且O1O2=。,3.數(shù)據(jù)相關(guān)避免,主要解決反相關(guān)和輸出相關(guān)，由編譯程序自動完成。,重命名方法：,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)量擴充方法：,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)體中語句重排序(無環(huán)路和有環(huán)路語句)，,forall：不同PE執(zhí)行不同次循環(huán)； pipeling：不同PE執(zhí)行各次循環(huán)中同一語句塊。,二、并行程序設(shè)計語言,1.開發(fā)方式,語言形成方式：擴充語言功能、重新設(shè)計并行語言,對語言的要求：靈活性、效率,程序設(shè)計方式：顯式、隱式,2.擴展語言中三種并行結(jié)構(gòu),FORK-JOIN：不同機器有不同形式，效果相同,FORK A： 派生一個進程，當(dāng)前進程繼續(xù)，,FORK A,J： FORK A功能外，地址J計數(shù)器+1，,

31、FORK A,J,N：FORK A功能外，地址J計數(shù)器值為N；,JOIN J： 地址J處計數(shù)器減1，當(dāng)計數(shù)器值為零時，啟動J+1處進程，否則，結(jié)束該進程，釋放PE。,例：3個PE并行處理88矩陣乘法。,DO 10 J=0，6 10 FORK 20，60 /*派生處理第06列進程*/ J=7 /*當(dāng)前進程處理第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)語言：,把可并行執(zhí)行的進程用cobegin-coend括起來處理,最后一條語句執(zhí)行完成后，方可執(zhí)行后續(xù)語句。,該語句可嵌套；可使用共享變量，但不允許修改。,.,parfor語句：,parfor語句原語：,例：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è)計語言必須處理好因共享變量導(dǎo)致的進程間通訊與同步問題。,三、并行算法,分為同步并行