計算機系統(tǒng)結構第七章互連網(wǎng)絡

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

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

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

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

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

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

7、對應關系，互連網(wǎng)絡有三種表示方法：(1)互連函數(shù)表示法： 如：f(xn-1…x1x0) = x0xn-2…x1xn-1(2)圖形表示法(3)輸入輸出對應表示法,互連網(wǎng)絡,,…,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） 當n＝3時，有3種函數(shù)

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

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

10、序反過來對于n＝3的情況，正好有： R＝B，R(2)＝B(2)，R(2)＝B(2)。,5. 移數(shù)函數(shù)函數(shù)關系：將輸入端向量循環(huán)移動一定的位置經(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個互連函數(shù) 每個接點與它的上下左右4個相鄰接點連接,例

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

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

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

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

15、有超立方體等。,1. 超立方體網(wǎng)n維立方體由N＝2n個結點，分布在n維上超立方體網(wǎng)采用交換函數(shù),網(wǎng)絡規(guī)模為2n個結點結點度為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ù)，對稱，直徑是N，結點度是2雙向環(huán)行網(wǎng)：又稱一維鄰居網(wǎng)，采用{PM2+0，PM2-0}函數(shù)，對稱，直徑為N/2 ，結點度是2 弦環(huán)網(wǎng)：增加的弦愈多，則結點度愈高，網(wǎng)絡直徑愈小。循環(huán)移數(shù)網(wǎng)絡：將每個結

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

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

18、絡,一般靜態(tài)互連網(wǎng)不能實現(xiàn)任意兩結點之間的互連。有兩種解決辦法：循環(huán)互連網(wǎng)：多次重復使用同一個單級互連網(wǎng)絡多級互連網(wǎng)：將多套相同的單級互連網(wǎng)絡連接起來前一種方法是犧牲時間換取設備，后一種方法是以設備換取時間RN為網(wǎng)絡連接寄存器，它有三個用處：發(fā)送消息，接收消息，轉發(fā)消息,例如：對于一個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 多級互連網(wǎng)絡,循環(huán)互連網(wǎng)絡雖然能夠實現(xiàn)結點到結點之間的任意互連，但是其通信速度低。多級互連網(wǎng)絡采用多個相同的或不同的單級互連網(wǎng)絡直接連接起來。一個時鐘周期就能夠實現(xiàn)任意結點到結點之間的互連。多級互連網(wǎng)絡采用的關鍵技術：(1) 交換開關，(2) 交換開關之間的拓撲連接，(3) 對交換開關的不同控制方式。,1. 交換開關一個a×b交換開關有a個輸入和b個輸出。最常用的二元

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、個數(shù)不多的系統(tǒng)中。把復雜的互連網(wǎng)絡移到了存儲器中。,7.4.3 STARAN交換網(wǎng)和移數(shù)網(wǎng),多級立方體網(wǎng)，應用在巨型機STARAN中。采用級控制可以構成STARAN交換網(wǎng)。采用部分級控制，可以構成STARAN移數(shù)網(wǎng)。,STARAN交換網(wǎng)實現(xiàn)交換函數(shù)關系例如：輸入端：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 結果為：(0,2) (1,3) (4,6) (5,7),,,STARAN移數(shù)網(wǎng)實現(xiàn)移數(shù)函數(shù)關系因為第i級用i+1個控制信號，因此共有6個控制信號。 有64種不同的控制。 表中僅列出了一小部分。,7.4.4 Omega互連網(wǎng),采用全混洗函數(shù)和交換函數(shù)，又稱混洗交換網(wǎng)絡。N個輸入的Omega網(wǎng)絡有l(wèi)og2N級，每級有N/2個2×2的四功能交換開關，每級的拓撲結構相同，采用單元控制（每一級的控

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