計算機系統(tǒng)結(jié)構(gòu)第一章基本概念第二章指令系統(tǒng)第三章存儲系統(tǒng)第四章輸入輸出系統(tǒng)第五章標(biāo)量處理機第六章向量處理機第七章互連網(wǎng)絡(luò)第八章并行處理機第九章多處理機1互連網(wǎng)絡(luò)是一種由開關(guān)元件按照一定的拓撲結(jié)構(gòu)和控制方式構(gòu)成的網(wǎng)絡(luò)用于實現(xiàn)計算機系統(tǒng)內(nèi)部多個處理機或多個功能部件之間的相互連接第七章互連網(wǎng)絡(luò)2第七章互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)的基本概念消息傳遞機制37.1互連網(wǎng)絡(luò)的基本概念互連網(wǎng)絡(luò)的作用互連函數(shù)互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù)互連網(wǎng)絡(luò)的種類47.1.1互連網(wǎng)絡(luò)的作用用來實現(xiàn)計算機系統(tǒng)內(nèi)部多個處理機或多個功能部件之間的相互連接。為并行處理系統(tǒng)的核心組成部分。對整個計算機系統(tǒng)的性能價格比有著決定性的影響。5具有本地存儲器、私有高速緩存、共享存儲器和共享外圍設(shè)備的一般處理機系統(tǒng)的互連結(jié)構(gòu)IPMN(處理機-存儲器網(wǎng)絡(luò))PION(處理機-I/O網(wǎng)絡(luò))IPCN(處理機之間通信網(wǎng)絡(luò))P(處理機)C(高速緩沖存儲器)SM(共享存儲器)LM(本地存儲器)磁盤SM1SM2SMmIPMN……CnPnLMC1P1LMIPCN……………………PION磁帶打印機終端網(wǎng)絡(luò)…(共享存儲器)(共享I/O與外設(shè))67.1.2互連函數(shù)互連函數(shù)將互連網(wǎng)的N個輸入和N個輸出端分別用整數(shù)(0,1,2,...,N-1)來表示，則表示相互連接的輸出端號和輸入端號之間的一一對應(yīng)關(guān)系表示方法：互連函數(shù)法，圖形表示法,輸入輸出對應(yīng)表示法函數(shù)表示法：x表示輸入端號，常用n位二進制形式表示xn-1xn-2...x1x0f(x)表示互連函數(shù)，為：f(xn-1xn-2...x1x0)圖形表示法:用圖形表示輸入和輸出端之間的連接輸入輸出對應(yīng)(矩陣)表示法：循環(huán)表示法:把互連函數(shù)f(x)表示為：

(x0，x1，...，xj)(xk，xk+1，...，xl)...表示對應(yīng)關(guān)系為:f(x0)=x1，f(x1)=x2，...，f(xj)=x0

j+1稱為該循環(huán)的長度

012...N-1f(0)f(1)f(2)...f(N-1)7常用的互連函數(shù)如下：1恒等置換：

I(xn-1xn-2...

x1x0)=xn-1xn-2...x1x082交換置換Exchange實現(xiàn)二進制地址編號中第0位位值不同的輸入和輸出端之間的連接。

E(xn-1xn-2...

x1x0)=xn-1xn-2...

x1x0其他互連函數(shù)還有：方體置換、均勻洗牌置換、蝶式置換、位序顛倒置換、移數(shù)置換、加減2i置換93、方體置換Cube當(dāng)n=3時，共有3種函數(shù)，每種函數(shù)能夠表示8個結(jié)點之間的連接關(guān)系。由于交換函數(shù)主要用于超立方體互連網(wǎng)中，因此也稱為超立方體函數(shù)，用Cube表示，如：Cube0、Cube1、Cube2等。用交換函數(shù)構(gòu)成的互連網(wǎng)絡(luò)的結(jié)點度為n，網(wǎng)絡(luò)直徑也為n。10變化發(fā)生在0，1，2位分別是高2，1，0位相同的為一個組組內(nèi)加/減1，2，4C0C2C1114、均勻洗牌置換Perfectshuffle把二進制結(jié)點循環(huán)左移一位。子混洗(subshuffle)S(k)

最低k位循環(huán)左移一位超混洗牌(supershuffle)S(k)

最高k位循環(huán)左移一位顯然成立：逆混洗函數(shù)：教材P397L2,3,6錯124、均勻洗牌置換Perfectshuffle子洗牌是將整組數(shù)據(jù)分成若干個子組，對每個子組完成均勻洗牌變換。S(2)

分兩組0，1，2，3；4，5，6，7只用均勻洗牌函數(shù)不能實現(xiàn)任意結(jié)點之間的互連通常用均勻洗牌函數(shù)與其他函數(shù)，如交換函數(shù)一起構(gòu)成互連網(wǎng)絡(luò)。均勻洗牌與逆均勻洗牌是兩種十分有用的互連函數(shù)以它們代表的鏈路與以交換置換代表的開關(guān)多級組合起來可構(gòu)成Omega(Ω)網(wǎng)絡(luò)與逆Omega(Ω^-1)網(wǎng)絡(luò)。

逆均勻洗牌是均勻洗牌的逆函數(shù)，兩者的輸入端和輸出端正好互換135、蝶式置換Butterfly蝶式函數(shù)的名稱來自于FFT變換時的圖形，如蝴蝶式樣。將輸入端二進制結(jié)點號的最高位和最低位互換位置。子蝶式(subbutterfly)B(k)最低k位的最高位與最低位互換位置超蝶式(superbutterfly)B(k)最高k位的最高位與最低位互換位置顯然成立教材P398L1,2錯145、蝶式置換Butterfly與全混洗函數(shù)類似，只用蝶式函數(shù)也不能實現(xiàn)任意結(jié)點之間的互連。156、位序顛倒置換BitReversal將輸入端二進制地址的位序反過來就得相應(yīng)輸出的地址。子反位序函數(shù)：最低k位的位序反過來超反位序函數(shù)：最高k位的位序反過來對于n=3的情況，正好有R=B，R(2)=B(2)，R(2)=B(2)。167、移數(shù)置換將輸入端數(shù)組循環(huán)移動一定的位置向輸出端傳輸。也可以將整個輸入數(shù)組分成若干個子數(shù)組，在子數(shù)組內(nèi)進行循環(huán)移數(shù)置換，這種段內(nèi)循環(huán)移數(shù)的表達式可寫成為兩個式子如下：

(a)移數(shù)量換k=2

