計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)第七章互連網(wǎng)絡(luò)

1、第7章 互連網(wǎng)絡(luò),7.1 互連網(wǎng)絡(luò)的基本概念7.2 互連網(wǎng)絡(luò)的種類7.3 消息傳遞機(jī)制7.4 互連網(wǎng)絡(luò)實(shí)例,7.1 互連網(wǎng)絡(luò)的基本概念,7.1.1 互連網(wǎng)絡(luò)的作用7.1.2 互連網(wǎng)絡(luò)的特性7.1.3 互連網(wǎng)絡(luò)的性能參數(shù)7.1.4 互連網(wǎng)絡(luò)的表示方法7.1.5 互連函數(shù),7.1.1 互連網(wǎng)絡(luò)的作用,用來實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)內(nèi)部多個(gè)處理機(jī)或多個(gè)功能部件之間的相互連接?；ミB網(wǎng)絡(luò)已成為并行處理系統(tǒng)的核心組成部分?；ミB網(wǎng)絡(luò)對(duì)

2、整個(gè)計(jì)算機(jī)系統(tǒng)的性能價(jià)格比有著決定性的影響。一個(gè)例子：具有本地存儲(chǔ)器、私有高速緩存、共享存儲(chǔ)器和共享外圍設(shè)備的一般處理機(jī)系統(tǒng)的互連結(jié)構(gòu),磁盤,SM1,,SM2,SMm,PMN,……,Cn,Pn,LM,C1,P1,LM,PCN,,,,,,,,,,,,,,……,……,……,……,PION,,,磁帶,,打印機(jī),,終端,,網(wǎng)絡(luò),,…,(共享存儲(chǔ)器),(共享I/O與外設(shè)),7.1.2 互連網(wǎng)絡(luò)的特性,互連網(wǎng)絡(luò)通常是用有向邊或無向邊連接有限個(gè)結(jié)點(diǎn)

3、的組成。互連網(wǎng)絡(luò)的主要特性有：(1)網(wǎng)絡(luò)規(guī)模：網(wǎng)絡(luò)中結(jié)點(diǎn)的個(gè)數(shù)(2)結(jié)點(diǎn)度：與結(jié)點(diǎn)相連接的邊數(shù)稱為結(jié)點(diǎn)度 進(jìn)入結(jié)點(diǎn)的邊數(shù)叫入度 從結(jié)點(diǎn)出來的邊數(shù)則叫出度(3)距離：兩個(gè)結(jié)點(diǎn)之間相連的最少邊數(shù)(4)網(wǎng)絡(luò)直徑：網(wǎng)絡(luò)中任意兩個(gè)結(jié)點(diǎn)間距離的最大值。用結(jié)點(diǎn)間的連接邊數(shù)表示,7.1.3 互連網(wǎng)絡(luò)的性能參數(shù),發(fā)送方的步驟如下：(1) 用戶程序把要發(fā)送的數(shù)據(jù)拷貝到系統(tǒng)緩沖區(qū)。(2) 緩沖區(qū)中的數(shù)據(jù)打包并發(fā)送到網(wǎng)絡(luò)接口部件。

4、(3) 網(wǎng)絡(luò)接口硬件開始發(fā)送消息。數(shù)據(jù)包的接收步驟如下：(1) 把數(shù)據(jù)包從網(wǎng)絡(luò)接口部件拷貝到系統(tǒng)緩沖區(qū)。(2) 檢查收到的數(shù)據(jù)包，如果正確，發(fā)回答信號(hào)。(3) 把接收到的數(shù)據(jù)拷貝到用戶地址空間。發(fā)送方接收到回答信號(hào)后釋放系統(tǒng)緩沖區(qū),互連網(wǎng)絡(luò)的主要性能參數(shù)：(1)頻帶寬度(Bandwidth)：傳輸信息的最大速率(2)傳輸時(shí)間(Transmission time)：等于消息長度除以頻寬。(3)飛行時(shí)間(Time of f

5、light)：第一位信息到達(dá)接收方所花費(fèi)的時(shí)間。(4)傳輸時(shí)延(Transport latency)：等于飛行時(shí)間與傳輸時(shí)間之和。(5)發(fā)送方開銷(Sender overhead)：處理器把消息放到互連網(wǎng)絡(luò)的時(shí)間。(6)接收方開銷(Receiver overhead)：處理器把消息從網(wǎng)絡(luò)取出來的時(shí)間。,一個(gè)消息的總時(shí)延可以用下面公式表示： 總時(shí)延＝發(fā)送方開銷＋飛行時(shí)間＋ 消息長度/頻寬＋接收方開銷例7.1：假設(shè)一個(gè)網(wǎng)絡(luò)的頻

