《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》 課件 第五章 并行處理機(jī)

第五章并行處理機(jī)主講教師：?jiǎn)尾槻⑿刑幚頇C(jī)(parallelprocessor)采用資源重復(fù)的并行性措施，通過(guò)重復(fù)設(shè)置大量相同的處理單元(PE，ProcessingElement)將它們按一定方式互連成陣列，在單一控制部件(CU，ControlUnit)控制下，對(duì)各自分配的不同數(shù)據(jù)并行執(zhí)行同一指令規(guī)定的操作以獲得高性能。并行處理機(jī)也稱為陣列處理機(jī)(arrayprocessor)，是屬于以單指令流多數(shù)據(jù)流(SIMD)方式工作的操作級(jí)并行計(jì)算機(jī)。并行處理機(jī)的結(jié)構(gòu)并行處理機(jī)由于存儲(chǔ)器采用的組成方式不同，有兩種基本結(jié)構(gòu)：具有分布式存儲(chǔ)器結(jié)構(gòu)的并行處理機(jī)和具有集中式共享存儲(chǔ)器結(jié)構(gòu)的并行處理機(jī)。分布式存儲(chǔ)器結(jié)構(gòu)并行處理機(jī)它包含重復(fù)設(shè)置的多個(gè)相同的處理單元PE，各PE都擁有自己的局部存儲(chǔ)器(PEM，ProcessingElementMemory)存放被分配的數(shù)據(jù)并只能被本處理單元直接訪問(wèn)。在控制部件CU內(nèi)設(shè)有一個(gè)存放程序和數(shù)據(jù)的控制部件存儲(chǔ)器CUM，整個(gè)系統(tǒng)在CU控制運(yùn)算過(guò)程中，各處理單元之間的可通過(guò)互連網(wǎng)絡(luò)(ICN，InterConnectionNetwork)實(shí)現(xiàn)數(shù)據(jù)交換。下運(yùn)行用戶程序和部分系統(tǒng)程序。系統(tǒng)中的處理單元陣列通過(guò)控制部件連接到一臺(tái)主處理機(jī)(SC，SubjectComputer)上。SC主要實(shí)現(xiàn)整個(gè)并行處理機(jī)系統(tǒng)的管理，包括系統(tǒng)全部資源的管理，完成系統(tǒng)輸入輸出、用戶程序的匯編及向量化編譯、作業(yè)調(diào)度、存儲(chǔ)分配、設(shè)備管理、文件管理等功能。這種結(jié)構(gòu)的并行處理機(jī)是SIMD的主流，典型機(jī)器有美國(guó)伊里諾大學(xué)研制、Burroughs公司生產(chǎn)的ILLIAC-IV陣列處理機(jī)，Goodyear宇航公司研制成的巨型并行處理機(jī)MPP(MassivelyParallelProcessor)，英國(guó)ICL公司設(shè)計(jì)生產(chǎn)的分布式陣列處理機(jī)DAP(DistributedArrayProcessor)，MasPar公司的MP-1等。集中式共享存儲(chǔ)器結(jié)構(gòu)并行處理機(jī)與分布存儲(chǔ)器結(jié)構(gòu)的并行處理機(jī)相比，其主要差別在于系統(tǒng)存儲(chǔ)器是由K個(gè)存儲(chǔ)體(SM0～SMK-1)集中構(gòu)成，經(jīng)互連網(wǎng)絡(luò)ICN為整個(gè)系統(tǒng)的N個(gè)處理單元所共享。采用這種結(jié)構(gòu)的典型機(jī)器有Burroughs公司和伊里諾大學(xué)聯(lián)合研制的科學(xué)處理機(jī)BSP(BurroughsScientificProcessor)。并行處理機(jī)的特點(diǎn)1．資源重復(fù)2．連接模式3．專用性4．復(fù)合性并行處理機(jī)的算法在并行處理機(jī)上并行算法的研究是與結(jié)構(gòu)緊密聯(lián)系在一起的，并行處理機(jī)處理單元陣列的結(jié)構(gòu)是為適應(yīng)一定類型計(jì)算問(wèn)題而設(shè)計(jì)的專門(mén)結(jié)構(gòu)。這里，以ILLIAC-IV為例，討論幾種并行處理機(jī)上的常用算法。這些算法本身不帶有任何原理上的局限性，對(duì)其他并行處理機(jī)同樣具有典型意義。ILLIAC-IV的處理單元陣列結(jié)構(gòu)在這個(gè)陣列中，任意兩個(gè)PU之間的通信可以用軟件方法尋找最短路徑進(jìn)行，其最短距離都不會(huì)超過(guò)七步。例如，從PU9到PU55的通信路徑為PU9→PU1→PU0→PU63→PU55，只需四步。一般而言，在n×n個(gè)PU組成的陣列中，任意兩個(gè)處理單元之間的最短距離不會(huì)超過(guò)n-1步。2．陣列處理機(jī)的并行算法(1)矩陣加(2)矩陣乘(3)累加和(1)矩陣加設(shè)A和B是n×n階矩陣，A、B相加的和矩陣為C，它也是n×n階矩陣。矩陣加的算法為計(jì)算cij時(shí)只與aij和bij有關(guān)，所以把a(bǔ)ij和bij分布在同一個(gè)處理單元的PEM中，而結(jié)果cij也存放在此PEM中。在全部64個(gè)PEM中，令A(yù)的分量單元均為同一地址d，B的分量單元均為同一地址d+l，而結(jié)果矩陣C的各分量也相應(yīng)存放于各PEM同一地址為d+2的單元內(nèi)，圖5.4給出了處理單元個(gè)數(shù)為64，A、B、C為8×8矩陣的存儲(chǔ)器分配示意圖，其中d為存儲(chǔ)器地址對(duì)于這樣的矩陣加運(yùn)算，只需用三條ILLIAC-IV的匯編指令就可以一次實(shí)現(xiàn)。LDA ALPHA ；全部(d)由PEMi送PEi的累加器RGAiADRN ALPHA+l ；全部(d+1)號(hào)(RGAi)進(jìn)行浮點(diǎn)加，結(jié)果送RGAiSTA ALPHA+2 ；全部(RGAi)由PEi送PEMi的d+2單元這里，0≤i≤63。由以上過(guò)程可以看出，并行處理機(jī)具有單指令流（三條指令順序執(zhí)行）多數(shù)據(jù)流（64個(gè)元素并行相加）以及數(shù)組運(yùn)算中的“全并行”等工作特點(diǎn)。矩陣乘設(shè)A和B是n×n階矩陣，A、B的乘積矩陣C也是n×n階矩陣。矩陣乘的傳統(tǒng)串行算法為若n=8，A、B和C均為8×8的矩陣。在SIMD陣列處理機(jī)上求解，可執(zhí)行下列用FORTRAN語(yǔ)言編寫(xiě)的程序： DO 10 I=0，7 C(I，J)=0 DO 10 K=0，710 C(I，J)=C(I，J)+A(I，K)*B(K，J)類似的計(jì)算在SISD計(jì)算機(jī)上要用K、I、J三重循環(huán)才能完成，每重循環(huán)執(zhí)行八次，共需512次乘、加時(shí)間（不考慮其他循環(huán)控制指令所需時(shí)間）。在SIMD計(jì)算機(jī)上執(zhí)行上述程序時(shí)，可用八個(gè)處理單元并行計(jì)算矩陣C(I，J)的某一行，即將J循環(huán)轉(zhuǎn)化成一維的向量處理，只需一次計(jì)算即可完成，其余K、I兩重循環(huán)，僅需64次乘、加時(shí)間，速度可提高至八倍。程序執(zhí)行流程如圖5.5所示。累加和累加和并行算法是將N個(gè)數(shù)的順序相加過(guò)程變?yōu)椴⑿邢嗉舆^(guò)程。例如，某一個(gè)向量含N個(gè)元素，求這些元素的累加和。如果在SISD計(jì)算機(jī)中采用串行方法來(lái)完成則需要進(jìn)行N-l次加法；如果在SIMD并行處理機(jī)上采用遞歸折疊方法，用N個(gè)處理單元來(lái)求和，則可以提高并行求和速度。假設(shè)處理單元的個(gè)數(shù)為八整個(gè)累加求和過(guò)程僅需lb8=3次并行傳送和三次并行相加。5.2并行處理機(jī)的互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)是一種由開(kāi)關(guān)元件按照一定的拓?fù)浣Y(jié)構(gòu)和控制方式將集中式系統(tǒng)或分布式系統(tǒng)中的結(jié)點(diǎn)連接起來(lái)所構(gòu)成的網(wǎng)絡(luò)，這些結(jié)點(diǎn)可能是處理器、存儲(chǔ)模塊或者其他設(shè)備，它們通過(guò)互連網(wǎng)絡(luò)相互連接并進(jìn)行信息交換?；ミB網(wǎng)絡(luò)已成為并行處理系統(tǒng)的核心組成部分，它對(duì)并行處理系統(tǒng)的性能起著決定性的作用。互連網(wǎng)絡(luò)設(shè)計(jì)的相關(guān)內(nèi)容1．操作方式：分為同步和異步兩種。2．控制策略：分為集中和分散兩種。3．交換方式：線路交換和分組交換兩種。4.網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)：分為靜態(tài)網(wǎng)絡(luò)(staticnetwork)和動(dòng)態(tài)網(wǎng)絡(luò)(dynamicnetwork)兩種。網(wǎng)絡(luò)部件1．鏈路。用來(lái)將計(jì)算機(jī)系統(tǒng)中兩個(gè)硬件部件進(jìn)行物理連接。2．交換開(kāi)關(guān)。交換開(kāi)關(guān)(switch)也稱為路由器(router)，它用于建立交換網(wǎng)絡(luò)。3．網(wǎng)絡(luò)接口電路。網(wǎng)絡(luò)接口電路(NIC，NetworkInterfaceCircuit)也稱為網(wǎng)卡(networkinterfacecard)，它常用于將一臺(tái)主機(jī)連接到某個(gè)網(wǎng)絡(luò)上?；ミB函數(shù)互連函數(shù)用于描述互連網(wǎng)絡(luò)的連接特性，每種互連網(wǎng)絡(luò)可用一組互連函數(shù)來(lái)描述。如果把互連網(wǎng)絡(luò)的N個(gè)入端和N個(gè)出端（N-2n）分別用編號(hào)0、l、…、N-l來(lái)表示，那么互連函數(shù)則表示互連網(wǎng)絡(luò)的入端號(hào)與出端號(hào)之間的一一對(duì)應(yīng)關(guān)系。互連函數(shù)一般有兩種表示形式：1.互連網(wǎng)絡(luò)中入、出端對(duì)應(yīng)連接表示法。2.函數(shù)表示法。下面介紹幾種基本單級(jí)互連網(wǎng)絡(luò)的互連函數(shù)1．立方體立方體的每個(gè)頂點(diǎn)代表一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的編號(hào)用二進(jìn)制碼(C2ClC0)表示。立方體單級(jí)網(wǎng)絡(luò)的互連函數(shù)實(shí)現(xiàn)二進(jìn)制編號(hào)中第k位值不同的結(jié)點(diǎn)之間的連接，故三維的立方體單級(jí)網(wǎng)絡(luò)有三種互連函數(shù)-Cube0、Cube1和Cube2，分別建立結(jié)點(diǎn)編號(hào)中C0不同或Cl不同或C2不同的結(jié)點(diǎn)之間的連接，其連接方式如圖5.9所示。一般情況下，一個(gè)n維立方體有N=2n個(gè)結(jié)點(diǎn)，共有n種互連函數(shù)，分別由n位編號(hào)中的每一位的位值求反來(lái)確定，即PM2I（是加減2i的簡(jiǎn)稱，plus-minus2i）PM2I單級(jí)網(wǎng)絡(luò)能實(shí)現(xiàn)j號(hào)結(jié)點(diǎn)與