(b)段內(nèi)移數(shù)置換k=1,r=2178、加減2i置換其中：0xN-1，0in-1，n=log2N。188、加減2i置換通常采用移數(shù)函數(shù)可以構(gòu)成環(huán)型網(wǎng)(包括單向環(huán)網(wǎng)、雙向環(huán)網(wǎng)、弦環(huán)網(wǎng))、方格網(wǎng)、移數(shù)網(wǎng)等。例如，Illiac函數(shù)是構(gòu)成IlliacIV陣列的基礎(chǔ)，它包含PM20和PM2n/2等四個互連函數(shù)。采用全部移數(shù)函數(shù)構(gòu)成網(wǎng)絡(luò)稱為移數(shù)網(wǎng)，移數(shù)網(wǎng)的結(jié)點度d=2n-1，網(wǎng)絡(luò)直徑D=n/2197.1.3互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù)1互連網(wǎng)絡(luò)的特性互連網(wǎng)絡(luò)通常是用有向邊或無向邊連接有限個結(jié)點的組成?；ミB網(wǎng)絡(luò)的主要特性有(1)網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點的個數(shù)(2)結(jié)點度：與結(jié)點相連接的邊數(shù)稱為結(jié)點度。包括入度和出度。進入結(jié)點的邊數(shù)叫入度，從結(jié)點出來的邊數(shù)則叫出度(3)距離：兩個結(jié)點之間相連的最少邊數(shù)(4)網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個結(jié)點間距離的最大值。用結(jié)點間的連接邊數(shù)表示207.1.3互連網(wǎng)絡(luò)的特性和傳輸?shù)男阅軈?shù)(5)等分寬度：當(dāng)某一網(wǎng)絡(luò)被切成相等的兩半時，沿切口的最小邊數(shù)(通道)稱為通道等分寬度，用b表示。于是線等分寬度就是B=b×w，w為通道寬度(用位表示)。等分寬度是說明沿等分網(wǎng)絡(luò)最大通信帶寬的一個參數(shù)。網(wǎng)絡(luò)的所有其它橫截面都應(yīng)限在等分寬度之內(nèi)。(6)結(jié)點間的線長：兩個結(jié)點間連線的長度。用米、公里等表示(7)對稱性：從任何結(jié)點看到拓撲結(jié)構(gòu)都是一樣的網(wǎng)絡(luò)稱為對稱網(wǎng)絡(luò)。對稱網(wǎng)絡(luò)比較易實現(xiàn)，編程也較容易。212互連網(wǎng)絡(luò)傳輸?shù)男阅軈?shù)一臺機器發(fā)送消息給另一臺機器時，發(fā)送方的步驟如下：(1)用戶程序把要發(fā)送的數(shù)據(jù)拷貝到操作系統(tǒng)的緩沖區(qū)。(2)操作系統(tǒng)把緩沖區(qū)中的數(shù)據(jù)打包，并發(fā)送的網(wǎng)絡(luò)接口部件。(3)網(wǎng)絡(luò)接口硬件開始發(fā)送消息。數(shù)據(jù)包的接收步驟如下：(1)把數(shù)據(jù)包從網(wǎng)絡(luò)接口部件拷貝到操作系統(tǒng)緩沖區(qū)。(2)檢查收到的數(shù)據(jù)包，如果正確，給接收方發(fā)回答信號。(3)把接收到的數(shù)據(jù)拷貝到用戶地址空間。發(fā)送方接收到回答信號后，釋放系統(tǒng)緩沖區(qū)22互連網(wǎng)絡(luò)在傳輸方面的主要性能參數(shù)(1)頻帶寬度(Bandwidth)： 互連網(wǎng)絡(luò)傳輸信息的最大速率(2)傳輸時間(Transmissiontime)： 等于消息長度除以頻寬(3)飛行時間(Timeofflight)：

第一位信息到達接收方所花費的時間(4)傳輸時延(Transportlatency)： 等于飛行時間與傳輸時間之和(5)發(fā)送方開銷(Senderoverhead)： 處理器把消息放到互連網(wǎng)絡(luò)的時間(6)接收方開銷(Receiveroverhead)： 處理器把消息從網(wǎng)絡(luò)取出來的時間23一個消息的總時延總時延=發(fā)送方開銷+飛行時間+消息長度/頻寬+接收方開銷24例7.1假設(shè)一個網(wǎng)絡(luò)的頻寬為10Mb/S，發(fā)送方開銷為230us，接收方開銷為270us。如果兩臺機器相距100米，現(xiàn)在要發(fā)送一個1000字節(jié)的消息給另一臺機器，試計算總時延。如果兩臺機器相距1000公里，那么總時延為多大？解光的速度為299792.5KM/S，信號在導(dǎo)體中傳遞速度大約是光速的50%，相距100米時總時延相距1000公里時的總時延257.1.4互連網(wǎng)絡(luò)的種類互連網(wǎng)絡(luò)的種類很多，分類方法也很多以互連特性為特征，可分為如下幾類靜態(tài)互連網(wǎng)絡(luò)：連接通路是固定的，一般靜態(tài)互連網(wǎng)絡(luò)不能實現(xiàn)任意結(jié)點到結(jié)點之間的互連循環(huán)互連網(wǎng)絡(luò)：通過多次重復(fù)使用同一個單級互連網(wǎng)絡(luò)以實現(xiàn)任意結(jié)點到結(jié)點之間的互連多級互連網(wǎng)絡(luò)：將多套相同的單級互連網(wǎng)絡(luò)連接起來，實現(xiàn)任意結(jié)點到結(jié)點之間的互連全排列互連網(wǎng)絡(luò)：不僅能夠?qū)崿F(xiàn)任意結(jié)點到結(jié)點之間的互連，而且能夠同時實現(xiàn)任意結(jié)點到結(jié)點之間的互連全交叉開關(guān)網(wǎng)絡(luò)：除了能夠同時實現(xiàn)任意結(jié)點到結(jié)點之間的互連之外，還能夠?qū)崿F(xiàn)廣播和多播261靜態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)是指在各結(jié)點間有專用的連接通路，且在運行中不能改變的網(wǎng)絡(luò)在靜態(tài)互連網(wǎng)絡(luò)中，每一個開關(guān)元件固定地與一個結(jié)點相連，建立該結(jié)點與鄰近結(jié)點之間的連接通路，直接實現(xiàn)兩結(jié)點間的通信一維的有線性陣列結(jié)構(gòu)二維的有環(huán)形、星形、樹形、網(wǎng)格形等三維的有立方體等三維以上的有超立方體等27(1)線性陣列一種一維網(wǎng)絡(luò)，其中N個結(jié)點用N-1條鏈路連成一行內(nèi)部的結(jié)點度為2，端點的結(jié)點度為1。直徑為N-1當(dāng)N大時，直徑也比較大。等分寬度b=1線性陣列是最簡單的拓撲結(jié)構(gòu)。這種結(jié)構(gòu)不對稱，當(dāng)N很大時，通信效率很低在N很小的情況下，如N=2，實現(xiàn)線性陣列是相當(dāng)經(jīng)濟的。由于直徑隨N線性增大，因此當(dāng)N比較大時，就不應(yīng)使用這種網(wǎng)絡(luò)了28(1)線性陣列線性陣列與總線的區(qū)別是很大的，后者是通過切換與其連接的許多結(jié)點來實現(xiàn)時分特性的線性陣列允許不同的源結(jié)點和目的結(jié)點對并發(fā)使用系統(tǒng)的不同部分(通道)

7654

89101115141312

012329(2)環(huán)和帶弦環(huán)(3)循環(huán)移數(shù)網(wǎng)絡(luò)采用移數(shù)函數(shù)。使用不同的移數(shù)函數(shù)，可以構(gòu)成多種環(huán)形網(wǎng)單向環(huán)行網(wǎng)右環(huán)網(wǎng)，采用PM2+0函數(shù)左環(huán)網(wǎng)，采用PM2-0函數(shù)雙向環(huán)行網(wǎng)：又稱為一維鄰居網(wǎng)，采用{PM2+0，PM2-0}函數(shù)環(huán)行網(wǎng)是對稱的，結(jié)點度是常數(shù)2雙向環(huán)網(wǎng)的直徑為N/2，單向環(huán)形網(wǎng)的直徑是N將結(jié)點度由2提高至3，可得到弦環(huán)網(wǎng)增加的弦愈多，則結(jié)點度愈高，網(wǎng)絡(luò)直徑愈小循環(huán)移數(shù)網(wǎng)絡(luò)也是一種環(huán)形網(wǎng)，它將環(huán)上每個結(jié)點與其距離為2的整數(shù)冪的結(jié)點之間連接構(gòu)成循環(huán)移數(shù)網(wǎng)的結(jié)點度為2n-1，直徑為[n/2]3010234576循環(huán)移數(shù)網(wǎng)(2)環(huán)和帶弦環(huán)(3)循環(huán)移數(shù)網(wǎng)絡(luò)0123456789101112131415度為3的帶弦環(huán)012345678910111213141531二叉樹網(wǎng)二叉胖樹網(wǎng)星形網(wǎng)(4)樹形和星形(5)胖樹形一棵k層完全平衡二叉樹有N=2^k-1個結(jié)點，結(jié)點度3，直徑2(k-1)星形是一種特殊的2層樹，結(jié)點度很高，為d=N-1，直徑2星形結(jié)構(gòu)已用于有集中監(jiān)督結(jié)點的系統(tǒng)中二叉胖樹的結(jié)點度從葉子結(jié)點往根結(jié)點逐漸增加胖樹緩解了一般二叉樹根結(jié)點通信速度高的矛盾32(6)網(wǎng)格和環(huán)網(wǎng)形網(wǎng)格網(wǎng)是一種比較流行的網(wǎng)絡(luò)結(jié)構(gòu)，有各種變體形式在IlliacIV、MPP、DAP、CM-2和InetlParagon中得到了實現(xiàn)一般網(wǎng)格網(wǎng)，N=n^k

