Omega網絡

Omega網絡是一種常用於並行計算架構的網絡配置。它是一個依賴於完美洗牌互聯算法的非直連拓撲。

連接架構

一個8x8的Omega網絡是一個多級互聯網絡，這意味着處理單元（英語：processing element，簡稱PE）是由多級交換機互聯的。如上圖，輸入和輸出標好了地址。每一級的輸出和下一級的輸入用一個完美洗牌系統（英語：Faro shuffle）連接起來，這意味着每個級間互聯都仿佛是一疊撲克牌劃分為數量相等的兩疊然後洗牌洗到一起，一張來自一組的牌疊在一張來自另一組的牌上。如果我們考慮用二進制表示PE，那麼每級的完美洗牌可以看作是一個循環邏輯左移位，地址中的每個位每次向左移一位，把最高位放置到最低位上。

在每一級上，相鄰的一對輸入被連接在一個簡單的互換單元上，這個單元可以選擇直通（英文：straight，也就是把輸入直接傳送到輸出）也可以選擇交叉（英文：crossed，也就是把上面的輸入放到下面輸出，把下面的輸入放到上面輸出）。對於 $N$ 個處理單元，一個Omega網絡的每一級有 $N/2$ 個交換機，共有 $\log _{2}N$ 級。這些交換機的配置決定了網絡在任意時間的通路的可用狀態，配置方法有兩種，分別為目的地標籤路（英語：destination-tag routing）由和XOR標籤路由（英語：XOR-tag routing）。

Omega網絡是高阻塞的，然而在一個自由網絡里對於任意一對輸入輸出總能找到一條路由。

目的地標籤路由

在目的地標籤路由中，交換機的配置完全按照要傳遞的消息的目的地決定。目的地地址的最高位被用來選擇第一級交換機的輸出口：如果最高位時0，那麼選擇上面的輸出口；如果最高位是1，那麼選擇下面的輸出口。第二高位被用來選擇第二級交換機的輸出口，依此類推直到到達最終的輸出。

例如，如果一條消息的目的地是PE 001，那麼交換機的配置為：上，上，下。如果一條消息的目的地是PE 101，那麼交換機的配置為：下，上，下。這些交換機的配置不考慮輸入的地址。

XOR標籤路由

在XOR標籤路由中，交換機的配置基於 (源PE地址) XOR (目的地PE地址)。這樣生成的一個XOR標籤包含的1的位置意味着地址在這一位上必須要被反轉，而0的位置意味着源PE地址和目的地PE地址在這一位是相同的。XOR標籤的最高位被用來設置第一級路由：如果它是0，則交換機選擇直通；如果它是1，則交換機選擇交叉。第二高位被用來選擇第二級交換機的輸出口，依此類推直到到達最終的輸出。

例如，如果PE 001想發消息給PE 010，那麼XOR標籤位011，交換機配置為：A2直通，B3交叉，C2交叉。

應用

在多處理器處理中，Omega網絡可以被用來連接CPU和共享內存從而降低CPU到內存的連接成為瓶頸的概率。

Omega網絡已被應用於Illinois Cedar Multiprocessor、IBM RP3和NYU Ultracomputer中^{[來源請求]}.

外部連結

用C語言實現的Omega網絡模擬（頁面存檔備份，存於互聯網檔案館）

參見

克洛斯網絡（英語：Clos network）
立方環（英語：Cube-connected cycles）
非阻塞最小生成交換（英語：Nonblocking minimal spanning switch）
榕樹交換（英語：Banyan switch）
Delta網絡
胖樹（英語：Fat tree）
交叉開關交換（英語：Crossbar switch）
網絡編碼

參考文獻

Lawrie, Duncan H. Access and Alignment of Data in an Array Processor. IEEE Transactions on Computers. December 1975, C–24 (12): 1145–55. doi:10.1109/T-C.1975.224157.