號(hào)結(jié)點(diǎn)的直接相連，N為處理器的個(gè)數(shù)，n=lbN。因此，它共有2n個(gè)互連函數(shù)，即設(shè)N=8，則各互連循環(huán)為

PM2I單級(jí)網(wǎng)絡(luò)的最大距離為[n/2]。在圖5.10中給出了PM21互連網(wǎng)絡(luò)的部分連接圖。3．混洗交換混洗交換(shuffle-exchange)互連網(wǎng)絡(luò)包含全混洗和交換兩種互連函數(shù)。(1)全混洗

全混洗的互連函數(shù)為由此可知，是將入端二進(jìn)制編號(hào)循環(huán)左移一位即得到對(duì)應(yīng)出端的二進(jìn)制編號(hào)。圖5.11所示是八個(gè)結(jié)點(diǎn)的全混連接。(2)交換由于單一的全混洗互連網(wǎng)絡(luò)不能實(shí)現(xiàn)二進(jìn)制編號(hào)為全0和全1的結(jié)點(diǎn)與其他任何結(jié)點(diǎn)的連接，所以又增加了Cube0交換互連函數(shù)。同時(shí)采用了全混洗和交換的單級(jí)互連網(wǎng)絡(luò)稱為混洗交換單級(jí)互連網(wǎng)絡(luò)，其連接如圖5.12所示。圖5.12中虛線表示全混，實(shí)線表示交換。在混洗交換網(wǎng)絡(luò)中，最遠(yuǎn)的兩個(gè)入、出端號(hào)是全0和全1，它們的連接需要經(jīng)過(guò)n次交換和n-l次混洗，所以混洗交換網(wǎng)絡(luò)的最大距離為2n-l。4．蝶形蝶形(butterfly)互連網(wǎng)絡(luò)的互連函數(shù)為它將入端二進(jìn)制編號(hào)的最高位和最低位互換位置即可得相應(yīng)出端的二進(jìn)制編號(hào)?；ミB函數(shù)特性參數(shù)1．互連網(wǎng)絡(luò)的結(jié)構(gòu)特性參數(shù)2．互連網(wǎng)絡(luò)的傳輸特性參數(shù)1．互連網(wǎng)絡(luò)的結(jié)構(gòu)特性參數(shù)互連網(wǎng)絡(luò)的網(wǎng)絡(luò)拓?fù)?networkingtopology)可用有向邊或無(wú)向邊連接有限個(gè)結(jié)點(diǎn)的圖來(lái)表示。利用圖的有關(guān)參數(shù)能定義出互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的若干結(jié)構(gòu)特性參數(shù)。(1)網(wǎng)絡(luò)規(guī)模網(wǎng)絡(luò)中的結(jié)點(diǎn)數(shù)稱為網(wǎng)絡(luò)規(guī)模(networksize)，它表示該網(wǎng)絡(luò)所能連接的部件個(gè)數(shù)。(2)結(jié)點(diǎn)度與結(jié)點(diǎn)相連接的邊（鏈路或通道）數(shù)稱為結(jié)點(diǎn)度(nodedegree)。在單向鏈路的情況下，進(jìn)入結(jié)點(diǎn)的鏈路數(shù)稱為入度(indegree)，而從結(jié)點(diǎn)出來(lái)的鏈路數(shù)則稱為出度(outdegree)，結(jié)點(diǎn)度為二者之和。(3)網(wǎng)絡(luò)直徑網(wǎng)絡(luò)直徑(networkdiameter)是網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)間最短路徑的最大值。(4)網(wǎng)絡(luò)等分寬度一個(gè)有n個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)的等分平面是一組連線，移去它將把網(wǎng)絡(luò)分為兩個(gè)n/2個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)。一個(gè)網(wǎng)絡(luò)可以有許多個(gè)等分平面。最小的等分平面是指具有最小連線數(shù)的等分平面。網(wǎng)絡(luò)的等分寬度(networkbisectionwidth)是指對(duì)半分割網(wǎng)絡(luò)時(shí)所必須移去的最少邊數(shù)。(5)網(wǎng)絡(luò)對(duì)稱性所謂網(wǎng)絡(luò)對(duì)稱性(networksymmetry)指的是，如果從網(wǎng)絡(luò)任意結(jié)點(diǎn)看上去網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)都是相同的，便稱該網(wǎng)絡(luò)是對(duì)稱的，否則網(wǎng)絡(luò)是非對(duì)稱的。(6)數(shù)據(jù)尋徑數(shù)據(jù)尋徑是指在網(wǎng)絡(luò)通信中對(duì)路徑的選擇與指定。數(shù)據(jù)尋徑網(wǎng)絡(luò)一對(duì)一通信也稱點(diǎn)對(duì)點(diǎn)(point-to-point)通信，僅有一個(gè)發(fā)送者和一個(gè)接收者。一對(duì)多通信包括廣播(broadcast)和散射(scatter)兩種。廣播操作是指其中一個(gè)進(jìn)程（或稱根進(jìn)程）向所有進(jìn)程（包括自己）發(fā)送相同消息；散射操作則是由根進(jìn)程對(duì)不同進(jìn)程發(fā)送一個(gè)不同的消息。多對(duì)一通信包括聚集(gather)和歸約(reduction)兩種。聚集操作是指根進(jìn)程從每個(gè)進(jìn)程處接收一個(gè)不同消息，所以根進(jìn)程共接收了行個(gè)消息，這里的理是組的大小；歸約是指某個(gè)根進(jìn)程接收來(lái)自每個(gè)進(jìn)程（包括自己）的局部值，并將它們?cè)诟M(jìn)程中歸約求和形成一個(gè)最終值。多對(duì)多通信中最簡(jiǎn)單的形式是置換(permutation)，其中每個(gè)進(jìn)程只向一個(gè)進(jìn)程發(fā)送并只接收一個(gè)進(jìn)程發(fā)來(lái)的消息，如循環(huán)移位(circularshift)、掃描(scan)、全交換(totalexchange)等。圖5.14互連網(wǎng)絡(luò)的傳輸特性參數(shù)時(shí)延(Iatency)和帶寬(bandwidth)是用來(lái)評(píng)估網(wǎng)絡(luò)傳輸性能或系統(tǒng)互連性能的兩種基本參數(shù)。通信時(shí)延是指網(wǎng)絡(luò)中從源結(jié)點(diǎn)到目的結(jié)點(diǎn)傳輸一條消息所需的總時(shí)間。該時(shí)延包括四部分：在網(wǎng)絡(luò)兩端，相應(yīng)收發(fā)消息的軟件開(kāi)銷；由于通道占用導(dǎo)致的通道時(shí)延；在沿尋徑路徑做一系列尋徑?jīng)Q策期間花費(fèi)的尋徑時(shí)延；由于網(wǎng)絡(luò)傳輸競(jìng)爭(zhēng)導(dǎo)致的競(jìng)爭(zhēng)時(shí)延。網(wǎng)絡(luò)時(shí)延。軟件開(kāi)銷和競(jìng)爭(zhēng)時(shí)延依賴于程序行為，故而將通道時(shí)延和尋徑時(shí)延之和稱為網(wǎng)絡(luò)時(shí)延，其大小完全由網(wǎng)絡(luò)硬件特征決定，與程序行為和網(wǎng)絡(luò)傳輸狀況無(wú)關(guān)。結(jié)點(diǎn)帶寬。網(wǎng)絡(luò)中從任意結(jié)點(diǎn)到其他結(jié)點(diǎn)每秒鐘傳輸消息的最大位數(shù)或字節(jié)數(shù)。在對(duì)稱網(wǎng)絡(luò)中，結(jié)點(diǎn)帶寬和結(jié)點(diǎn)位置無(wú)關(guān)，非對(duì)稱網(wǎng)絡(luò)中的結(jié)點(diǎn)帶寬定義為所有結(jié)點(diǎn)帶寬的最小值。聚集帶寬。對(duì)于一個(gè)給定網(wǎng)絡(luò)，聚集帶寬定義為從一半結(jié)點(diǎn)到另一半結(jié)點(diǎn)每秒鐘傳輸消息的最大位數(shù)或字節(jié)數(shù)。等分帶寬。網(wǎng)絡(luò)的等分帶寬(bisectionbandwidth)是指每秒鐘內(nèi)在網(wǎng)絡(luò)的最小等分平面上通過(guò)所有連線的最大信息位數(shù)或字節(jié)數(shù)靜態(tài)連接網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)在各結(jié)點(diǎn)間使用直接鏈路，且一旦構(gòu)成后就固定不變。這種網(wǎng)絡(luò)比較適合構(gòu)造通信模式可預(yù)測(cè)或可用靜態(tài)連接實(shí)現(xiàn)的并行處理系統(tǒng)和分布計(jì)算機(jī)系統(tǒng)。1．線性陣列線性陣列(lineararray)是一種一維線性網(wǎng)絡(luò)，用N-l條鏈路將N個(gè)結(jié)點(diǎn)連成一行，如圖5.15(a)所示。線性陣列是連接最簡(jiǎn)單的拓?fù)浣Y(jié)構(gòu)，其內(nèi)部結(jié)點(diǎn)度為2，端結(jié)點(diǎn)度為1，為不對(duì)稱結(jié)構(gòu)。網(wǎng)絡(luò)直徑為N-l，等分寬度為1，當(dāng)N很大時(shí)，通信效率很低。2．環(huán)和帶弦環(huán)環(huán)(ring)是將線性陣列的兩個(gè)端結(jié)點(diǎn)用一條附加鏈路連接在一起構(gòu)成的。環(huán)是對(duì)稱結(jié)構(gòu)，結(jié)點(diǎn)度為2。雙向環(huán)直徑為