結(jié)點的k維網(wǎng)格的結(jié)點度為2k，直徑為k(n-1)環(huán)網(wǎng)形網(wǎng)格網(wǎng)沿陣列每行每列都有環(huán)形連接。一個n×n二元環(huán)網(wǎng)的結(jié)點度為4，直徑為2[n/2]。環(huán)網(wǎng)是一種對稱的拓撲結(jié)構(gòu)。附加的回繞連接使直徑減至的網(wǎng)格的一半一個n×n

Illiac網(wǎng)格直徑為d=n-1，為純網(wǎng)格直徑的一半IlliacIV的8×8Illiac網(wǎng)格，其結(jié)點度為4，直徑為733網(wǎng)格形環(huán)形網(wǎng)Illiac網(wǎng)(6)網(wǎng)格和環(huán)網(wǎng)形34(7)搏動式陣列這是一類為實現(xiàn)確定算法而設(shè)計的多維流水線陣列結(jié)構(gòu)圖7.15(d)所示就是為完成矩陣相乘而專門設(shè)計的搏動式陣列。內(nèi)部結(jié)點度為6一般說來，靜態(tài)搏動式陣列可在多個方向上使數(shù)據(jù)流變成以流水線方式工作商用InteliWarp系統(tǒng)就是用搏動式結(jié)構(gòu)設(shè)計而成自從1978年Kung和Leiserson提出搏動式陣列后，它已成為廣泛研究的領(lǐng)域通過確定的互連和同步操作，搏動式陣列可與算法的通信結(jié)構(gòu)相匹配對信號/圖象處理等特殊應(yīng)用，搏動式陣列可提供更好的性能/價格比但結(jié)構(gòu)的實用性有限，而且編制程序也很難35(7)搏動式陣列36n維立方體由N=2^n個結(jié)點,分布在n維上,每維有兩個結(jié)點超立方體網(wǎng)采用交換函數(shù)，結(jié)點度為n，直徑也為n4-立方體可通過將兩個3-立方體的相應(yīng)結(jié)點互連組成(8)超立方體YXZ011000010110111101100(9)帶環(huán)立方體這種結(jié)構(gòu)是從超立方體改進而來的一個3-立方體可改成帶環(huán)3-立方體(CCC)。構(gòu)成的辦法是將3-立方體的角結(jié)點(頂角)用一個結(jié)點環(huán)來代替從一個k-立方體構(gòu)成一個有n=2^k個結(jié)點環(huán)的帶環(huán)k-立方體所用的辦法是用k個結(jié)點的環(huán)取代k維超立方體的每個頂角這樣，一個k-立方體可變成k×2^k個結(jié)點的k-CCC3-CCC的直徑為6，比原來3-立方體的直徑大一倍。一般說來，k-CCC的網(wǎng)格直徑2k。CCC的主要改進之處即在其結(jié)點度為常數(shù)3，與超立方體的維數(shù)無關(guān)一超立方體有N=2^n結(jié)點。一個有同樣N結(jié)點數(shù)的CCC一定是由低維k-立方體組成，即2^n=k×2^k，其中k<n對應(yīng)于n=6和k=4的情況，一個64結(jié)點的CCC可用4結(jié)點的環(huán)取代4-立方體的角結(jié)點組成。CCC的直徑為2k=8，比6-立方體的6要長些。但是，CCC的結(jié)點度為3，比6-立方體的結(jié)點度6要小容許一定的時延,CCC是一種構(gòu)造可擴展系統(tǒng)的較好的結(jié)構(gòu)38(9)帶環(huán)立方體YXZ01100001011011110110039(10)k元n-立方體網(wǎng)絡(luò)環(huán)形、網(wǎng)格形、環(huán)網(wǎng)形、二元n-立方體(超立方體)和W網(wǎng)絡(luò)都是k元n-立方體網(wǎng)絡(luò)系列的拓撲同構(gòu)體參數(shù)n是立方體的維數(shù)，k是基數(shù)或者說是沿每個方向的結(jié)點數(shù)(多重性)。這兩個數(shù)與網(wǎng)絡(luò)中結(jié)點數(shù)N的關(guān)系為k元n-立方體的結(jié)點可用基數(shù)為k的n位地址A=a1a2…an來表示，其中ai代表第i維結(jié)點位置。為簡單起見，所有鏈路都認為是雙向的。網(wǎng)絡(luò)中每條線代表兩個通信通道，每個方向一個40圖7.17k=4和n=3的k元n-立方體網(wǎng)絡(luò)(1)4結(jié)點串成綠色環(huán)(2)4綠色環(huán)并排成面，同一列用黃色環(huán)連接(3)4黃色面堆成體，同一行用藍色環(huán)連接41(a)傳統(tǒng)環(huán)網(wǎng)(4元2-立方體) (b)折疊連接的環(huán)網(wǎng)SHOWAVI422動態(tài)互連網(wǎng)絡(luò)動態(tài)互連網(wǎng)絡(luò)設(shè)置有源開關(guān)根據(jù)需要借助控制信號對連接通路加以重新組合，實現(xiàn)所要求的通信模式包括總線、多級互連網(wǎng)和交叉開關(guān)網(wǎng)絡(luò)43(1)總線總線系統(tǒng)是一組導(dǎo)線和插座用于處理與總線相連接的處理機、存儲器模塊和外圍設(shè)備間的數(shù)據(jù)業(yè)務(wù)總線被稱為多個功能模塊間爭用總線或時分總線總線系統(tǒng)與其它兩種動態(tài)連接網(wǎng)絡(luò)相比，其價格較低，帶寬較窄。有很多可用的工業(yè)和IEEE總線標(biāo)準(zhǔn)44(2)開關(guān)模塊一個ab開關(guān)模塊有a個輸入和b個輸出。一個二元開關(guān)則與a=b=2的22開關(guān)模塊相對應(yīng)。實際中a和b通常選為a=b=2^k，k>=1最常用的二元開關(guān)：a=b=2每個輸入可與一個或多個輸出相連，但是在輸出端必須避免發(fā)生沖突。一對一和一對多映射是容許的；但不容許有多對一映射只容許一對一映射時稱為置換連接，稱這種開關(guān)為n×n交叉開關(guān)具有直通和交換兩種功能的交換開關(guān)稱為二功能開關(guān)，或交換開關(guān)。用一位控制信號控制具有所有四種功能的交換開關(guān)稱為四功能開關(guān)，用兩位控制信號控制45直通交換上播下播模塊大小合法狀態(tài)交換連接2×2424×4256248×81677721640320n×nnnn!交換開關(guān)和合法狀態(tài)46(3)多級網(wǎng)絡(luò)能夠?qū)崿F(xiàn)結(jié)點到結(jié)點之間的任意互連是互連網(wǎng)絡(luò)的一種基本功能多級互連網(wǎng)絡(luò)采用多個相同的或不同的互連網(wǎng)絡(luò)直接連接起來屬于組合邏輯線路，一個時鐘周期就能夠?qū)崿F(xiàn)任意結(jié)點到結(jié)點之間的互連多級互連網(wǎng)絡(luò)采用的關(guān)鍵技術(shù)(1)交換開關(guān)(2)交換開關(guān)之間的拓撲連接(3)對交換開關(guān)的不同控制方式(3)多級網(wǎng)絡(luò)(3a)拓撲結(jié)構(gòu)(級間連接)前一級交換開關(guān)的輸出端與后一級交換開關(guān)的輸入端之間的連接模式稱為拓撲結(jié)構(gòu)通常采用前面介紹的互連函數(shù)實現(xiàn)拓撲結(jié)構(gòu)從結(jié)點的輸出到第一級交換開關(guān)的輸入，及從最后一級交換開關(guān)的輸出到結(jié)點的輸入也可以采用拓撲結(jié)構(gòu)連接(3b)控制方式在多級互連網(wǎng)絡(luò)中有多級交換開關(guān)，每一級又有多個交換開關(guān)(1)級控制：同一級交換開關(guān)使用同一個控制信號控制(2)單元級控制：每個交換開關(guān)分別控制(3)部分級控制：如，第i級使用i+1個控制信號控制(0<=i<=n-1)同一個多級互連網(wǎng)絡(luò)分別使用三種不同的控制方式，可以構(gòu)成三種不同的互連網(wǎng)絡(luò)圖7.20一種由a×b開關(guān)模塊和級間連接模式49采用二功能開關(guān)，總共需要開關(guān)n2^(n-1)個。采用交換函數(shù)構(gòu)成拓撲結(jié)構(gòu)，各級分別采用E0、E1、…En-1交換函數(shù)當(dāng)所有開關(guān)都直通時，實現(xiàn)恒等變換當(dāng)A、B、C、D四個開關(guān)交換，其余直通時實現(xiàn)E0

