【正文】 該網絡由 混洗函數 （ shuffle） 與 交換函數 （ exchange即 Cube0） 定義 ， 或者說它的互連函數族只有這兩個成員 。 1，…… ， PM2 177。 ? 性質 1：對相同的 i值 ， PM2+i 與 PM2i函數的傳送路徑相同 ， 方向相反 （ 右圖中所有箭頭 反向即為 PM21的拓撲形狀 ） ； ? 性質 2： PM2+(n1) = PM2(n1)。 我們只學習多級混洗 — 交換網 。 各級編號是 n1， …… ， 0， 即按 降序排列 。 輸入 第 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， 路徑 如下圖 紅線 所示 。向不同方向進行的發(fā)送不能同時進行（具有這種能力的互連網不屬于現(xiàn)在的討論范圍）。 選播流量最少算法是最小成本生成樹算法，具體操作順序既可以是先短邊后長邊“長樹”，也可以是先長邊后短邊“砍樹” （ 教材 P426圖(c)）。 小圖 (a)指出廣播算法的時間是 4， 流量是 15。 習題： P446，題 3，題 10，題 26(1)～ (2)，題 27(3)。 先看一個簡單的例子 （ 下圖 ） ：已知 N=4， 維數 n=2， 源結點是 0， 目的結點是 1和 3。 不論對何種網絡，貪婪算法總是重復使用一個固定的操作規(guī)則：從當前擁有數據的結點出發(fā)，向需要數據的結點數最多的方向并行傳送一步，如此循環(huán)，直至傳遍所有需要數據的結點。下面舉幾個具體實例。 輸入 第 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ā)的時間開銷。 如果各級二元交換開關都處于 “ 直連 ” 狀態(tài) ， N個結點的數據通過網絡僅經過 n次混洗操作 ， 排列順序最終 恢復輸入狀態(tài) （ 混洗函數性質 2） ；如果各級二元交換開關都處于 “ 交換 ” 狀態(tài) ， 則 N個結點的數據在每次混洗之后緊接著一次交換 （ Cube0） ， 也就是地址碼的最低位取反 ， 最后 n位地址均被取反 。 二元交換開關的基本接通狀態(tài)有 “ 直連 ” 、 “ 交換 ” 、 “ 上播 ” 和 “ 下播 ” ， 在進行數據置換時只能使用前 2種 。 單級 PM2I網絡的直徑是 。 PM2I函數定義： PM2177。 n=3的混洗函數開關狀態(tài)如 P397圖 (a)所示 ， 其連接規(guī)律就像洗牌 。 (2) 單級 ICN ICN 0 0N1 N12022/5/31 計算機系統(tǒng)結構 18 該網絡由立方體 函數定義 ， 立方體 函數族有 n個成員 ， 分別是 Cube0， Cube1， …… ， Cuben1。 通用網 2022/5/31 計算機系統(tǒng)結構 16 特點：并行度高，造價昂貴。它的主要優(yōu)點在于采用模塊結構，因而可擴展性較好。 每個周期可以實現(xiàn) n個數據傳輸，與每個總線周期只傳一個數據相比，它的頻寬最高。 它是對稱的，結點度是常數 2。通常見到的處理單元之間的數據路由功能有 移數 、 混洗、交換、廣播 (一對全體 )、 選播 (多對多 )等。 (2) 結點度 與結點相連接的邊 (即鏈路或通道 )的數目稱為結點度。2022/5/31 計算機系統(tǒng)結構 1 本章內容：介紹用于多機并行計算的各種網絡 ， 它們統(tǒng)稱為互連網絡 ，縮寫符號是 ICN（ Interconnection Network） 。其結點數稱為網絡規(guī)模。 (6) 路由 在網絡通信中對路徑的選擇與指定。 2022/5/31 計算機系統(tǒng)結構 6 環(huán)可以單向工作，也可以雙向工作。正方形交叉開關網絡 (n＝ m)可以無阻塞地實現(xiàn) n!種置換。 多級網絡則是兩個極端之間的折衷。 示例： (4) 典型代表：以太網，令牌網（環(huán)或直線）。 互連函數族的組成必須使網絡成為 連通圖 。 ? 混洗函數 定義： 2j mod（ N1） ， 當 j N1 shuffle（ j） = N1 ， 當 j = N1 例如：當 N=8時 ， shuffle（ 0） = 0， shuffle（ 1） = 2， shuffle（ 7） = 7。 (n1)。 根據性質 2， 我們知道 單級 PM2I網絡實際上只能 實現(xiàn) 2n1種不同的置換 。 多級立方體網和多級混洗 — 交換網不使用單級互連網中的那種多路選擇開關， 而是用一種 2輸入 /2輸出的 二元交換開關 ， 以減少開關總數 。 在多級混洗 — 交換網絡中 ， 單獨一級 混洗拓撲線路可完成一次 數據混洗 （shuffle） ， 而單獨一列二元交換開關在處于 “ 交換 ” 狀態(tài)時可完成一次 交換操作 （ Cube0） 。 給定傳輸 011→ 010B， 二者異或結果為 001B， 路徑 如下圖 白線 所示 。 顯然對不同的網絡，適用的廣播與選播算法也不同。 實現(xiàn)第 3種目標的一種重要算法是貪婪算法（教材 P426圖 (b)）。Cube0 ～ Cuben1的使用順序對廣播算法的時間和流量沒有影響 ， 但對小圖 (b)的選播算法的時間和流量有影響 。