，單向環(huán)直徑為N。在環(huán)的結(jié)點(diǎn)上增加一條或兩條附加鏈路，即可得到結(jié)點(diǎn)度分別為3和4的帶弦環(huán)(chordalring)，16個(gè)結(jié)點(diǎn)的環(huán)(b)與帶弦環(huán)(c)和(d)相比，網(wǎng)絡(luò)直徑由8分別減至5和3。3．循環(huán)移數(shù)網(wǎng)絡(luò)和全連接循環(huán)移數(shù)網(wǎng)絡(luò)(barrelshifter)是將環(huán)上每個(gè)結(jié)點(diǎn)到所有與其距離為2的整數(shù)冪的結(jié)點(diǎn)之間都增加一條附加鏈路而構(gòu)成的。圖5.15(e)所示為N=16的循環(huán)移數(shù)網(wǎng)絡(luò)。若循環(huán)移數(shù)網(wǎng)絡(luò)的規(guī)模為N=2n，則循環(huán)移數(shù)網(wǎng)絡(luò)的結(jié)點(diǎn)度為2n-1，網(wǎng)絡(luò)直徑為n/2。全連接網(wǎng)絡(luò)(completelyconnectednetwork)是環(huán)上任意兩個(gè)結(jié)點(diǎn)間都有附加鏈路連接。16個(gè)結(jié)點(diǎn)的全連接網(wǎng)絡(luò)如圖5.15(f)所示。這種全連接網(wǎng)絡(luò)是一個(gè)對(duì)稱的網(wǎng)絡(luò)，當(dāng)網(wǎng)絡(luò)規(guī)模為N時(shí)，結(jié)點(diǎn)度為N-l，網(wǎng)絡(luò)直徑為1，鏈路數(shù)為N(N-l)/2。4．樹(shù)形和星形圖5.16(a)所示的是一棵五層31個(gè)結(jié)點(diǎn)的二叉樹(shù)(binarytree)。頂部的一個(gè)結(jié)點(diǎn)稱為根，底部的16個(gè)結(jié)點(diǎn)稱為葉子，其他的稱為中間結(jié)點(diǎn)。除了葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)。一棵k層完全平衡的二叉樹(shù)應(yīng)有N=2k-1個(gè)結(jié)點(diǎn)，最大結(jié)點(diǎn)度為3，直徑為2（k-l）。二叉樹(shù)是一種可擴(kuò)展的結(jié)構(gòu)，但其直徑較長(zhǎng)。星形(star)是一種二層樹(shù)，結(jié)點(diǎn)度為N-l，網(wǎng)絡(luò)直徑為常數(shù)2。圖5.16(b)所示的是一個(gè)結(jié)點(diǎn)數(shù)為9的星形網(wǎng)絡(luò)。5．胖樹(shù)形傳統(tǒng)二叉樹(shù)根部的交通最忙，所以二叉樹(shù)中的根結(jié)點(diǎn)可能會(huì)成為性能瓶頸，胖樹(shù)形(fattree)使得這一問(wèn)題得到改善。二叉胖樹(shù)(binaryfattree)結(jié)構(gòu)如圖5.16(c)所示，胖樹(shù)的鏈路數(shù)從葉結(jié)點(diǎn)往根結(jié)點(diǎn)上行方向逐漸增多。6．網(wǎng)格形和環(huán)網(wǎng)形一個(gè)3×3網(wǎng)格(mesh)形網(wǎng)絡(luò)如圖5.17(a)所示。一般而言，網(wǎng)絡(luò)規(guī)模為N=nk個(gè)結(jié)點(diǎn)的k維網(wǎng)格的網(wǎng)絡(luò)直徑為k（n一1），內(nèi)部結(jié)點(diǎn)度為2k，而邊結(jié)點(diǎn)和角結(jié)點(diǎn)的結(jié)點(diǎn)度分別為3和2。因各種結(jié)點(diǎn)的度不相同，故圖5.17(a)所示的純網(wǎng)格形網(wǎng)絡(luò)應(yīng)為不對(duì)稱結(jié)構(gòu)。圖5.17(b)所示為一種呈閉合螺線狀回繞連接的網(wǎng)格網(wǎng)。ILLIAC-IV系統(tǒng)采用的就是這種拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)，故稱這種結(jié)構(gòu)為ILLIAC網(wǎng)，它是一種不對(duì)稱的拓?fù)浣Y(jié)構(gòu)。一個(gè)N=n×n的ILLIAC網(wǎng)的網(wǎng)絡(luò)直徑為n-l，僅為純網(wǎng)格直徑的一半。圖5.17(c)所示的環(huán)網(wǎng)形(torus)結(jié)構(gòu)是將環(huán)形和網(wǎng)格組合在一起，環(huán)網(wǎng)形陣列的每行每列都有環(huán)形連接。一個(gè)N=n×n的二維環(huán)網(wǎng)的結(jié)點(diǎn)度為4，直徑為2×