6、寬為10Mb/S，發(fā)送方開銷為230us，接收方開銷分別為270us。如果兩臺(tái)機(jī)器相距100米，現(xiàn)在要發(fā)送一個(gè)1000字節(jié)的消息給另一臺(tái)機(jī)器，試計(jì)算總時(shí)延。如果兩臺(tái)機(jī)器相距1000公里，那么總時(shí)延為多大？,解：光的速度為299792.5KM/S，信號(hào)在導(dǎo)體中傳遞速度大約是光速的50％。 相距100米時(shí)總時(shí)延為： 相距1000公里時(shí)的總時(shí)延為：,7.1.4 互連網(wǎng)絡(luò)的表示方法,為了在輸入結(jié)點(diǎn)與輸出結(jié)點(diǎn)之間建立

7、對(duì)應(yīng)關(guān)系，互連網(wǎng)絡(luò)有三種表示方法：(1)互連函數(shù)表示法： 如：f(xn-1…x1x0) = x0xn-2…x1xn-1(2)圖形表示法(3)輸入輸出對(duì)應(yīng)表示法,互連網(wǎng)絡(luò),,…,0,,0,,1,,1,…,,n-1,,n-1,輸入: 0 1 2 3 4 5 6 7輸出: 1 0 3 2 5 4 7 6,7.1.5 互連函數(shù),互連函數(shù)也稱為互連置換或互連排列等。1. 交換函數(shù)（Exchange） 當(dāng)n＝3時(shí)，有3種函數(shù)

8、，每種能表示8個(gè)結(jié)點(diǎn)之間的連接關(guān)系。由于交換函數(shù)主要用于超立方體互連網(wǎng)中，因此也稱為超立方體函數(shù)，用Cube表示，如：Cube0、Cube1、Cube2等。,2.全混洗函數(shù)（Perfect shuffle）函數(shù)關(guān)系：把二進(jìn)制結(jié)點(diǎn)號(hào)循環(huán)左移一位子混洗(subshuffle)S(k) ,最低k位循環(huán)左移一位 超混洗(supershuffle)S(k),最高k位循環(huán)左移一位顯然成立：逆混洗函數(shù)：,3. 蝶式函數(shù)（But

9、terfly）蝶式函數(shù)的名稱來自于FFT變換時(shí)的圖形，如蝴蝶式樣。函數(shù)關(guān)系：將輸入端二進(jìn)制結(jié)點(diǎn)號(hào)的最高位和最低位互換位置。子蝶式(subbutterfly)B(k) 最低k位的高低位互換 超蝶式(superbutterfly)B(k) 最高k位的高低位互換顯然成立：,4. 反位序函數(shù)（Bit Reversal）函數(shù)關(guān)系：將二進(jìn)制自變量的位序反過來。子反位序函數(shù)，最低k位的位序反過來超反位序函數(shù)，最高k位的位

10、序反過來對(duì)于n＝3的情況，正好有： R＝B，R(2)＝B(2)，R(2)＝B(2)。,5. 移數(shù)函數(shù)函數(shù)關(guān)系：將輸入端向量循環(huán)移動(dòng)一定的位置經(jīng)常取r＝2i，因此移數(shù)函數(shù)又稱為加減2i函數(shù)、PM2I函數(shù)等。子移數(shù)函數(shù)：其中：0 ? x ? N-1，0 ? i, k ? n-1，n = log2N。Illiac函數(shù)包含PM2?0和PM2?n/2等4個(gè)互連函數(shù) 每個(gè)接點(diǎn)與它的上下左右4個(gè)相鄰接點(diǎn)連接,例