互連函數(shù)當(dāng)E、F、G、H四個開關(guān)交換，其余直通時實現(xiàn)E1

互連函數(shù)當(dāng)I、J、K、L四個開關(guān)交換，其余直通時實現(xiàn)E2

互連函數(shù)采用三種不同的控制方式，可以構(gòu)成三種不同的互連網(wǎng)絡(luò)。采用級控制可以構(gòu)成STARAN交換網(wǎng)采用部分級控制，可以構(gòu)成STARAN移數(shù)網(wǎng)采用單元控制可以構(gòu)成間接二進制n方體網(wǎng)(3c)多級立方體網(wǎng)50

B(2) B(3) S-1ABCDEFGHIJKL0123456701234567k=0k=1k=2(3c)多級立方體網(wǎng)51(4)Ω網(wǎng)絡(luò)16×16Ω網(wǎng)絡(luò)，共需4級2×2開關(guān)網(wǎng)絡(luò)左側(cè)有16個輸入，右側(cè)有16個輸出

ISC是對16個對象的均勻洗牌模式2路洗牌相當(dāng)于n個輸入端平均地分成2個子組，然后2個子組均勻地洗牌一個n輸入的Ω網(wǎng)絡(luò)需要log2n級2×2開關(guān)，每級要用n/2個開關(guān)模塊，網(wǎng)絡(luò)共需(nlog2n)/2個開關(guān)不同的開關(guān)狀態(tài)組合可實現(xiàn)各種置換、廣播或從輸入到輸出的其它連接每級的拓撲結(jié)構(gòu)相同采用單元控制能夠?qū)崿F(xiàn)任意一個輸入端到任意一個輸出端的連接不能同時實現(xiàn)多個輸入端到多個輸出端的連接通過檢查二進制目的地址編碼來控制數(shù)據(jù)路徑目的地址編碼從高位開始的第i位為0時，第i級的2×2開關(guān)的輸入端與上輸出端連接，否則輸入端與下輸出端連接52均勻洗牌置換輸入1可連接到哪幾個輸出?53

(5)基準(zhǔn)網(wǎng)絡(luò)Wu和Feng

研究過多級互連網(wǎng)絡(luò)之間的關(guān)系基準(zhǔn)網(wǎng)絡(luò)可如圖7.22(a)所示遞歸生成第1級為一個N×N模塊第2級為兩個(N/2)×(N/2)子模塊，以C0和C1表示以上構(gòu)成方法可遞歸用于子模塊直至得到2×2的N/2子模塊為止各小框和最終的子模塊構(gòu)件是2×2開關(guān)，每個有兩個合法連接狀態(tài)：兩個輸入和兩個輸出間的直送和交叉連接54每個交換開關(guān)的輸出分成上下兩組，分別連到兩個N/255