。環(huán)網(wǎng)形網(wǎng)絡(luò)是一種對(duì)稱性的拓?fù)浣Y(jié)構(gòu)，并能向高維擴(kuò)展。7．搏動(dòng)式陣列搏動(dòng)式陣列(systolicarray)通常是為實(shí)現(xiàn)某種特定數(shù)據(jù)流算法而設(shè)計(jì)的一類多維流水線陣列結(jié)構(gòu)。圖5.17(d)所示就是實(shí)現(xiàn)矩陣相乘的搏動(dòng)式陣列，其內(nèi)部結(jié)點(diǎn)度為6。這種結(jié)構(gòu)可在多個(gè)方向上使數(shù)據(jù)流變成以流水線方式工作。8．超立方體超立方體(hypercube)是一種二元n維立方體結(jié)構(gòu)。通常，一個(gè)n-立方體由N=2n個(gè)結(jié)點(diǎn)組成，它們分布在n維上，每維有兩個(gè)結(jié)點(diǎn)，這就是所謂二元n維的含義。圖5.18(a)所示為八個(gè)結(jié)點(diǎn)的3-立方體結(jié)構(gòu)。它沿著每個(gè)方向的結(jié)點(diǎn)數(shù)為2，總結(jié)點(diǎn)數(shù)N=8=23個(gè)，故也可稱為二元3-立方體結(jié)構(gòu)。4-立方體結(jié)構(gòu)可通過(guò)將兩個(gè)3-立方體的相應(yīng)結(jié)點(diǎn)互連得到，如圖5.18(b)所示。沿每個(gè)方向結(jié)點(diǎn)數(shù)為2，總結(jié)點(diǎn)數(shù)為16，即N=24，維數(shù)為4，故稱為二元4-立方體結(jié)構(gòu)。n-立方體的結(jié)點(diǎn)度等于n，即網(wǎng)絡(luò)的直徑為n。9．帶環(huán)立方體帶環(huán)立方體(cube-connectedcycle)結(jié)構(gòu)從超立方體結(jié)構(gòu)改進(jìn)而來(lái)。圖5.18(c)所示為帶環(huán)3-立方體（簡(jiǎn)稱3-CCC），它是用含三個(gè)結(jié)點(diǎn)的結(jié)點(diǎn)環(huán)代替3-立方體的每個(gè)角結(jié)點(diǎn)（頂角）而得到的。從一個(gè)k-立方體構(gòu)成一個(gè)有n=2k個(gè)結(jié)點(diǎn)環(huán)的帶環(huán)k-立方體的方法，是用是k個(gè)結(jié)點(diǎn)的環(huán)取代k維超立方體的每個(gè)頂點(diǎn)，如圖5.18(d)所示。10.k元n-立方體網(wǎng)絡(luò)k元n-立方體網(wǎng)絡(luò)中的參數(shù)k是沿每個(gè)方向的結(jié)點(diǎn)數(shù)，n是立方體的維數(shù)。這兩個(gè)數(shù)與網(wǎng)絡(luò)中總結(jié)點(diǎn)數(shù)N的關(guān)系為