11、6.2：假設(shè)16個(gè)處理機(jī)的編號(hào)分別為0、1、…、15，采用單級(jí)互連網(wǎng)絡(luò)?；ミB函數(shù)分別為： (1)Cube3 (2)PM2+3 (3)PM2-0 (4)Shuffle (5)Butterfly (6)Reversal 第13號(hào)處理機(jī)分別與哪一個(gè)處理機(jī)相連？,解： (12)10 = (1100)2 (1) Cube3， (2) PM2+3， (3) PM2-0， (4)

12、Shuffle，(5) Butterfly， (6) Reversal 1100最高位取反得0100， 4號(hào)處理機(jī) (12 + 8) MOD 16 = 4， 4號(hào)處理機(jī) 12 – 1 = 11， 11號(hào)處理機(jī) 1100循環(huán)左移1位得到1001, 9號(hào)處理機(jī) 1100的最高最低位交換0101, 5號(hào)處理機(jī) 1100的

13、位序反過來為0011, 3號(hào)處理機(jī),7.2 互連網(wǎng)絡(luò)的種類,7.2.1 靜態(tài)互連網(wǎng)絡(luò) 7.2.2 循環(huán)互連網(wǎng)絡(luò)7.2.3 多級(jí)互連網(wǎng)絡(luò)7.2.4 全排列互連網(wǎng)絡(luò)7.2.5 全交叉開關(guān)網(wǎng)絡(luò),靜態(tài)互連網(wǎng)絡(luò)：連接通路是固定的，一般不能實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。循環(huán)互連網(wǎng)絡(luò)：通過多次重復(fù)使用同一個(gè)單級(jí)互連網(wǎng)絡(luò)以實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連 。多級(jí)互連網(wǎng)絡(luò)：將多套相同的單級(jí)互連網(wǎng)絡(luò)連接起來，實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的

14、互連。全排列互連網(wǎng)絡(luò)：能夠同時(shí)實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。全交叉開關(guān)網(wǎng)絡(luò)：能夠同時(shí)實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連，還能夠?qū)崿F(xiàn)廣播和多播。,7.2.1 靜態(tài)互連網(wǎng)絡(luò),按照網(wǎng)絡(luò)的互連特性為特征分類，可分為如下幾類：1. 靜態(tài)互連網(wǎng)絡(luò)在各結(jié)點(diǎn)之間有固定的連接通路，在運(yùn)行過程中不能改變的網(wǎng)絡(luò)結(jié)構(gòu)。一般靜態(tài)互連網(wǎng)絡(luò)不能實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。一維的有線性陣列結(jié)構(gòu)；二維的有環(huán)形、星形、樹形、網(wǎng)格形等；三維的有立方體等；三維以上的

15、有超立方體等。,1. 超立方體網(wǎng)n維立方體由N＝2n個(gè)結(jié)點(diǎn)，分布在n維上超立方體網(wǎng)采用交換函數(shù),網(wǎng)絡(luò)規(guī)模為2n個(gè)結(jié)點(diǎn)結(jié)點(diǎn)度為n直徑也為n,2. 環(huán)形網(wǎng)采用移數(shù)函數(shù)單向環(huán)行網(wǎng)：右環(huán)網(wǎng)采用PM2+0函數(shù)，左環(huán)網(wǎng)采用PM2-0函數(shù)，對(duì)稱，直徑是N，結(jié)點(diǎn)度是2雙向環(huán)行網(wǎng)：又稱一維鄰居網(wǎng)，采用{PM2+0，PM2-0}函數(shù)，對(duì)稱，直徑為N/2 ，結(jié)點(diǎn)度是2 弦環(huán)網(wǎng)：增加的弦愈多，則結(jié)點(diǎn)度愈高，網(wǎng)絡(luò)直徑愈小。循環(huán)移數(shù)網(wǎng)絡(luò)：將每個(gè)結(jié)

