計算機互連網絡ppt課件-文庫吧資料
2025-05-09 07:08本頁面
【正文】 C u b e0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5單級立方體網絡廣播算法 （順序是 C ub e3 ～ C ube0）2022/5/31 計算機系統(tǒng)結構 34 選播算法 選播算法的設計目標有 3種：時間最少、流量最少、在時間最少的多個方案中選取流量最少方案。 如圖 （ 圖中實線箭頭表示一個數據的一次實際傳送 ， 虛線指出上一步已有數據的結點 ） 。下面舉幾個具體實例。向不同方向進行的發(fā)送不能同時進行（具有這種能力的互連網不屬于現在的討論范圍）。 研究廣播與選播算法的目的是盡量利用互連網的并行傳輸能力，尋找花費時間最少或者動用信道次數（又稱 流量 或 通道數 ）最少的方案。個）結點， 1≤N39。 輸入 第 2 級 第 1 級 第 0 級 輸出 000 00 1 0 1 0 0 11 1 00 1 0 1 11 0 1 11 000 00 1 0 1 0 0 11 1 00 1 0 1 11 0 1 11 2022/5/31 計算機系統(tǒng)結構 28 傳輸性能計算 基本傳輸時間（ P400） 說明：指 相鄰結點間傳輸 單個數據包 所用時間，不考慮中間結點轉發(fā)的時間開銷。 輸入 第 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)結構 27 Omega網尋徑沖突 給定傳輸 101B→ 011B， 二者異或結果為 110B， 路徑 如下圖 紅線 所示 。 例如給定傳輸 101B→ 011B， 二者異或結果為 110B， 于是從 101B號輸入端開始 ， 把它遇到的第 2級開關置為 “ 交換 ” ， 第 1級開關置為 “ 交換 ” ， 第 0級開關置為 “ 直連 ” 。 2022/5/31 計算機系統(tǒng)結構 26 多級混洗 — 交換網絡尋徑算法（路由算法） 目的 ：根據給定的輸入 /輸出對應關系 ， 確定各開關的狀態(tài) 。 如果各級二元交換開關都處于 “ 直連 ” 狀態(tài) ， N個結點的數據通過網絡僅經過 n次混洗操作 ， 排列順序最終 恢復輸入狀態(tài) （ 混洗函數性質 2） ；如果各級二元交換開關都處于 “ 交換 ” 狀態(tài) ， 則 N個結點的數據在每次混洗之后緊接著一次交換 （ Cube0） ， 也就是地址碼的最低位取反 ， 最后 n位地址均被取反 。 各級編號是 n1， …… ， 0， 即按 降序排列 。 多級混洗 — 交換網絡結構：它 由 n級構成 ， 每一級包含 一個無條件 混洗拓撲 線路 和 一列可控的二元 交換開關 ， 前后重復 ， 便于制造 。 級控方式 就是同一級 （ 即同一列 ） 開關共用一個控制信號 ， 動作保持一致；部分級控方式 在第 i級設置 i+1個獨立的控制信號 ， 每個信號管轄若干開關； 單元控制方式 為每個開關獨自設置一個控制信號 ， 各開關動作獨立 ， 性能比前兩種方式都更靈活 ， 結構也更復雜 。 二元交換開關的基本接通狀態(tài)有 “ 直連 ” 、 “ 交換 ” 、 “ 上播 ” 和 “ 下播 ” ， 在進行數據置換時只能使用前 2種 。 我們只學習多級混洗 — 交換網 。 通常在 N個結點的網絡中 ， 多級 ICN由 n級構成 （ n = log2N） 。 i的功能是對入端結點編號加或減 2i， 然后再作模 N運算 PM2+i（ X） = X + 2i mod N PM2i（ X） = X 2i mod N 其中 X = 0 ～ N 1， i = 0 ～ n 1。 單級 PM2I網絡的直徑是 。 ? 性質 1：對相同的 i值 ， PM2+i 與 PM2i函數的傳送路徑相同 ， 方向相反 （ 右圖中所有箭頭 反向即為 PM21的拓撲形狀 ） ； ? 性質 2： PM2+(n1) = PM2(n1)。 單級加減 2i網 （ PM2I網，移數網， P398倒數第 2行） 0 01 12 23 34 45 56 67 72022/5/31 計算機系統(tǒng)結構 22 N = 8的 PM2+i網絡拓撲形狀如下圖所示，可以看出它包含多個強連通子圖（即除去若干邊以后仍能保證任何一對結點互相可達），所以這 2n個函數并不是實現互連網的最小集合。 例如：當 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。 PM2I函數定義： PM2177。 1，…… ， PM2 177。 交換置換函數定義：對入端結點編號二進制形式的第 0位取反 0 1 2 3 4 5 6 7 2022/5/31 計算機系統(tǒng)結構 21 該網絡由 PM2I函數定義 ， PM2I函數共有 n對成員 ， 分別是 PM2 177。
教學課件相關推薦
鄂ICP備17016276號-1