N=kn

（n=logkN）圖5.19 k=4和n=3的k元n-立方體網(wǎng)絡(luò)

（未畫(huà)出隱藏部分的結(jié)點(diǎn)和連接）表5.1匯總了靜態(tài)連接網(wǎng)絡(luò)的重要特性。其中網(wǎng)絡(luò)的結(jié)點(diǎn)度越大，表示連接性越好，但鏈路數(shù)總體上會(huì)隨結(jié)點(diǎn)度的增加而增加，這樣會(huì)使得網(wǎng)絡(luò)的迮接趨于復(fù)雜，成本也會(huì)趨高。因此，在能實(shí)現(xiàn)所有結(jié)點(diǎn)間連接的前提下，結(jié)點(diǎn)度應(yīng)越小越好，相應(yīng)的網(wǎng)絡(luò)時(shí)延也是越小越好。等分寬度越大，表示網(wǎng)絡(luò)的帶寬就越大。網(wǎng)絡(luò)直徑越大，則意味著通信的時(shí)間延遲越大。從表中顯示網(wǎng)絡(luò)直徑有很大的變化范圍，但隨著蟲(chóng)蝕尋徑等硬件尋徑技術(shù)的不斷完善，網(wǎng)絡(luò)直徑已不是一個(gè)嚴(yán)重問(wèn)題，因?yàn)槿我鈨山Y(jié)點(diǎn)間的通信延遲在高度流水線操作下幾乎是固定不變的。[例5.1]設(shè)計(jì)一種采用加、乘和數(shù)據(jù)尋徑操作的算法，分別在下面的計(jì)算機(jī)系統(tǒng)上用最短的時(shí)間來(lái)計(jì)算表達(dá)式S=A1×B1+A2×B2+…+A32×B32。假設(shè)加法和乘法分別需要兩個(gè)和四個(gè)單位時(shí)間，從存儲(chǔ)器取指令、取數(shù)據(jù)、譯碼的時(shí)間忽略不計(jì)，并假定所有的指令和數(shù)據(jù)已裝入有關(guān)的PE，試確定下列每種情況的最小計(jì)算時(shí)間。一臺(tái)串行計(jì)算機(jī)，處理機(jī)中有一個(gè)加法器和一個(gè)乘法器，同一時(shí)刻只有其中一個(gè)可以使用。(2)一臺(tái)有八個(gè)PE(PE0、PEl…PE7)的SIMD計(jì)算機(jī)，八個(gè)PE連成雙向環(huán)結(jié)構(gòu)。每個(gè)PE用一個(gè)單位時(shí)間可以把數(shù)據(jù)直接送給它的相鄰PE。操作數(shù)Ai和Bi最初存放在PEj(mod8)中，其中i=1，2，…，32。每個(gè)PE可在不同時(shí)刻執(zhí)行加法或乘法。(3)若將(2)中八個(gè)PE之間的連接由雙向環(huán)結(jié)構(gòu)改為單向環(huán)結(jié)構(gòu)，結(jié)果又如何？解：(1)采用單處理機(jī)系統(tǒng)串行處理不需要數(shù)據(jù)尋徑操作，所需的計(jì)算時(shí)間為t=32×4+31×2=190（單位時(shí)間）(2)根據(jù)題意，畫(huà)出八個(gè)PE的雙向環(huán)連接圖和操作數(shù)的初始存放位置，如圖5.20所示。數(shù)據(jù)尋徑操作的算法如下：每個(gè)PE同時(shí)執(zhí)行乘法四次，加法三次。PE0→PE7、PE1→PE7、PE6→PE5、PE3→PE4同時(shí)傳遞和一次，再加法一次。PE7→PE6→PE3、PE2→PE3→PE4同時(shí)傳遞和二次，再加法一次。PE4→PE5傳遞和一次，最后加法一次。因此，八個(gè)PE雙向環(huán)并行處理所需的最小時(shí)間為t=4×4+3×2+1+2+2+2+1+2=32（單位時(shí)間）(3)若將(2)中八個(gè)PE之間的連接由雙向環(huán)結(jié)構(gòu)改為單向環(huán)結(jié)構(gòu)，則八個(gè)PE的連接圖和操作數(shù)的初始存放位置如圖5.21所示。數(shù)據(jù)尋徑操作的算法如下：每個(gè)PE同時(shí)執(zhí)行乘法四次，加法三次。PE0→PE1、PE2→PE3、PE4→PE5、PE6→PE7同時(shí)傳遞和、再加法一次。PE1→PE2→PE3、PE5→PE6→PE7同時(shí)傳遞和二次，再加法一次。PE3→PE4→PE5→PE6→PE7傳遞和四次，最后加法一次。因此，八個(gè)PE雙向環(huán)并行處理所需的最小時(shí)間為t=4×4+3×2+1+2+2+2+5+2=35（單位時(shí)間）推廣到一般情況略去動(dòng)態(tài)連接網(wǎng)絡(luò)動(dòng)態(tài)連接網(wǎng)絡(luò)可根據(jù)程序要求實(shí)現(xiàn)所需的通信模式。它不用固定連接，而是沿著連接