1組16結(jié)點S-12組8結(jié)點S-14組4結(jié)點S-1遞歸終點為1個2x2子模塊，即僅有兩個結(jié)點56(6)交叉開關(guān)網(wǎng)絡(luò)全交叉開關(guān)網(wǎng)絡(luò)能夠同時實現(xiàn)任意結(jié)點到結(jié)點之間的互連還能夠?qū)崿F(xiàn)廣播和多播全交叉開關(guān)網(wǎng)絡(luò)的帶寬和互連特性最好在多處理機系統(tǒng)中，處理機、存儲器和IOP之間用交叉開關(guān)網(wǎng)絡(luò)連接可看作是一個單級開關(guān)網(wǎng)絡(luò)。象電話交換機一樣，交叉點開關(guān)能在對偶(源、目的)之間形成動態(tài)連接，每個交叉點開關(guān)在對偶間提供一條專用連接通路，開關(guān)可根據(jù)程序的要求動態(tài)地設(shè)置“開”或“關(guān)”57另一種分類587.2消息傳遞機制研究各種尋徑方法，并分析它們的通信時延問題引入虛擬通道的概念，說明怎樣用虛擬通道來避免死鎖確定的和自適應(yīng)兩種尋徑算法拓撲結(jié)構(gòu)與尋徑策略有一定的關(guān)系597.2.1消息尋徑方式四種尋徑方式線路交換存儲轉(zhuǎn)發(fā)虛擬直通蟲蝕尋徑1.消息格式消息是結(jié)點間通信的邏輯單位常常由任意數(shù)目的長度固定的包所組成其長度是可變的。包是包含尋徑目的地址的基本單位。每個包需要一個序號，以便重新組裝消息?？梢詫M一步分成一些固定長度的片尋徑信息和序號形成頭片，其余的片是數(shù)據(jù)片。60消息包片DDDDDDSRR：在消息傳遞網(wǎng)絡(luò)中通信的信息單位：消息、包和片的格式R：導(dǎo)徑信息S：序號D：數(shù)據(jù)片包消息包片據(jù)片頭片尾片……順序號數(shù)bbbbbbbb61在采用存儲轉(zhuǎn)發(fā)尋徑方式的多計算機系統(tǒng)中，包是信息傳送的最小單位在采用蟲蝕尋徑網(wǎng)絡(luò)的多計算機中，包可以進一步分成片。片的長度往往受網(wǎng)絡(luò)大小的影響256個結(jié)點的網(wǎng)絡(luò)需要片長為8位包的長度取決于尋徑方式和網(wǎng)絡(luò)的實現(xiàn)方法典型的包的長度為64～512位。序號可能占用1～2個片，取決于消息的長度包和片的大小還與通道頻寬、尋徑器設(shè)計以及網(wǎng)絡(luò)流量密度等有關(guān)622、四種尋徑方式兩大類線路交換包交換(存儲轉(zhuǎn)發(fā)、虛擬直通和蟲蝕尋徑)(1)線路交換(circuitswitch)先建立一條從源結(jié)點到目的結(jié)點的物理通路，然后再傳遞消息傳輸時延公式T=(Lt/B)*D+L/B其中：Lt為建立路徑所需小信息包的長度L為信息包的長度D為經(jīng)過的結(jié)點數(shù)B為帶寬優(yōu)點：實際通信時間較短，使用緩沖區(qū)少缺點：建立源結(jié)點到目的結(jié)點的物理通路開銷很大，占用物理通路時間長63(2)存儲轉(zhuǎn)發(fā)(storeandforward)每個結(jié)點有一個包緩沖區(qū)，包從源結(jié)點經(jīng)過中間結(jié)點到達目的結(jié)點存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)的時延與源和目的地之間的距離成正比。傳輸時延公式：T=(L/B)*D+L/B=(D+1)*L/B優(yōu)點：占用物理通路的時間比較短缺點：包緩沖區(qū)大，時延大(與結(jié)點距離成正比)64(3)虛擬直通(virtualcutthrough)當(dāng)接收到用作尋徑的消息頭部時，即開始路由選擇。通信時延公式：T=(Lh/B)*D+L/B=(Lh*D+L)/B其中：Lh是消息的尋徑頭部的長度，一般有，L>>Lh×D；通信時延可以近似為：T=L/B與結(jié)點數(shù)無關(guān)當(dāng)出現(xiàn)尋徑阻塞時，只能將整個消息存儲在尋徑結(jié)點中主要優(yōu)點：通信延遲與結(jié)點數(shù)無關(guān)主要缺點：每個結(jié)點需要有足夠大的緩沖區(qū)來存儲最大信息包在最壞的情況下與存儲轉(zhuǎn)發(fā)方式的通信時延是一樣的，經(jīng)過的每個結(jié)點都發(fā)生阻塞，都需緩沖65(4)蟲蝕尋徑(wormhole)把包分成更小的片。每個結(jié)點的尋徑器中有片緩沖區(qū)用頭片直接開辟一條從輸入結(jié)點到輸出結(jié)點的路徑。每個消息中的片以流水方式在網(wǎng)絡(luò)中向前“蠕動”當(dāng)消息的頭片到達一個結(jié)點A的尋徑器后，尋徑器根據(jù)頭片的尋徑消息立即做出路由選擇如所選擇的通道空閑且所選擇的結(jié)點B的片緩沖區(qū)可用，那么這個頭片就不必等待，直接通過結(jié)點A傳向下一個結(jié)點B隨后的其它數(shù)據(jù)片跟著相應(yīng)地向前“蠕動”一步當(dāng)消息的尾片向前“蠕動”一步之后，它剛才所占有的結(jié)點就被放棄如果所選擇的通道或的結(jié)點的片緩沖區(qū)不可用時，頭片必須在該結(jié)點的片緩沖區(qū)中等待，其它數(shù)據(jù)片也在原來的結(jié)點上等待通信時延用公式：T=Tf×D+L/B=(Lf/B)×D+L/B=(Lf×D+L)/B其中：Lf是片的長度，Tf是片經(jīng)過一個結(jié)點所需時間。一般有L>>Lf×D，可近似為T=L/B，通信時延與結(jié)點數(shù)無關(guān)66蟲蝕尋徑的優(yōu)點每個結(jié)點的緩沖區(qū)較小，易于VLSI實現(xiàn)較低的網(wǎng)絡(luò)傳輸時延所有的片以流水方式向前傳輸，采用了時間并行性存儲轉(zhuǎn)發(fā)方式的消息包整個地從一個結(jié)點“跳”到另一個結(jié)點，通道的使用是串行的，所以它的傳輸時延基本上正比于消息在網(wǎng)絡(luò)中傳輸?shù)木嚯x蟲蝕尋徑方式的網(wǎng)絡(luò)傳輸時延正比于消息包的長度，傳輸距離對它的影響很小通道共享性好，利用率高對通道的預(yù)約和釋放是結(jié)合在一起的一個完整的過程有一段新的通道后將立即放棄用過的一段舊通道易于實現(xiàn)選播和廣播通信方式允許尋徑器復(fù)制消息包的片并把它們從其多個輸出通道輸出67蟲蝕尋徑的缺點：當(dāng)消息的一個片被阻塞時，整個消息都被阻塞，占用了結(jié)點資源需要采用虛擬通道的方式來避免由此引起的一連串的阻塞蟲蝕尋徑方式也可以分為無緩沖和有緩沖兩類，區(qū)別在于緩沖的大小緩沖大有利于性能的提高，但會增加結(jié)點的復(fù)雜度IBMSP2采用的尋徑方式就是帶緩沖的蟲蝕尋徑方式，它采用共享的存儲區(qū)來對輸入/輸出消息進行緩沖68圖7.25幾種尋徑方式的時空圖(a)線路開關(guān)尋徑(1)N1-->N4(2)通過識別消息頭部，N1接到N2，N2接到N3，N3接到N4(3)N1發(fā)送，以極小的延遲通過中間結(jié)點N2，N3到達N469(b)存儲轉(zhuǎn)發(fā)尋徑(1)N1-->N4(2)N1發(fā)送到N2存儲(3)N2轉(zhuǎn)發(fā)到N3存儲(4)N3轉(zhuǎn)發(fā)到N470(c)蟲蝕尋徑(1)N1-->N4(2)頭片由N1尋徑至N2，N1發(fā)送頭片到N2存儲(3)頭片由N2尋徑至N3，N2發(fā)送頭片到N3存儲

N1發(fā)送1號片到N2存儲(4)頭片由N3尋徑至N4，N3發(fā)送頭片到N4

N2發(fā)送1號片到N3存儲

N1發(fā)送2號片到N2存儲N1,N2,N3類似流水線的三段，頭片,1號片,2號片類似流水線的三條指令

