計算機互連網(wǎng)絡ppt課件(編輯修改稿)
2025-05-30 07:08 本頁面
【文章內(nèi)容簡介】 函數(shù)開關(guān)狀態(tài)如右圖 所示 ， 其連接規(guī)律是把各入端結(jié)點編號加上 相同的增量 21（ mod N） ， 獲得出端結(jié)點編號 。 單級加減 2i網(wǎng) （ PM2I網(wǎng)，移數(shù)網(wǎng)， P398倒數(shù)第 2行） 0 01 12 23 34 45 56 67 72022/5/31 計算機系統(tǒng)結(jié)構(gòu) 22 N = 8的 PM2+i網(wǎng)絡拓撲形狀如下圖所示，可以看出它包含多個強連通子圖（即除去若干邊以后仍能保證任何一對結(jié)點互相可達），所以這 2n個函數(shù)并不是實現(xiàn)互連網(wǎng)的最小集合。實際應用中為了降低造價，人們往往取它們的一個子集來構(gòu)造互連網(wǎng)。 ? 性質(zhì) 1：對相同的 i值 ， PM2+i 與 PM2i函數(shù)的傳送路徑相同 ， 方向相反 （ 右圖中所有箭頭 反向即為 PM21的拓撲形狀 ） ； ? 性質(zhì) 2： PM2+(n1) = PM2(n1)。 根據(jù)性質(zhì) 2， 我們知道 單級 PM2I網(wǎng)絡實際上只能 實現(xiàn) 2n1種不同的置換 。 單級 PM2I網(wǎng)絡的直徑是 。 ? ?2/n i=1 i=207 1i=06 25 342022/5/31 計算機系統(tǒng)結(jié)構(gòu) 23 各種互連函數(shù)總結(jié) E(Xn1Xn2… X1X0)=Xn1Xn2… X1X0， 其中 0≤ i≤n 1 交換置換函數(shù)定義 Cubei(Xn1… Xi+1XiXi1… X0)=Xn1… Xi+1XiXi1… X0， 其中 0≤ i≤n 1 立方體函數(shù)定義： Cubei的功能是對入端結(jié)點編號二進制形式的第 i位取反 均勻洗牌 shuffle（ Xn1Xn2…… X0） = Xn2…… X0Xn1（ 循環(huán)左移 ） PM2I函數(shù)定義： PM2177。 i的功能是對入端結(jié)點編號加或減 2i， 然后再作模 N運算 PM2+i（ X） = X + 2i mod N PM2i（ X） = X 2i mod N 其中 X = 0 ～ N 1， i = 0 ～ n 1。 2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 24 (3) 多級 ICN（ P409） 定義：多級 ICN使用多級開關(guān) ， 使得數(shù)據(jù)在一次通過網(wǎng)絡的過程中可以實現(xiàn)的置換種類更多 。 通常在 N個結(jié)點的網(wǎng)絡中 ， 多級 ICN由 n級構(gòu)成 （ n = log2N） 。 經(jīng)典的多級互連網(wǎng)有 多級立方體網(wǎng) 、 多級混洗 — 交換網(wǎng) 和 多級 PM2I網(wǎng) 。 我們只學習多級混洗 — 交換網(wǎng) 。 多級立方體網(wǎng)和多級混洗 — 交換網(wǎng)不使用單級互連網(wǎng)中的那種多路選擇開關(guān)， 而是用一種 2輸入 /2輸出的 二元交換開關(guān) ， 以減少開關(guān)總數(shù) 。 二元交換開關(guān)的基本接通狀態(tài)有 “ 直連 ” 、 “ 交換 ” 、 “ 上播 ” 和 “ 下播 ” ， 在進行數(shù)據(jù)置換時只能使用前 2種 。 各開關(guān)的控制信號可采用 3種分配方式之一： 級控方式 、 部分級控方式 和 單元控制方式 。 級控方式 就是同一級 （ 即同一列 ） 開關(guān)共用一個控制信號 ， 動作保持一致；部分級控方式 在第 i級設置 i+1個獨立的控制信號 ， 每個信號管轄若干開關(guān)； 單元控制方式 為每個開關(guān)獨自設置一個控制信號 ， 各開關(guān)動作獨立 ， 性能比前兩種方式都更靈活 ， 結(jié)構(gòu)也更復雜 。 ( a ) 直連 (b ) 交換 (c ) 上播 (d ) 下播2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 25 多級混洗 — 交換網(wǎng)絡（ P410/P436） 多級混洗 — 交換網(wǎng)絡又稱為 Omega網(wǎng) 。 多級混洗 — 交換網(wǎng)絡結(jié)構(gòu)：它 由 n級構(gòu)成 ， 每一級包含 一個無條件 混洗拓撲 線路 和 一列可控的二元 交換開關(guān) ， 前后重復 ， 便于制造 。 如 P436圖 示 。 各級編號是 n1， …… ， 0， 即按 降序排列 。 在多級混洗 — 交換網(wǎng)絡中 ， 單獨一級 混洗拓撲線路可完成一次 數(shù)據(jù)混洗 （shuffle） ， 而單獨一列二元交換開關(guān)在處于 “ 交換 ” 狀態(tài)時可完成一次 交換操作 （ Cube0） 。 如果各級二元交換開關(guān)都處于 “ 直連 ” 狀態(tài) ， N個結(jié)點的數(shù)據(jù)通過網(wǎng)絡僅經(jīng)過 n次混洗操作 ， 排列順序最終 恢復輸入狀態(tài) （ 混洗函數(shù)性質(zhì) 2） ；如果各級二元交換開關(guān)都處于 “ 交換 ” 狀態(tài) ， 則 N個結(jié)點的數(shù)據(jù)在每次混洗之后緊接著一次交換 （ Cube0） ， 也就是地址碼的最低位取反 ， 最后 n位地址均被取反 。 程序員根據(jù)數(shù)據(jù)置換或復制的需要 ， 可以靈活地設置各開關(guān)的狀態(tài) 。 2022/5/31 計算機系統(tǒng)結(jié)構(gòu) 26 多級混洗 — 交換網(wǎng)絡尋徑算法（路由算法） 目的 ：根據(jù)給定的輸入 /輸出對應關(guān)系 ， 確定各開關(guān)的狀態(tài) 。 名稱 ：源 目的地址異或法 操作 ：將任一個輸入地址與它要到達的輸出地址作異或運算 ， 其結(jié)果的 biti位控制數(shù)據(jù)到達的第 i級開關(guān) ， “ 0” 表示 “ 直連 ” ， “ 1” 表示 “ 交換 ” 。 例如給定傳輸 101B→ 011B， 二者異或結(jié)果為 110B， 于是從 101B號輸入端開始 ， 把它遇到的第 2級開關(guān)置為 “ 交換 ” ， 第 1級開關(guān)置為 “ 交換 ” ， 第 0級開關(guān)置為 “ 直連 ” 。 如下圖 紅線 所示 。 輸入 第 2 級 第 1 級 第 0 級 輸出000 00 000 1 00 10 1 0 0 1 00 11 01 11 00 1 001 0 1 1 0111 0 1 101 11 1 112022/5/31 計算機系統(tǒng)結(jié)構(gòu) 27 Omega網(wǎng)尋徑?jīng)_突 給定傳輸 101B→ 011B， 二者異或結(jié)果為 110B， 路徑 如下圖 紅線 所示 。 給定傳輸 011→
教學課件相關(guān)推薦
鄂ICP備17016276號-1