路徑使用開(kāi)關(guān)或仲裁器以提供動(dòng)態(tài)連接特性。根據(jù)級(jí)間連接方式，動(dòng)態(tài)連接網(wǎng)絡(luò)有單級(jí)相多級(jí)兩類。單級(jí)網(wǎng)絡(luò)只有有限的幾種連接，

任意兩個(gè)結(jié)點(diǎn)之間的信息傳送可能需經(jīng)過(guò)在單級(jí)網(wǎng)絡(luò)中循環(huán)多次才能實(shí)現(xiàn)，故單級(jí)網(wǎng)絡(luò)也

稱循環(huán)網(wǎng)絡(luò)。多級(jí)網(wǎng)絡(luò)由多個(gè)單級(jí)網(wǎng)絡(luò)串聯(lián)組合而成，以實(shí)現(xiàn)任意兩個(gè)結(jié)點(diǎn)之間的連接。

級(jí)間連接模式的選擇取決于網(wǎng)絡(luò)連接特性，不同級(jí)的連接模式可能相同也可能不相同。在

此基礎(chǔ)上，還可將多級(jí)互連網(wǎng)絡(luò)循環(huán)使用，以實(shí)現(xiàn)復(fù)雜的互連。1．總線互連方式的動(dòng)態(tài)連接網(wǎng)絡(luò)總線互連方式是實(shí)現(xiàn)動(dòng)態(tài)連接最簡(jiǎn)單的一種結(jié)構(gòu)形式。用一條公用系統(tǒng)總線將多個(gè)處