--------流水方式，蠕動，一個包傳送完成前，蠕動路徑不能和其他包的蠕動路徑交叉頭片逐個結(jié)點尋徑，尾片逐個結(jié)點放棄蠕動路徑717.2.2死鎖和虛擬通道1虛擬通道虛擬通道是兩個結(jié)點間的邏輯鏈由源結(jié)點的片緩沖區(qū)、結(jié)點間的物理通道以及接收結(jié)點的片緩沖區(qū)組成物理通道由所有的虛擬通道分時共享如圖四條虛擬通道分時共享一條物理通道72物理通道四條虛擬通道以片傳遞為基礎(chǔ)分時地共享一條物理通道732死鎖的產(chǎn)生和避免由于緩沖區(qū)或通道上的循環(huán)等待會引起死鎖采用存儲轉(zhuǎn)發(fā)尋徑的四個結(jié)點間出現(xiàn)緩沖區(qū)死鎖DDDDD包緩沖區(qū)CCCCC包緩沖區(qū)BBBBB包緩沖區(qū)AAAAA包緩沖區(qū)74結(jié)點A結(jié)點D結(jié)點B結(jié)點Cm3m2m1m4尋徑器C尋徑器B片緩沖區(qū)消息1消息2消息3尋徑器A消息4尋徑器D采用蟲蝕尋徑的四個結(jié)點之間出現(xiàn)通道死鎖75如何避免死鎖緩沖區(qū)或通道上的循環(huán)等待會引起死鎖利用虛擬通道方法可以減少死鎖。增加兩條虛擬通道V3和V4利用虛擬通道避免死鎖虛擬通道可以用單向通道或者雙向通道實現(xiàn)將兩條單向通道組合在一起可以構(gòu)成一條雙向通道虛擬通道可能會使每個請求可用的有效通道頻寬降低確定虛擬通道數(shù)目，需要對網(wǎng)絡(luò)吞吐量和通信時延折衰考慮實現(xiàn)數(shù)目很大的虛擬通道需要用高速的多路選擇開關(guān)76(b)包含循環(huán)的通道相關(guān)圖 (d)利用虛擬通道后修改的通道相關(guān)圖777.2.3流控制策略1包沖突的解決在兩個相鄰結(jié)點之間傳送片時，必須具備三個條件(1)源緩沖區(qū)已存有該片(2)通道已分配好(3)接收緩沖區(qū)準(zhǔn)備接收該片接收緩沖區(qū)或輸出通道沖突的仲裁(1)把后一個包暫時存放在緩沖區(qū)(2)阻塞后一個包(3)揚棄后一個包(4)繞道78圖7.31解決兩個包請求同一條輸出通道發(fā)生沖突時的流控制方法(a)用緩沖實現(xiàn)虛擬直徑尋徑 (b)阻塞流控制(c)揚棄并重發(fā) (d)阻塞后繞道792確定尋徑和自適應(yīng)尋徑如何找出一條從源結(jié)點到目的結(jié)點的路徑來傳送消息？尋徑可以分為確定和自適應(yīng)兩類采用確定尋徑時，通信路徑完全由源和目的地址確定即尋找的路徑是預(yù)先唯一確定的，與網(wǎng)絡(luò)的狀況無關(guān)自適應(yīng)尋徑與網(wǎng)絡(luò)的狀況有關(guān)，可能會有幾條路徑兩種尋徑都需要無死鎖算法80(1)確定尋徑維序?qū)剿惴ò凑斩嗑S網(wǎng)絡(luò)維序的特定順序來選擇后繼通道在二維網(wǎng)格網(wǎng)絡(luò)中稱為X-Y尋徑首先沿著X維方向確定路徑，然后沿著Y維方向選擇路徑在超立體(或n立方體)網(wǎng)絡(luò)中，采用最初由Sullivan和Bashkow于1977年提出的稱為E立方體尋徑(E-cuberouting)方法。逐維改變(a)二維網(wǎng)格網(wǎng)絡(luò)的X-Y尋徑假定從任意源結(jié)點s=(x1，y1)到任意目的結(jié)點d=(x2，y2)尋徑從s開始首先沿X方向前進一直到d所在的第x2列為止然后沿Y方向前進直到y(tǒng)2,即d總是首先沿X維方向?qū)?，然后再沿Y維方向?qū)剑瑢骄筒粫霈F(xiàn)死鎖或循環(huán)等待81與東-北、東-南、西-北及西-南的路徑方向相對應(yīng)，X-Y尋徑共有4種模式(2,1;7,6)東-北(0,7;4,2)東-南...82按照維序，可以很容易地將X-Y尋徑擴充到n維網(wǎng)絡(luò)以三維網(wǎng)格為例，可以類似地說明X-Y-Z尋徑方法X-Y方式不會產(chǎn)生死鎖尋徑，可用于存儲轉(zhuǎn)發(fā)或蟲蝕尋徑網(wǎng)絡(luò)，在源和目的結(jié)點之間形成一條距離最短的路徑對于環(huán)網(wǎng)網(wǎng)絡(luò)，采用維序?qū)椒椒ú荒艿玫阶疃搪窂綖榱藴p少網(wǎng)絡(luò)流量或其它原因，不會產(chǎn)生死鎖的非最短尋徑算法有時會使包通過的路徑較長83(b)超立方體網(wǎng)絡(luò)的E立方體尋徑假設(shè)有一N=2n個結(jié)點的n方體。每個結(jié)點的二進制編碼為b=bn-1bn-2…b1b0。這樣，源結(jié)點為s=sn-1sn-2…s1s0，目的結(jié)點d=dn-1bn-2…d1d0現(xiàn)在要確定一條從s到d的步數(shù)最小的路徑將n維表示成i=1，2，…，n，其中第i維對應(yīng)于結(jié)點地址中的第i-1位。設(shè)u=un-1un-2…u1u0是路徑中的任一結(jié)點路徑可以根據(jù)以下方法唯一地確定①計算方向位ri=si-1⊕di-1，其中i=1，2，...，n。使i=1，v=s②如果ri=1，從當(dāng)前結(jié)點u尋徑到下一結(jié)點。如果ri=0，則跳過這一步③i←i+1。如果i≤n，則轉(zhuǎn)第②步，否則退出尋徑是按照從維1到維4的順序進行的如果s和d的第i位相同，則沿維i方向不需要尋徑否則從當(dāng)前結(jié)點沿著這一維方向走到其它結(jié)點重復(fù)這一過程直到到達目的結(jié)點E立方體尋徑也不會產(chǎn)生死鎖尋徑，也可用于存儲轉(zhuǎn)發(fā)和蟲蝕網(wǎng)絡(luò)，在源和結(jié)點之間形成一條距離最短的路徑84圖中，n=4，s=0110，d=1101r=r4r3r2r1=s⊕d=0110⊕1101=1011i=1,r1=1，v=s=0110尋徑到v=v⊕2^0=0110⊕1=0111i=2,r2=1，v=0111尋徑到v=v⊕2^1=0111⊕10=0101i=3,r3=0，跳過維i=3這一步i=4,r4=1，v=0101尋徑到v=v⊕2^3=0101⊕1000=1101=d85(2)自適應(yīng)尋徑采用自適應(yīng)尋徑要特別注意避免死鎖虛擬通道的概念使實現(xiàn)自適應(yīng)尋徑更經(jīng)濟和更靈活在網(wǎng)格連接網(wǎng)絡(luò)中，同一維的所有連接都使用虛擬通道圖7.34是一個用X-Y尋徑的網(wǎng)格網(wǎng)絡(luò)，在Y維上用了2對虛擬通道圖7.34(c)中的虛擬網(wǎng)絡(luò)可以用來避免消息在向西傳輸出現(xiàn)的死鎖，因為所有向東的X通道都沒有使用圖7.34(d)中的虛擬網(wǎng)絡(luò)使用另一組Y方向虛擬通道來支持只向東的傳輸不同的時刻使用兩個虛擬網(wǎng)絡(luò)，這樣死鎖就可以自動避免P424L3，X改成Y86圖7.34利用虛擬通道避免死鎖的自適應(yīng)X-Y尋徑

(a)沒有虛擬通道的原形網(wǎng)絡(luò) (b)Y維方向有兩對虛擬通道

(c)向西方向傳輸信息 (d)向東方向傳輸信息c,d有循環(huán)等待嗎87圖7.35是在X維和Y維方向各有兩條虛擬通道的網(wǎng)格形網(wǎng)絡(luò)這些虛擬通道可以用來生成4個虛擬網(wǎng)絡(luò)西-北方向通信應(yīng)該使用圖7.35(b)所示的虛擬網(wǎng)絡(luò)類似地，其它方向的通信可以構(gòu)造另外3個虛擬網(wǎng)絡(luò)注意，任何一個虛擬網(wǎng)絡(luò)都不會出現(xiàn)環(huán)路在這些網(wǎng)絡(luò)上實現(xiàn)X-Y尋徑方法時，完全可以避免死鎖如果相鄰結(jié)點之間的兩對通道都是物理通道，那么4個虛擬網(wǎng)絡(luò)中任何兩個都可以同時使用而不會產(chǎn)生沖突如果相鄰結(jié)點之間雙虛擬通道只能共享一對物理通道只有(b)和(e)或(c)和(d)可以同時使用其它組合如(b)和(c)，或(b)和(d)，或(c)和(e)，或(d)和(e)都不能同時存在，因為缺少通道網(wǎng)絡(luò)的通道數(shù)增加，尋徑的自適應(yīng)性也將增加成本的增加將很可觀，要避免使用過多的資源P425L3，b和c改成b和e88圖7.35雙通道網(wǎng)格網(wǎng)絡(luò)可實現(xiàn)4個虛擬網(wǎng)絡(luò)(a)雙通道的3×3網(wǎng)絡(luò) (b)西-北子網(wǎng) (c)東-北子網(wǎng)