16、點(diǎn)與其距離為2的整數(shù)冪的結(jié)點(diǎn)連接構(gòu)成。,循環(huán)移數(shù)網(wǎng)的結(jié)點(diǎn)度為2n-1，直徑為?n/2?。,環(huán)形網(wǎng),3. 樹形和星形網(wǎng) 二叉樹：一棵k層二叉樹有N＝2k－1個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)度是3，直徑是2(k-1)。星形：一種特殊的2層樹，結(jié)點(diǎn)度很高，為d=N-1，直徑是2。二叉胖樹：緩解了根結(jié)點(diǎn)通信速度高的矛盾,4. 網(wǎng)格形網(wǎng)二維網(wǎng)格網(wǎng)：結(jié)點(diǎn)度為 ，直徑為　　　。k維網(wǎng)格網(wǎng)：網(wǎng)絡(luò)規(guī)模為 ，結(jié)點(diǎn)度為 ，直徑為

17、 。環(huán)網(wǎng)形網(wǎng)格網(wǎng)：沿陣列每行每列都有環(huán)形連接。n×n二元環(huán)網(wǎng)的結(jié)點(diǎn)度為 ，直徑為 。環(huán)網(wǎng)形網(wǎng)格網(wǎng)是一種 的拓?fù)浣Y(jié)構(gòu),4,2(n-1),4,2?n/2?,對(duì)稱,N=nk,2k,k(n-1),5. 二維閉合螺旋線網(wǎng)格網(wǎng)結(jié)點(diǎn)度為4，網(wǎng)絡(luò)直徑為n-1。一個(gè)n×n的Illiac 網(wǎng)格的直徑為 n-1。8×8網(wǎng)格，結(jié)點(diǎn)度為4，直徑為7。,7.2.2 循環(huán)互連網(wǎng)

18、絡(luò),一般靜態(tài)互連網(wǎng)不能實(shí)現(xiàn)任意兩結(jié)點(diǎn)之間的互連。有兩種解決辦法：循環(huán)互連網(wǎng)：多次重復(fù)使用同一個(gè)單級(jí)互連網(wǎng)絡(luò)多級(jí)互連網(wǎng)：將多套相同的單級(jí)互連網(wǎng)絡(luò)連接起來前一種方法是犧牲時(shí)間換取設(shè)備，后一種方法是以設(shè)備換取時(shí)間RN為網(wǎng)絡(luò)連接寄存器，它有三個(gè)用處：發(fā)送消息，接收消息，轉(zhuǎn)發(fā)消息,例如：對(duì)于一個(gè)3維立方體網(wǎng)，如果要從PE0發(fā)送消息到PE3，需要經(jīng)過如下4步： 周期1：PE0?RN0，周期2：RN0?RN1 周期3：RN1?R

19、N3，周期4：RN3?PE3,7.2.3 多級(jí)互連網(wǎng)絡(luò),循環(huán)互連網(wǎng)絡(luò)雖然能夠?qū)崿F(xiàn)結(jié)點(diǎn)到結(jié)點(diǎn)之間的任意互連，但是其通信速度低。多級(jí)互連網(wǎng)絡(luò)采用多個(gè)相同的或不同的單級(jí)互連網(wǎng)絡(luò)直接連接起來。一個(gè)時(shí)鐘周期就能夠?qū)崿F(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連。多級(jí)互連網(wǎng)絡(luò)采用的關(guān)鍵技術(shù)：(1) 交換開關(guān)，(2) 交換開關(guān)之間的拓?fù)溥B接，(3) 對(duì)交換開關(guān)的不同控制方式。,1. 交換開關(guān)一個(gè)a×b交換開關(guān)有a個(gè)輸入和b個(gè)輸出。最常用的二元