理機(jī)、存儲(chǔ)器模塊和I/()部件通過(guò)各自的接口部件或是多個(gè)由CPU、本地存儲(chǔ)器和I/O部件所組成的計(jì)算機(jī)模塊通過(guò)公共的接口部件互連起來(lái)。2．交叉開(kāi)關(guān)互連方式的動(dòng)態(tài)連接網(wǎng)絡(luò)交叉開(kāi)關(guān)(crossbar)互連由一組縱橫開(kāi)關(guān)陣列組成，將橫向的p個(gè)處理機(jī)P及i個(gè)I/O模塊與縱向的m個(gè)存儲(chǔ)器模塊M連接起來(lái)。每個(gè)處理機(jī)和I/O設(shè)備都能分到一套總線與某個(gè)存儲(chǔ)器相連，從而大大加寬互連傳輸帶寬，提高系統(tǒng)效率，與總線互連中采用分時(shí)使用總線不同，交叉開(kāi)關(guān)采用的是空間分配機(jī)制3．多級(jí)網(wǎng)絡(luò)互連方式的動(dòng)態(tài)連接網(wǎng)絡(luò)是將多套單級(jí)互連網(wǎng)絡(luò)通過(guò)開(kāi)關(guān)模塊串聯(lián)擴(kuò)展成多級(jí)互連網(wǎng)絡(luò)(MultistageInterconnectonNetwork)。與單級(jí)網(wǎng)絡(luò)相比，多級(jí)網(wǎng)絡(luò)可以通過(guò)改變開(kāi)關(guān)的控制方式靈活的實(shí)現(xiàn)各種互連。常見(jiàn)多級(jí)互連網(wǎng)絡(luò)：多級(jí)立方體網(wǎng)絡(luò)多級(jí)混洗交換網(wǎng)絡(luò)多級(jí)PM2I網(wǎng)絡(luò)基準(zhǔn)網(wǎng)絡(luò)多級(jí)CLOS網(wǎng)絡(luò)多級(jí)BENES可重排網(wǎng)絡(luò)4．蝶式網(wǎng)絡(luò)多級(jí)蝶式網(wǎng)絡(luò)是用交叉開(kāi)關(guān)將單級(jí)蝶式網(wǎng)絡(luò)連成模塊構(gòu)成的，圖5.36所示是兩個(gè)規(guī)模不同的蝶式網(wǎng)絡(luò)。圖5.36(a)是一個(gè)由16個(gè)8×8交叉開(kāi)關(guān)構(gòu)成的兩級(jí)64×64蝶式網(wǎng)絡(luò)，級(jí)間采用8路混洗連接；圖5.36(b)是有512個(gè)輸入端的三級(jí)蝶式網(wǎng)絡(luò)結(jié)構(gòu)，同樣也由8×8交叉開(kāi)關(guān)構(gòu)成。圖5.36(b)中的每個(gè)64×64方框相當(dāng)于圖5.36(a)