(d)西-南子網(wǎng) (e)東-南子網(wǎng)b,c,d,e有循環(huán)等待嗎897.2.4選播與廣播尋徑算法四種通信模式(1)單播(unicast),一對一傳送(2)選播(multicast),一個源結(jié)點發(fā)送同一個消息到多個目的結(jié)點(3)廣播(broadcast),一個源結(jié)點發(fā)送同一個消息到全部結(jié)點(4)會議(conference),對應(yīng)于多到多的通信情況90廣播與選播算法廣播是將一個結(jié)點的數(shù)據(jù)復(fù)制到全部N個結(jié)點；選播是將一個結(jié)點的數(shù)據(jù)復(fù)制到多個(N'個)結(jié)點，1≤N'≤N研究廣播與選播算法的目的是盡量利用互連網(wǎng)的并行傳輸能力，尋找花費時間最少或者動用信道次數(shù)(又稱"流量"或"通道數(shù)")最少的方案這里所說的并行傳輸，指多個結(jié)點向同一方向的相鄰結(jié)點發(fā)送自己的數(shù)據(jù)副本。向不同方向進行的發(fā)送不能同時進行(具有這種能力的互連網(wǎng)不屬于現(xiàn)在的討論范圍)對不同的網(wǎng)絡(luò)，適用的廣播與選播算法也不同91選播選播算法的設(shè)計目標(biāo)有3種：時間最少、流量最少、在時間最少的多個方案中選取流量最少方案選播時間最少算法是通過單播時間最少算法裁剪而成(教材P426圖7.36(a)→(b))選播流量最少算法是最小成本生成樹算法，具體操作順序既可以是先短邊后長邊“長樹”，也可以是先長邊后短邊“砍樹”(教材P426圖7.36(c))實現(xiàn)第3種目標(biāo)的一種重要算法是貪婪算法(教材P426圖7.36(b))不論對何種網(wǎng)絡(luò)，貪婪算法總是重復(fù)使用一個固定的操作規(guī)則從當(dāng)前擁有數(shù)據(jù)的結(jié)點出發(fā)，向需要數(shù)據(jù)的結(jié)點數(shù)最多的方向并行傳送一步如此循環(huán)，直至傳遍所有需要數(shù)據(jù)的結(jié)點如果最后發(fā)現(xiàn)某個通道(即一次數(shù)據(jù)發(fā)送操作)不在通往給定目標(biāo)結(jié)點的路徑上，則應(yīng)將其刪去92擴散向最近的結(jié)點的方向移動1步5次點對點,1個流量為相鄰結(jié)點一次傳輸向可達結(jié)點數(shù)最多的方向移動1步123444412364593圖7.37貪婪算法4立方體廣播樹和選播樹(a)一個根結(jié)點為0000的4立方體。超立方體廣播樹的流量最小。(b)是一棵貪婪選播樹，可從結(jié)點0101發(fā)送包到7個目的結(jié)點94貪婪選播算法的基本思想是向那些可達到最多剩余目的結(jié)點的維方向發(fā)送包圖7.37(a)是一個根結(jié)點為0000的4立方體。超立方體廣播樹的流量最小圖7.37(b)是一棵貪婪選播樹，可從結(jié)點0101發(fā)送包到7個目的結(jié)點從源結(jié)點S=0101開始，由維2方向可以到達2個目的結(jié)點，由維4方向可以達到5個目的結(jié)點。第1層所用的通道是0101→0111和0101→1101從結(jié)點1101，由維2方向可以到達3個目的結(jié)點，由維1方向可以到達4個目的結(jié)點。第2層所用的通道是1101→1111，1101→1100和0111→0110同理，第3層所用的通道是1111→1110，1111→1011，1100→1000和0110→0010第4層所用的通道是1110→101095在擴充選播樹時首先應(yīng)該比較所有各維方向的可達性(reachability)然后選擇某些維使剩余目的結(jié)點的集合最小如果兩維之間有連線，那么選擇其中任何一維都可以。因此，所生成的樹不是唯一的已經(jīng)證明貪婪選播算法所需的通道數(shù)與多次單播或廣播樹相比要少在蟲蝕尋徑網(wǎng)絡(luò)中，實現(xiàn)選播操作時，每個結(jié)點的尋徑器應(yīng)有復(fù)制片緩沖區(qū)中數(shù)據(jù)的能力為了與選播樹或廣播樹的增長同步，樹中同一層的所有輸出通道必須在傳輸向前推進一層之前處于就緒狀態(tài)，否則中間結(jié)點需要增加緩沖區(qū)96(1)單級網(wǎng)格網(wǎng)(Mash網(wǎng))貪婪算法教材P426圖7.36(a)指出總共有1個源結(jié)點S和5個目的結(jié)點圖(b)指出從S出發(fā)，首先應(yīng)向右鄰結(jié)點發(fā)送數(shù)據(jù)，因為S的左方只有1個目的結(jié)點、上方有3個目的結(jié)點、右方有４個目的結(jié)點第二步從這2個擁有數(shù)據(jù)的結(jié)點出發(fā)，可以再向右發(fā)送(有3個目的結(jié)點)，也可以改向上發(fā)送(也有3個目的結(jié)點)，……只要每步遵守貪婪算法的規(guī)則，最后形成的不同路徑樹的時間和流量都是相同的97教材P426圖7.37(a)指出廣播算法的時間是4，流量是15。Cube0

～Cuben-1的使用順序?qū)V播算法的時間和流量沒有影響，但對小圖(b)的選播算法的時間和流量有影響先看一個簡單的例子(下圖)：已知N=4，維數(shù)n=2，源結(jié)點是0，目的結(jié)點是1和3

源結(jié)點編號的二進制形式00在bit0位與兩個目的結(jié)點的二進制形式01、11都不相同，而在bit1位僅與一個目的結(jié)點的二進制形式不同，所以應(yīng)該先傳bit0方向、再傳bit1方向，如右圖(a)所示，這時流量=2；如果先傳bit1方向、再傳bit0方向，如右圖(b)所示，則流量=3(2)單級立方體網(wǎng)絡(luò)貪婪算法98教材P426圖7.37(b)的例子。源結(jié)點編號的二進制形式0101在Cube0