20、開關(guān)：a=b=2。每個(gè)輸入可與一個(gè)或多個(gè)輸出相連，但是在輸出端必須避免發(fā)生沖突。一對(duì)一和一對(duì)多映射是容許的；但不容許有多對(duì)一映射。只容許一對(duì)一映射時(shí)稱為置換連接，稱這種開關(guān)為交叉開關(guān)。具有直通和交換兩種功能的開關(guān)稱為二功能開關(guān)，或交換開關(guān)。用一位控制信號(hào)控制。具有所有4種功能的交換開關(guān)稱為四功能開關(guān)，用兩位控制信號(hào)控制。,2. 拓?fù)浣Y(jié)構(gòu)前一級(jí)交換開關(guān)的輸出端與后一級(jí)交換開關(guān)的輸入端之間的連接模式稱為拓?fù)浣Y(jié)構(gòu)。通常，采用前面介

21、紹過的互連函數(shù)實(shí)現(xiàn)拓?fù)浣Y(jié)構(gòu)。實(shí)際上，從結(jié)點(diǎn)的輸出到第一級(jí)交換開關(guān)的輸入，以及從最后一級(jí)交換開關(guān)的輸出到結(jié)點(diǎn)的輸入也可以采用拓?fù)浣Y(jié)構(gòu)連接。,3. 控制方式有多級(jí)交換開關(guān)，每一級(jí)又有多個(gè)交換開關(guān)。通常有三種控制方式級(jí)控制：同一級(jí)交換開關(guān)使用同一個(gè)控制信號(hào)控制。單元級(jí)控制：每個(gè)交換開關(guān)分別控制。部分級(jí)控制：第i級(jí)使用i+1個(gè)控制信號(hào)控制（0?i?n-1）。同一個(gè)多級(jí)互連網(wǎng)絡(luò)分別常用三種不同的控制方式，可以構(gòu)成三種不同的互連網(wǎng)絡(luò)

22、。,4. 多級(jí)立方體網(wǎng)采用二功能開關(guān)，總共需要開關(guān) n 2n-1個(gè)。采用交換函數(shù)，各級(jí)分別采用E0,E1,…En-1函數(shù)當(dāng)所有開關(guān)都直通時(shí)，實(shí)現(xiàn)恒等變換。當(dāng)A、B、C、D交換，其余直通實(shí)現(xiàn) E0函數(shù)。當(dāng)E、F、G、H交換，其余直通實(shí)現(xiàn) E1函數(shù)。當(dāng)I、J、K、L交換，其余直通實(shí)現(xiàn) E2函數(shù)。采用不同的控制方式，可構(gòu)成不同的互連網(wǎng)絡(luò)采用級(jí)控制可以構(gòu)成STARAN交換網(wǎng)。采用部分級(jí)控制，可以構(gòu)成STARAN移數(shù)網(wǎng)

23、。采用級(jí)控制可以構(gòu)成間接二進(jìn)制n方體網(wǎng)。,多級(jí)立方體網(wǎng),7.2.4 全排列互連網(wǎng)絡(luò),循環(huán)互連網(wǎng)絡(luò)和多級(jí)互連網(wǎng)絡(luò)不能實(shí)現(xiàn)同時(shí)多個(gè)結(jié)點(diǎn)之間的互連。例如：多級(jí)立方體網(wǎng)中，如果要求同時(shí)實(shí)現(xiàn)0?5和1?7的互連，在開關(guān)A發(fā)生沖突。全排列互連網(wǎng)絡(luò)不僅能夠?qū)崿F(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連，而且能夠?qū)崿F(xiàn)同時(shí)任意結(jié)點(diǎn)之間的互連。解決方法：采用多個(gè)多級(jí)互連網(wǎng)絡(luò)連接。原理：N個(gè)結(jié)點(diǎn)的全排列需要有N！，N個(gè)結(jié)點(diǎn)的多級(jí)互連網(wǎng)絡(luò)共有二功能開關(guān)n 2n-1個(gè)

