《計算機互連網(wǎng)絡(luò)》ppt課件-文庫吧
2025-04-18 07:08 本頁面
【正文】 級數(shù)而上升。另外，由于增加了連線和開關(guān)復雜性，價格也是一種限制因素。 總線、多級網(wǎng)絡(luò)、交叉開關(guān)的對比 2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 15 特點：成本低，并行性差。 (1) 拓撲結(jié)構(gòu) (硬件， P402P407)： 直線，單向環(huán)，雙向環(huán)，帶弦環(huán)，樹，星型（真星型，假星型），完全網(wǎng)。 (2) 傳輸協(xié)議 (使用規(guī)則，軟件， P427P435)： 碰撞爭用，令牌協(xié)議，劍橋環(huán)。 (3) 主要參數(shù) (P399)： 直徑，中剖寬度，結(jié)點的度，最長邊。 示例： (4) 典型代表：以太網(wǎng)，令牌網(wǎng)（環(huán)或直線）。 通用網(wǎng) 2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 16 特點：并行度高，造價昂貴。 (1) 互連函數(shù) N個輸入到 N個輸出的一種對應狀態(tài)可以用一個映射函數(shù)表示，稱為互連函數(shù)。它是處理單元集合對于自身的雙射映射，所以又稱為“ 置換 ”，或者“ 循環(huán) ”。 互連函數(shù)有多種表示方式，如下例所示： f(0)=1 0 0 f(1)=2 1 1 f= 0 1 2 3 f=(0,1,2)(3) f(2)=0 2 2 1 2 0 3 f(3)=3 3 3 一個網(wǎng)絡(luò)通過開關(guān)切換可以形成多個映射關(guān)系，所以要用“ 互連函數(shù)族 ”來定義一個網(wǎng)絡(luò)。 專用網(wǎng) 2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 17 定義： 單級 ICN只使用一級開關(guān)，如下圖所示。 開關(guān)的每種接通組合方式可用一個互連函數(shù)表示。 f( j入 ) = j出 ， 0≤ j≤N 1 在互連函數(shù)中，記： N ── 結(jié)點數(shù) n = log2N ── 維數(shù) j= Xn1…… X0 ─ ─ 結(jié)點 編號的二進制形式，位數(shù)為 n。 互連函數(shù)族的組成必須使網(wǎng)絡(luò)成為 連通圖 。 (2) 單級 ICN ICN 0 0N1 N12022/5/31 計算機系統(tǒng)結(jié)構(gòu) 18 該網(wǎng)絡(luò)由立方體 函數(shù)定義 ， 立方體 函數(shù)族有 n個成員 ， 分別是 Cube0， Cube1， …… ， Cuben1。 立方體 函數(shù) 定義： Cubei的功能 是對 入端結(jié)點編號二進制形式的第 i位取反 Cubei(Xn1… Xi+1XiXi1… X0)=Xn1… Xi+1XiXi1… X0， 其中 0≤ i≤n 1 例如： Cube0(0)=1， Cube3(7)=15。 n=3的單級立方體網(wǎng)絡(luò)拓撲形狀如 右 圖所示 。 最壞情況下的傳輸需 對輸入結(jié)點編號的全部 n位取反 。 所以 單級立方體網(wǎng)絡(luò)的直徑是 n。 立方體 函數(shù) 性質(zhì) ： 結(jié)合律 、 交換律 以及 自反 律 （ Cubei重復使用 2次的結(jié)果與原始自變量相 同 ） 。 單級立方體網(wǎng) （ Cube網(wǎng)， P396第 1行 / P405第 4行） 2 30 1 6 74 52022/5/31 計算機系統(tǒng)結(jié)構(gòu) 19 該網(wǎng)絡(luò)由 混洗函數(shù) （ shuffle） 與 交換函數(shù) （ exchange即 Cube0） 定義 ， 或者說它的互連函數(shù)族只有這兩個成員 。 ? 混洗函數(shù) 定義： 2j mod（ N1） ， 當 j N1 shuffle（ j） = N1 ， 當 j = N1 例如：當 N=8時 ， shuffle（ 0） = 0， shuffle（ 1） = 2， shuffle（ 7） = 7。 n=3的混洗函數(shù)開關(guān)狀態(tài)如 P397圖 (a)所示 ， 其連接規(guī)律就像洗牌 。 ? 性質(zhì) 1： shuffle（ Xn1Xn2…… X0） = Xn2…… X0Xn1（ 循環(huán)左移） ? 性質(zhì) 2： shufflen（ j） = j n=3的 混洗 網(wǎng)絡(luò)拓撲形狀如下圖 綠線 所示 ， 可以看出它不是一個 連通圖 ， 所以還需要增加一個 交換函數(shù) （ 圖中 紅線 所示 ） ， 才能構(gòu)成完整的單級混洗 — 交換網(wǎng)絡(luò) 。 單級混洗 — 交換網(wǎng)絡(luò)的直 徑是 2n1。 單級混洗 交換網(wǎng) （ P396倒數(shù)第 8行 ） 0 1 2 3 4 5 6 72022/5/31 計算機系統(tǒng)結(jié)構(gòu) 20 交換置換（ P395） E(Xn1Xn2… X1X0)=Xn1Xn2… X1X0， 其中 0≤ i≤n 1 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 n=3的交換置換形狀如 右 圖所示。 交換置換函數(shù)定義：對入端結(jié)點編號二進制形式的第 0位取反 0 1 2 3 4 5 6 7 2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 21 該網(wǎng)絡(luò)由 PM2I函數(shù)定義 ， PM2I函數(shù)共有 n對成員 ， 分別是 PM2 177。 0， PM2 177。 1，…… ， PM2 177。 (n1)。 PM2I函數(shù)定義： PM2177。 i的功能是對入端結(jié)點編號加或減 2i， 然后再作模 N運算 PM2+i（ j） = j + 2i mod N PM2i（ j） = j 2i mod N 其中 j = 0 ～ N 1， i = 0 ～ n 1。 例如：當 N = 8時 ， PM2+0（ 0） = 0 + 20 = 1， PM2+0（ 1） = 1 + 20 = 2， PM2+0（ 7） = 7 + 20 = 0， PM2+1（ 0） = 0 + 21 = 2。 N = 8的 PM2+1（ j）
教學課件相關(guān)推薦
鄂ICP備17016276號-1