～Cube3位分別與5、5、4、5個目的結(jié)點的二進制形式不同，所以Cube2方向應(yīng)該最后發(fā)送，其它3個方向的發(fā)送先后順序則沒有限制。教材P427采用了Cube3、Cube1、Cube0、Cube2的發(fā)送順序，如下圖所示，時間=4，總流量=10997.3互連網(wǎng)絡(luò)實例著重研究下面幾種多處理機的互連網(wǎng)絡(luò)總線結(jié)構(gòu)、環(huán)形互連、交叉開關(guān)、混洗交換互連等處理機系統(tǒng)采用哪種互連結(jié)構(gòu)主要取決于系統(tǒng)的最大通信量反過來，系統(tǒng)的最大通信量受到互連結(jié)構(gòu)的限制7.3.1總線互連目前，大部分處理機內(nèi)部采用總線結(jié)構(gòu)CPU與存儲器之間有系統(tǒng)總線存儲器與輸入輸出設(shè)備之間有I/O總線總線與總線之間通過總線橋連接總線的主要優(yōu)點是結(jié)構(gòu)簡單，能夠很方便實現(xiàn)廣播通信總線的主要缺點是帶寬低，發(fā)生總線沖突的可能性大總線沖突的解決辦法有(1)設(shè)置靜態(tài)優(yōu)先級(2)在同步方式中采用時間片(3)采用動態(tài)優(yōu)先級(如LRU法等)(4)先來先服務(wù)101總線結(jié)構(gòu)的多處理機102為了提高總線的通信帶寬，有如下方法(1)采用多總線結(jié)構(gòu)(2)層次總線結(jié)構(gòu)(3)多維總線結(jié)構(gòu)多總線西門子公司的SMS系統(tǒng)(StracturedMultiprocessorSystem)通過8條總線連接128個處理機層次總線卡內(nèi)基梅隆大學(xué)的Cm*多處理機系統(tǒng)采用層次總線結(jié)構(gòu)三級總線：群總線、Map總線、處理機總線每群14臺處理機主機P1P2P16P17P18P32P113P114P128………………………………總線驅(qū)動器SMS多總線結(jié)構(gòu)卡內(nèi)基梅隆大學(xué)的Cm*層次總線結(jié)構(gòu)CmCmCm…KmCmBCm…KmCmCmCm…Km…MIOP群間總線7.3.2環(huán)形互聯(lián)一種互連方法，它既能具有總線型互連的簡單性，又可以克服總線所固有的缺點信息的傳送過程是發(fā)送進程把信息放到環(huán)上，通過環(huán)形網(wǎng)絡(luò)不斷向下一臺處理機傳播，直到此信息回到發(fā)送者為止106IEEE802.5令牌環(huán)(TokenRing)IEEE802.5令牌環(huán)(TokenRing)標(biāo)準(zhǔn)是把環(huán)形看作邏輯總線的協(xié)議發(fā)送信息的處理機擁有一個唯一的令牌，在同一時刻只有一臺處理機持有這個令牌當(dāng)發(fā)送者發(fā)送信息時，這個環(huán)形網(wǎng)絡(luò)的作用如同總線一樣，其它處理機都處于接收信息的狀態(tài)信息傳送結(jié)束時，發(fā)送者播送一個令牌，這個令牌是在普通信息中不會出現(xiàn)的特定信號。每臺處理機依次看到令牌如果某臺處理機等待發(fā)送信息，那么它便接收這個令牌而不再傳遞給下一臺處理機，這時這臺處理機就可以通過環(huán)形網(wǎng)絡(luò)發(fā)送信息了假如沒有想發(fā)送信息的處理機，那么令牌就將在環(huán)形網(wǎng)絡(luò)上不斷循環(huán)，直到某臺處理機需要發(fā)送信息為止107令牌環(huán)的優(yōu)點是點點連接，而不是總線連接，其物理參數(shù)更容易控制令牌環(huán)形互連非常適于高帶寬的光纖通信。N較小的總線互連系統(tǒng)很難采用光纖通信，N較大的系統(tǒng)也還未實現(xiàn)令牌環(huán)形互連的一個主要缺點是每個總線接口都有延遲通常是1位的延遲當(dāng)互連處理機臺數(shù)增加時，在環(huán)中的信息傳輸延遲將正比例地增加但是當(dāng)系統(tǒng)負載很重時，系統(tǒng)的帶寬卻不會像總線互連系統(tǒng)那樣下降1087.3.3交叉開關(guān)互連交叉開關(guān)網(wǎng)絡(luò)，它把N臺處理機和N個存儲器連接起來圖中處理機臺數(shù)與存儲器個數(shù)相等，一般情況是存儲器數(shù)目等于或是處理機數(shù)目的幾倍網(wǎng)絡(luò)中每個交叉點是一個允許任何一臺處理器與任何一個存儲器連接的開關(guān)系統(tǒng)允許N個存取操作并行執(zhí)行任意兩個存取操作不能涉及同一臺處理機或同一個存儲器如果兩個或兩個以上存取操作同時要訪問某個存儲器，那么爭用現(xiàn)象就發(fā)生了如處理機P1和P2同時要訪問存儲器M1減少爭用，在系統(tǒng)結(jié)構(gòu)方面大有文章可做如果爭用是由于多臺處理機同時要訪問同一存儲模塊中不同單元的數(shù)據(jù)而引起的，一種解決爭用的方法是盡量使這些數(shù)據(jù)平均地分配到多個不同的存儲模塊中，而不要把它們集中在一個存儲模塊中把一個數(shù)據(jù)塊中數(shù)據(jù)依次分配到相繼的存儲模塊中同樣，共享程序代碼也應(yīng)該這樣分配這樣，當(dāng)兩臺或兩臺以上的處理機同時訪問共享程序代碼或數(shù)據(jù)時，爭用只使其中一臺處理機延遲一個周期只要兩臺處理機順序地不斷地訪問，兩者不會再發(fā)生沖突這種尋址技術(shù)也可用于流水線多處理機中，使各臺處理機能彼此步調(diào)一致地存取向量數(shù)據(jù)1107.3.4混洗交換互連和合并開關(guān)混洗交換網(wǎng)絡(luò)能提供一種重要的功能，稱為合并開關(guān)它使某些操作在網(wǎng)絡(luò)一級并行地執(zhí)行，從而減少爭用現(xiàn)象否則這些需要訪問存儲器的操作只能串行地執(zhí)行對那些需要互斥地訪問共享變量的進程來說，這種方法很有潛力互斥地訪問共享變量限制了大部分多處理機系統(tǒng)的性能當(dāng)出現(xiàn)多個進程要存取某個共享變量時，無論系統(tǒng)再增加多少臺處理機也不可能再提高其速度1118臺處理器和8個存儲器通過混洗交換互連網(wǎng)絡(luò)連接1127.3.5Omega網(wǎng)絡(luò)采用了全混洗函數(shù)和交換函數(shù)，又稱為混洗交換網(wǎng)絡(luò)Omega網(wǎng)已經(jīng)用于伊利諾依大學(xué)的Cedar多處理機、IBM的RP3系統(tǒng)和紐約大學(xué)Ultracomputer中N個輸入的Omega網(wǎng)絡(luò)有l(wèi)og2N級每級有N/2個2×2的四功能交換開關(guān)每級的拓撲結(jié)構(gòu)相同采用單元控制(每一級的控制信號均相同)能夠?qū)崿F(xiàn)任意一個輸入端到任意一個輸出端的連接不能同時實現(xiàn)多個輸入端到多個輸出端的連接通過檢查二進制目的地址編碼來控制數(shù)據(jù)路徑目的地址編碼從高位開始的第i位為0時，第i級的2×2開關(guān)的輸入端與上輸出端連接，否則輸入端與下輸出端連接1138個輸入端的Omega網(wǎng)絡(luò)2路洗牌相當(dāng)于8個輸入端平均地分成2個子組，然后2個子組均勻地洗牌同時實現(xiàn)06和47有沖突沖突的還有：30和51，30和73，50和71等0123010101114開關(guān)設(shè)置從輸入端001到輸出端011的路徑。它使用了開關(guān)A、B、C目的地址編碼011的最高位“0”，輸入端001與開關(guān)A的上輸出端(編號為2)連接,開關(guān)A設(shè)置成直送狀態(tài)011的次高位是“1”，輸入端4和下輸出端連接，開關(guān)B設(shè)置成交換狀態(tài)011的最低位是“1”，輸入端4和下輸出端連接，開關(guān)C設(shè)置成直送狀態(tài)輸入端101到輸出端101的路徑？115116如果采用級控制，是STARAN交換網(wǎng)的逆網(wǎng)如果采用部分級控制，是STARAN移數(shù)網(wǎng)的逆網(wǎng)因此，Omega網(wǎng)的許多性質(zhì)與多級立方體網(wǎng)相反，如發(fā)生沖突的情況Omega網(wǎng)屬于多級互連網(wǎng)當(dāng)有N個輸入端時，共有N^(N/2)個變換要同時實現(xiàn)任意一個輸入端到任意一個輸出端的連接，總共需要N!個變換8個輸入端的Omega網(wǎng)絡(luò)實際上只能實現(xiàn)全部變換的10%(8