24、，共有不同的狀態(tài)種類：,7.2.5 全交叉開關(guān)網(wǎng)絡(luò),全交叉開關(guān)網(wǎng)絡(luò)除了能夠?qū)崿F(xiàn)同時(shí)任意結(jié)點(diǎn)之間的互連之外，還能夠?qū)崿F(xiàn)廣播和多播。在多處理機(jī)系統(tǒng)中，處理機(jī)、存儲(chǔ)器和IOP之間用交叉開關(guān)網(wǎng)絡(luò)連接。,7.3 消息傳遞機(jī)制,7.3.1 消息尋經(jīng)方式7.3.2 虛擬通道7.3.3 流控制策略7.3.4 選播與廣播,7.3.1 消息尋徑方式,1. 線路交換(circuit switch)先建立一條從源結(jié)點(diǎn)到目的結(jié)點(diǎn)的物理通路

25、，然后傳遞消息。傳輸時(shí)延用公式：T＝(Lt/B)×D+L/B， 其中：Lt為建立路徑所需的小信息包的長度， L為信息包的長度， D為經(jīng)過的結(jié)點(diǎn)數(shù)，B為帶寬。優(yōu)點(diǎn)：實(shí)際通信時(shí)間較短，使用緩沖區(qū)少。缺點(diǎn)：建立物理通路的開銷很大，占用物理通路的時(shí)間長。,2. 存儲(chǔ)轉(zhuǎn)發(fā)(store and forward)每個(gè)結(jié)點(diǎn)有一個(gè)包緩沖區(qū)，包從源結(jié)點(diǎn)經(jīng)過中間結(jié)點(diǎn)到達(dá)目的結(jié)

26、點(diǎn)。存儲(chǔ)轉(zhuǎn)發(fā)網(wǎng)絡(luò)的時(shí)延與源和目的地之間的距離成正比。 時(shí)延用公式： T＝(L/B)×D+L/B=(D+1)×L/B優(yōu)點(diǎn)：占用物理通路的時(shí)間比較短。缺點(diǎn)：包緩沖區(qū)大，時(shí)延大（與結(jié)點(diǎn)距離成正比）。,3. 虛擬直通(virtual cut through)當(dāng)接收到用作尋徑的消息頭部時(shí)，即開始路由選擇。通信時(shí)延公式： T=(Lh/B)×D+L/B=(Lh×D+L

27、)/B≈L/B其中：Lh是尋徑頭部的長度，一般L>>Lh×D當(dāng)出現(xiàn)尋徑阻塞時(shí)，只能將整個(gè)消息存儲(chǔ)在尋徑結(jié)點(diǎn)中。優(yōu)點(diǎn)：通信延遲與結(jié)點(diǎn)數(shù)無關(guān)。缺點(diǎn)：每個(gè)結(jié)點(diǎn)需要有足夠大的緩沖區(qū)。在最壞的情況下與存儲(chǔ)轉(zhuǎn)發(fā)方式的通信時(shí)延相同，經(jīng)過的每個(gè)結(jié)點(diǎn)都阻塞，都需要緩沖。,4. 蟲蝕尋徑(wormhole)把包分成更小的片。每個(gè)結(jié)點(diǎn)的尋徑器中設(shè)置有片緩沖區(qū)。用頭片直接開辟一條從輸入結(jié)點(diǎn)到輸出結(jié)點(diǎn)的路徑。每個(gè)消息中的片以流

28、水方式在網(wǎng)絡(luò)中向前“蠕動(dòng)”。當(dāng)消息的頭片到達(dá)一個(gè)結(jié)點(diǎn)的尋徑器后，尋徑器根據(jù)頭片的尋徑消息立即做出路由選擇如果所選擇的通道或結(jié)點(diǎn)的片緩沖區(qū)不可用時(shí)，頭片必須在該結(jié)點(diǎn)的片緩沖區(qū)中等待，其它數(shù)據(jù)片也在原來的結(jié)點(diǎn)上等待。,時(shí)延公式： T=Tf×D+L/B=(Lf/B)×D＋L/B=(Lf×D＋L)/B,其中：Lf是片的長度， Tf是片經(jīng)過一個(gè)結(jié)點(diǎn)所需時(shí)間。 一般有

