【文章內(nèi)容簡介】 交叉 0 1 0 1 上播 0 1 0 1 下播 交換開關(guān) 一個 a b交換開關(guān)有 a個輸入和 b個輸出 。 最常用的二元開關(guān)： a=b=2。 每個輸入可與一個或多個輸出相連，但是在輸出端必須避免發(fā)生沖突。一對一和一對多映射是容許的；但不容許有多對一映射。只容許一對一映射時稱為置換連接，稱這種開關(guān)為 n n交叉開關(guān)。具有直通和交叉兩種功能的交換開關(guān)稱為二功能開關(guān)，或交換開關(guān)。用一位控制信號控制。具有所有四種功能的交換開關(guān)稱為四功能開關(guān)，用兩位控制信號控制。 （ 2）級間互連模式（拓?fù)浣Y(jié)構(gòu)）： – 前一級交換開關(guān)的輸出端與后一級交換開關(guān)的輸入端之間的連接模式稱為拓?fù)浣Y(jié)構(gòu)。 – 通常 ， 采用前面介紹的互連函數(shù)實(shí)現(xiàn)拓?fù)浣Y(jié)構(gòu) 。 – 實(shí)際上 ， 從結(jié)點(diǎn)的輸出到第一級交換開關(guān)的輸入 ， 以及從最后一級交換開關(guān)的輸出到結(jié)點(diǎn)的輸入也可以采用拓?fù)浣Y(jié)構(gòu)連接 。 （ 3）控制方式 在多級互連網(wǎng)絡(luò)中，有多級交換開關(guān)，每一級又有多個交換開關(guān)。 通常有三種控制方式 (1) 級控制：同一級交換開關(guān)使用同一個控制信號控制 。 (2) 單元級控制：每個交換開關(guān)分別控制 。 (3) 部分級控制：例如 ， 第 i級使用 i+1個控制信號控制 （ 0?i?n1） 。 同一個多級互連網(wǎng)絡(luò)分別常用三種不同的控制方式 ， 可以構(gòu)成三種不同的互連網(wǎng)絡(luò) 。 2. Ω網(wǎng) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第 0級 第 1級 第 2級 Ω網(wǎng)的特點(diǎn)： 開關(guān)單元 ： 2?2四功能開關(guān) ISC： 洗牌變換 +恒等變換 控制方式 ：采用單元控制方式。當(dāng)目的地址編碼從高位開始的第 i位（從 0開始）為 0時，第 i級的 2?2開關(guān)的輸入端與上輸出端連接，否則輸入端與下輸出端連接。 A B 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第 0級 第 1級 第 2級 無沖突的實(shí)現(xiàn)置換 π1=（ 0 7 6 4 2）（ 1 3）（ 5） C 對于上圖，觀察一個消息從輸入端 001到輸出端011的路徑。它使用了開關(guān) A、 B和 C。由于目的地址的編碼的最高位為 “ 0”，所以開關(guān) A設(shè)置成直送狀態(tài)，使輸入端 001與開關(guān) A的上輸出端連接。011的中間一位是 “ 1”，所以開關(guān) B設(shè)置成交換狀態(tài)使輸入端與下端相連。 011的最低位為 “ 1”，使開關(guān) C設(shè)置成直送狀態(tài)，使輸入端與 C的下端相連。再考察其他的比如輸入端為 000，輸出端為111等前面 π 1 中提到的其他置換，開關(guān)設(shè)置不存在沖突。 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第 0級 第 1級 第 2級 置換 π2=（ 0 6 4 7 3）（ 1 5）（ 2） 在開關(guān) F、 G、 H、 I和 J上發(fā)生沖突 F G H J I 如上圖， 在開關(guān) F、 G、 H、 I和 J上發(fā)生沖突， F產(chǎn)生沖突的原因是由于 000到 110和 100到 111引起的。因?yàn)閮蓚€目的的地址編碼的最高位都是“ 1”，開關(guān) F的兩個輸入端都要求與下輸出端連接，為了解決這個問題，必須拒絕一個請求。同樣， 011到 000和 111到 011引起開關(guān) G沖突，101到 001和 011到 000引起開關(guān) H沖突。而開關(guān) I和 J的設(shè)置可以實(shí)現(xiàn)一個輸入端與兩個輸出端相連的廣播功能，但條件是開關(guān)要是四功能開關(guān)。 Ω網(wǎng)的特點(diǎn) (2)： 并不是所有的置換在 Ω網(wǎng)中一次通過便可以實(shí)現(xiàn)。 Ω網(wǎng)是阻塞網(wǎng)絡(luò)：出現(xiàn)沖突時，可以采用幾次通過的方法來解決沖突。 如上圖的 π2可以采用幾次通過的方法來解決沖突。在第一次時通過時實(shí)現(xiàn)連接 000110，001101， 010010， 101001， 110100，第二次通過時實(shí)現(xiàn)連接 011000， 100111，111011。 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 第 0級 第 1級 第 2級 Ω網(wǎng)的廣播功能：采用上播或下播開關(guān)設(shè)置， Ω網(wǎng)絡(luò)也可以將數(shù)據(jù)從一個源廣播到八個輸出端，如下圖： 001?8個輸出端 0 1 第 1級 4?4開關(guān)構(gòu)成的 Ω網(wǎng)：多路洗牌 如 16輸入 4路洗牌：網(wǎng)路級數(shù)為 log416 = 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 第 0級 Ω網(wǎng)的特點(diǎn) (3)： 當(dāng)采用 k?k開關(guān)元件時，則可以定義 k路洗牌函數(shù)來構(gòu)造更大的級數(shù)為 logkn的 Ω網(wǎng)絡(luò)。 3. 蝶式網(wǎng)絡(luò)（ Butterfly switch work） 蝶式網(wǎng)絡(luò)的開關(guān)不允許廣播功能，它實(shí)際上是 Omega網(wǎng)的一個子集。 兩級 64 ? 64的蝶式網(wǎng)絡(luò)如下圖所示：它采用 16個 8 ? 8交叉開關(guān)構(gòu)成，兩級間采用8路洗牌連接。 8?8 8?8 8?8 0 . . . 7 8?8 8?8 8?8 第 1級 第 0級 8 . . . 15 56 . . . 63 . . . . . . . . . 0 7 8 15 56 63 . . . . . . . . . . . . . . . . . . . . . . . . 兩級 64 ? 64的蝶式網(wǎng)絡(luò) 全交叉開關(guān)網(wǎng)絡(luò)除了能夠同時實(shí)現(xiàn)任意結(jié)點(diǎn)到結(jié)點(diǎn)之間的互連之外 ， 還能夠?qū)崿F(xiàn)廣播和多播 。 全交叉開關(guān)網(wǎng)絡(luò)的帶寬和互連特性最好 。 在多處理機(jī)系統(tǒng)中，處理機(jī)、存儲器和 IOP之間用交叉開關(guān)網(wǎng)絡(luò)連接 。 ? ? 處理機(jī)１ 處理機(jī) N 處理機(jī)２ 處理機(jī)１ 處理機(jī)２ 處理機(jī)Ｎ 第三章 互連與通信 互連網(wǎng)絡(luò)的作用 靜態(tài)網(wǎng)絡(luò) 動態(tài)網(wǎng)絡(luò) 通信問題 基本術(shù)語與性能指標(biāo) 尋徑算法 虛擬通道與死鎖 包沖突的解決 維序?qū)? 通信模式 通信問題 、包和片 消息（ Message） ：是在多計算機(jī)系統(tǒng)的處理節(jié)點(diǎn)之間傳遞包含數(shù)據(jù)和同步消息的信息包。它是一種邏輯單位，可由任意數(shù)量的包構(gòu)成。因此其長度是可變的。 包（ Packet） ：包是包含尋徑目的地址的基本單位，其長度隨協(xié)議不同而不同，它是信息傳送的最小單位，典型的包由 64512位。由于不同的包可能異步的到達(dá)目的結(jié)點(diǎn)，因此每個包需要一個序號，以便于目的結(jié)點(diǎn)重新裝配。 片（ Flit） ：在某些特殊尋徑的網(wǎng)絡(luò)里，包可以進(jìn)一步被分成片 ,片的長度往往受網(wǎng)絡(luò)的影響。 它們的相互關(guān)系如下圖： 包 …… 消息 包 片 據(jù) 片 頭片 尾片 …… 順序號 數(shù) b b b b b b b b 一個消息的傳輸時延 ：從它在源結(jié)點(diǎn)進(jìn)行發(fā)送初始化到它在目的結(jié)點(diǎn)完整的被接收所耗費(fèi)的時間。 一個網(wǎng)絡(luò)的傳輸時延 ：在一定條件下發(fā)送消息的平均時延。 網(wǎng)絡(luò)的吞吐量 ：單位時間內(nèi)網(wǎng)絡(luò)所能傳輸?shù)南?shù)目或長度。 bns TTTT ??? 其中， Ts稱為 建立時延 ， Tn稱為 網(wǎng)絡(luò)時延 ， Tb稱為 阻塞時延 。 它們具體定義如下： 建立時延 Ts：一個消息在源結(jié)點(diǎn)和目的結(jié)點(diǎn)上裝配和分解、從存儲器拷貝到通信緩沖區(qū)以及正確性驗(yàn)證等所耗費(fèi)的時間。它和機(jī)器本身的硬件、軟件技術(shù)有關(guān)。 sdsss TTT ?? 其中： Tss稱為 源結(jié)點(diǎn)時延 ：從發(fā)送進(jìn)程開始消息發(fā)送初始化到消息的頭部進(jìn)入網(wǎng)絡(luò)所經(jīng)歷的時間。 Tsd稱為 目的結(jié)點(diǎn)時延 ：從消息的尾部到達(dá)目的結(jié)點(diǎn)到消息完全被接收進(jìn)程接收所經(jīng)歷的時間。 網(wǎng)絡(luò)時延 Tn：消息頭部從源結(jié)點(diǎn)進(jìn)入網(wǎng)絡(luò)到消息的尾部到達(dá)目的結(jié)點(diǎn)的時間間隔。 BLDTT pn /??? 其中： Tp?D稱為 結(jié)點(diǎn)時延 ：其中 Tp是消息在它所經(jīng)過的路徑上的每個中間結(jié)點(diǎn)上的平均時延， D為中間結(jié)點(diǎn)或源結(jié)點(diǎn)與目的結(jié)點(diǎn)之間的距離。 L/B稱為 線路時延 ：其中 L為消息長度， B為結(jié)點(diǎn)之間的通道帶寬。 阻塞時延 Tb：消息傳遞過程中其他所有可能的時延（主要原因是資源沖突）。 決定發(fā)送一個消息到其目的地所經(jīng)過的路徑。 確定性算法 ：此方法完全由源地址和目的地址來決定路由，一對源地址和目的地址之間只有一條通路可選，這條固定的通路通常是選擇幾條最短通路中的一條，而且在這條通路的各個中間節(jié)點(diǎn)間轉(zhuǎn)遞分組的算法也要求簡單。這種算法的優(yōu)點(diǎn)是簡單，但如果遇到有沖突或故障時，就無法改選其他通路。 自適應(yīng)算法 ：通信的通路每次都要根據(jù)通信資源或者網(wǎng)絡(luò)的情況來選擇，這樣就可以避開擁擠的或者有故障的結(jié)點(diǎn)，從而網(wǎng)絡(luò)資源的利用效率可以得到改進(jìn)。有很多自適應(yīng)的實(shí)施方案。十分明顯，用自適應(yīng)方法可以是網(wǎng)絡(luò)上的吞吐量提高很多倍。 當(dāng)一個消息在網(wǎng)絡(luò)中沿著某條路徑傳送時，互連網(wǎng)絡(luò)如何來為它分配通道和緩沖器。 我們介紹四種尋徑方式： 存儲轉(zhuǎn)發(fā)（ StoreandForward） 虛擬直通（ Vir