29、L>>Lf×D，時(shí)延近似為：T＝L/B，與結(jié)點(diǎn)數(shù)無關(guān)。優(yōu)點(diǎn)：每個(gè)結(jié)點(diǎn)的緩沖區(qū)較小。 較低的網(wǎng)絡(luò)傳輸時(shí)延；通道共享性好，利用率高；易于實(shí)現(xiàn)選播和廣播通信方式。缺點(diǎn)：當(dāng)消息的一個(gè)片被阻塞時(shí)，整個(gè)消息都被阻塞。,7.3.2 虛擬通道,1. 虛擬通道 虛擬通道是兩個(gè)結(jié)點(diǎn)間的邏輯鏈路，由源結(jié)點(diǎn)的片緩沖區(qū)、結(jié)點(diǎn)間的物理通道及接收結(jié)點(diǎn)的片緩沖區(qū)組成。,2. 死鎖的產(chǎn)生與避免緩沖區(qū)或通道上的循環(huán)等待會(huì)引起死鎖。

30、利用虛擬通道可以減少死鎖。虛擬通道可能會(huì)使每個(gè)請(qǐng)求可用的有效通道頻寬降低。,7.3.3 流控制策略,在相鄰結(jié)點(diǎn)間傳送片時(shí)，必須具備三個(gè)條件：(1) 源緩沖區(qū)已存有該片；(2) 通道已分配好；(3) 接收緩沖區(qū)準(zhǔn)備接收該片。接收緩沖區(qū)或輸出通道沖突的仲裁：(1) 把后一個(gè)包暫時(shí)存放在緩沖區(qū)。(2) 阻塞后一個(gè)包。 (3) 場(chǎng)棄后一個(gè)包。(4) 繞道。,,維序?qū)剿惴ǎ?按照特定順序選擇后繼通道。

31、在二維網(wǎng)格網(wǎng)絡(luò)中稱為X-Y尋徑： 例如，X優(yōu)先于Y 在超立方體中稱為E立方體尋徑： 逐維改變。 適應(yīng)尋徑,采用雙虛擬通道和X-Y尋經(jīng)可以完全避免死鎖,2024年3月1日星期五,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第七章 互連網(wǎng)絡(luò),53,超立方體網(wǎng)絡(luò)的E立方體尋徑,,,,2024年3月1日星期五,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第七章 互連網(wǎng)絡(luò),54,自適應(yīng)尋徑   

32、0;采用自適應(yīng)尋徑要特別注意避免死鎖。虛擬通道的概念使實(shí)現(xiàn)自適應(yīng)尋徑更經(jīng)濟(jì)和更靈活。圖7.33說明怎樣利用虛擬通道達(dá)到這一目的。在網(wǎng)格連接網(wǎng)絡(luò)中，同一維的所有連接都使用虛擬通道。,,沒有虛擬通道的原形網(wǎng)絡(luò),向西方向傳輸信息,Y維方向有兩對(duì)虛擬通道,向東方向傳輸信息,2024年3月1日星期五,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第七章 互連網(wǎng)絡(luò),55,雙通道網(wǎng)格網(wǎng)絡(luò)可實(shí)現(xiàn)4個(gè)虛擬網(wǎng)絡(luò),2024年3月1日星期五,計(jì)算機(jī)系統(tǒng)結(jié)構(gòu) 第七章

33、互連網(wǎng)絡(luò),56,7.3.4 選播與廣播尋徑算法,四種通信模式：(1)單播(unicast)，一對(duì)一傳送。(2)選播(multicast)，從一個(gè)源結(jié)點(diǎn)發(fā)送同一消息到多個(gè)目的結(jié)點(diǎn)(3)廣播(broadcast)，從一個(gè)源結(jié)點(diǎn)發(fā)送同一消息到全部結(jié)點(diǎn)。(4)會(huì)議(conference)，多到多的通信情況。擴(kuò)充選播樹的原則：選擇某些維使剩余目的結(jié)點(diǎn)的集合最小。貪婪選播算法所需的通道數(shù)，與多次單播或廣播樹所需的通道數(shù)相比要少。,7.4

34、 互連網(wǎng)絡(luò)實(shí)例,7.4.1 總線互連7.4.2 多端口存儲(chǔ)器7.4.3 STARAN交換網(wǎng)和STARAN移數(shù)網(wǎng)7.4.4 Omega互連網(wǎng),7.4.1 總線互連,總線的優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單，很方便實(shí)現(xiàn)廣播?？偩€的缺點(diǎn)：帶寬低，發(fā)生沖突的可能性大。總線沖突的解決辦法有：(1) 設(shè)置靜態(tài)優(yōu)先級(jí)(2) 在同步方式中采用時(shí)間片(3) 采用動(dòng)態(tài)優(yōu)先級(jí)（如LRU法等）(4) 先來先服務(wù)提高總線通信帶寬的方法有：(1

35、) 采用多總線結(jié)構(gòu)(2) 層次總線結(jié)構(gòu)(3) 多維總線結(jié)構(gòu),多總線：西門子公司的SMS系統(tǒng)（Stractured Multiprocessor System）通過8條總線連接128個(gè)處理機(jī)。,層次總線：卡內(nèi)基梅隆大學(xué)的Cm*多處理機(jī)系統(tǒng)采用層次總線結(jié)構(gòu)。 三級(jí)總線：群總線、Map總線、處理機(jī)總線 每群14臺(tái)處理機(jī),7.4.2 多端口存儲(chǔ)器,多個(gè)多端口存儲(chǔ)器與多個(gè)CPU和IOP連接。多端口存儲(chǔ)器用于處理機(jī)

36、個(gè)數(shù)不多的系統(tǒng)中。把復(fù)雜的互連網(wǎng)絡(luò)移到了存儲(chǔ)器中。,7.4.3 STARAN交換網(wǎng)和移數(shù)網(wǎng),多級(jí)立方體網(wǎng)，應(yīng)用在巨型機(jī)STARAN中。采用級(jí)控制可以構(gòu)成STARAN交換網(wǎng)。采用部分級(jí)控制，可以構(gòu)成STARAN移數(shù)網(wǎng)。,STARAN交換網(wǎng)實(shí)現(xiàn)交換函數(shù)關(guān)系例如：輸入端：0 1 2 3 4 5 6 7 4G2E： 1?0 3?2 5?4 7?8 2G4E： 2 3?0 1 6 7

37、?4 5 結(jié)果為：(0,2) (1,3) (4,6) (5,7),,,STARAN移數(shù)網(wǎng)實(shí)現(xiàn)移數(shù)函數(shù)關(guān)系因?yàn)榈趇級(jí)用i+1個(gè)控制信號(hào)，因此共有6個(gè)控制信號(hào)。 有64種不同的控制。 表中僅列出了一小部分。,7.4.4 Omega互連網(wǎng),采用全混洗函數(shù)和交換函數(shù)，又稱混洗交換網(wǎng)絡(luò)。N個(gè)輸入的Omega網(wǎng)絡(luò)有l(wèi)og2N級(jí)，每級(jí)有N/2個(gè)2×2的四功能交換開關(guān)，每級(jí)的拓?fù)浣Y(jié)構(gòu)相同，采用單元控制（每一級(jí)的控

38、制信號(hào)均相同）。Omega網(wǎng)能夠?qū)崿F(xiàn)任意一個(gè)輸入端到任意一個(gè)輸出端的連接。但不能同時(shí)實(shí)現(xiàn)多個(gè)輸入端到多個(gè)輸出端的連接。當(dāng)有N個(gè)輸入端時(shí)，共有NN/2個(gè)種變換。如果要同時(shí)實(shí)現(xiàn)任意一個(gè)輸入端到任意一個(gè)輸出端的連接，共需要N！種變換換。 Omega網(wǎng)能夠?qū)崿F(xiàn)從任意一個(gè)輸入端到所有輸出端的廣播。,同時(shí)實(shí)現(xiàn)0?6和4?7有沖突，同樣還有：3?0和5?1，3?0和7?3，5?0和7?1等。8個(gè)輸入端的Omega網(wǎng)絡(luò)實(shí)際上只能實(shí)現(xiàn)全部變換的10