基於omega網**蠕蟲網的技術動態
---基於無阻塞omega網路的蠕蟲網尋徑方式
摘要omega網路由於自身結構的特點，無法實現任意置換的同時連通，在某些結點同時互聯時會出現阻塞。對於該問題，一般的解決方法是將置換分批多次通過或增加器件，但這些方法都是以通訊頻寬的減小或硬體成本的增加為代價的，無法體現omega網路自身的優越性。同時並行處理機由於其良好的可擴充套件性和聯高效能**比，已成為實現超高效能計算的重要支援工具。
並行處理機系統效能的發揮極大程度上依賴於互連網路的通訊效能，對於平行計算來說，尋徑技術是至關重要的。互連網路中採用的尋徑演算法決定了訊息在網路中如何選取路徑，其效能對網路效率的發揮起著重要作用。
本文首先分析了現有幾種主要的omega組合網路以及對應的尋徑演算法，然後提出了omega網路的無阻塞方案：通過對簡單omega網路進行改進，只增加了少量的部件和連線。該文還以多機系統中的各種訊息尋徑方式概述為背景，著重討論wormhole 訊息尋徑方式。
關鍵詞：omega網阻塞機間通訊蠕蟲尋徑方法及其優勢
1 無阻塞omega網路
omega網路是多級網際網路絡的一種。通常的多級網路是動態連線網路，即不採用固定連線，而是沿著連線通路使用開關與仲裁器來提供動態連線特性。簡單omega網路的構成單元是2×2 開關。
乙個n輸入的omega網路通常需要log2n級，每級n/2個，共n*log2 n/2個2×2開關。網路左右兩側各有n個結點，分別用二進位制編號為xn-1xn-2x0。其互聯模式為兩組物件的均勻洗牌連線（xn-1xn-2x0 → xn-2xn-3x0 xn-1）。
1.1 omega網路的阻塞特性
對於乙個具體的置換連線，簡單omega網路由固定的演算法來計算各開關如何設定。對於兩個置換（xn-1xn-2x0 → yn-1yn-2y0）和（pn-1pn-2p0 → qn-1qn-2q0），若在開關設定的第i步出現xn-1-ixn-2-ix0 yn-1yn-2yn+1-i＝pn-1-ipn-2-ip0 qn-1qn-2qn+1-i，而yn-i≠qn-i，即同一開關上兩個輸入請求的是同乙個輸出，則這兩個輸出被阻塞。n輸入的omega網路一次通過可以實現nn/2個置換，但總共有n!
個置換，無法保證每次置換都被完全通過。
1.2 以器件為代價的無阻塞尋徑演算法
對於阻塞問題，一種解決方法是把所有的置換分為若干批，依次通過。一般來說，規模為n=2*k的omega網路實現非阻塞連線最多需要通過的次數為k次，但是這樣有效通訊頻帶寬將降低為原來的1/k。另一種方法是採用多一倍的器件，配合較複雜的尋徑演算法，可以一次通過任意的n對n的置換，如benes網路，所對應的演算法稱為迴圈演算法，它的計算複雜度為o(n*logn)。
wu和feng在2023年提出了混洗——交換類網路的通用結構和對應演算法[3]，並給出一種用兩個頭對頭的omega網路互聯起來組成的組合網路（稱為omega-1×omega 網路) ，指出了它於benes網路的拓撲等價性。但是這種結構的尋徑演算法是以benes網路的迴圈演算法為基礎的，比迴圈演算法還多出一些計算。在此基礎上，feng於2023年提出了類似的一種結構[1]，用兩個omega網路頭對尾順序連線起來(即omega×omega網路)，並給出了完全不同於迴圈演算法的一種尋徑演算法，實現了複雜度為o(n)的計算量級。
結點數為n的omega×omega網路中，對該網路兩邊的輸入、輸出結點依次編號為：0, 1, 2, , n-1，對各級開關的級別編號為：1, 2, ,2k (這裡n=2k )。
通過對前k級開關的位置進行逆位序置換，feng證明了該結構與omega-1×omega 網路的拓撲等價性，並指出由此構成的omega-1×omega 網路之間的連線是蝶式或變形蝶式的。
對於omega-1×omega 網路，feng提出了一種新的尋徑演算法[1]，對於每對置換，從網路中間的第k級開關和第k+1級開關開始，找出各自在這兩級開關中所對應的位置，分別向兩邊按照簡單omega的尋徑方法得出一條完整的路徑。相對於計算複雜度為o(n*logn)的benes類網路的迴圈演算法，feng演算法具有明顯的優越性，其總體計算時間為2n+logn-1，計算開銷大大減少。不可避免的是，該演算法仍然是以兩倍的器件量為代價來取得網路的一次性置換連通。
2. wormhole尋徑（wormhole routing）
蠕蟲網路機間採用小容量緩衝儲存器，實現訊息分組尋徑儲存**之用。在蠕蟲網路中，將訊息分組又分割成一系列更小的小組，同一分組中所有小組以非同步流水方式按序不間斷地傳送，同一分組中的所有小組，只有頭部的小組知道其所在整個分組傳送的目的地，用硬體方式進行傳送的應答。各個分組允許交叉傳送，但不同分組中的各個小組不能互相混在一起傳送，利用虛擬通道思想，使存在於傳送和接收結點之間的一條物理通道能被多個虛擬通道分時共享。
它首先把乙個訊息分成許多片，訊息的頭片包含了這個訊息的所有尋徑資訊，尾片是乙個其最後包含了訊息結束符的片，中間的片均為資料片。片是最小資訊單位。每個結點上只需要緩衝乙個片就能滿足要求。
wormhole尋徑方式如圖1所示。
當訊息的頭片到達乙個結點a的尋徑器後，尋徑器根據頭片的尋徑資訊立即做出尋徑選擇：如果所選擇的通道空閒而且所選擇的結點b的通訊緩衝器可用，那麼這個頭片就不必等待，直接通過結點a傳向下乙個結點b；隨後的其它片跟著相應的向前「蠕動」一步。當訊息的尾片向前「蠕動」一步後，它剛才所占用的結點就被放棄了。
如果所選擇的通道非空閒或者所選擇的結點的通訊緩衝器非可用，那麼這個頭片就必須在此結點的通訊緩衝器中等待，直到上述兩者都可用為止；其它片也在原來的結點上等待。此時，被阻塞的訊息不從網路中移去，片不放棄它所占有的結點和通道。這是wormhole技術和其它流控制技術都不同的地方。
wormhole方式從管道訊息流的概念中所繼承的。它的優點是每個結點的緩衝器的需求量小，易於用vlsi實現；較低的網路傳輸延遲；所有的片以流水方式向前傳送。而在儲存**中，訊息是整個的從乙個結點「跳」向另乙個結點，通道的使用是序列的。
wormhole與線路開關的網路傳輸延遲正比於訊息包的長度，傳輸距離對它的影響很小（訊息包較長時的情況）。通道共享性好、利用率高。對通道的預約和釋放是結合在一起的乙個完整的過程：
占有一段新的通道後將立即放棄用過的一段舊通道。易於實現multicast和broadcast。允許尋徑器複製訊息包的片並把它們從多個輸出通道輸出。
由於wormhole技術淡化了路徑長度對網路效能的負面影響，使人們有希望採用簡單、規整的低維網格結構來實現高效能的大規模並行處理（mpp）互連網路。所以，wormhole技術已被廣泛用於mpp互連網路中，並收到了較好的效果。
與其它尋徑技術相比, w or m h ol e 尋徑技術有其獨特的優點:
1. 它對每個結點上的緩衝器的需求量小, 易於v lsi 實現。資訊包在網路中一步步向前「 蠕動」 , 占用了一串結點。
資訊包的各個微片分布在各個結點上, 減少了對每個結點上的緩衝器的需求。而在儲存**和v ir t u a l c u t 一t h r o u g h 技術中資訊包整個放在乙個結點上, 緩衝器的需求量大且資訊包的大小受到緩衝器大小的限制, 在w or m hol e 技術中不存在這個間題。
2. 它具有較低的網路傳輸延遲。
資訊包的所有微片以流水的方式向前傳送, 充分發揮了時間並行性, 提高了傳輸效率。而在儲存**和v i r t u a l e u t 一t hr o u g h技術中, 資訊包整個地從乙個結點「跳」 向另乙個結點.通道的使用是序列的, 所以它們的傳輸延遲正比於訊息在網路中傳輸的距離。
w o rm ho le 技術和e i r v u i t , 開關技術的網路傳輸延遲正比於資訊包的長度, 傳輸距離對它的影響很小。
3. 它的通道共享性好通道利用率高。
在技術中對通道的預約和釋放是結合在一起的乙個完整的過程,占有一段新的通道後將立即放棄用過的一段舊通道,充分考慮了多個資訊對通道資源的共享。對資訊包經過的每一段通道既不在資訊包到達之前預約也不在資訊包經過之後繼續占有, 僅當資訊包到達時才被使用。對某一段通道在資訊包到達之前它不必空閒等待; 在資訊包經過之後它立即可以為其它資訊所利用。
而在電路開關技術中對通道的預約和釋放是完全分離的兩個步驟—在資訊包傳送之前一次性預約所有將用到的通道, 直到資訊包傳送之後才全部釋放。這樣導致個段通道都存在被空閒占用的時間, 降低了通道的使用效率。同時也造成不同的資訊包之間無法共享物理通道。
在virtualcut-through 技術中也有同樣的間題。
4. 它易於實現multieast 和broadeast
wormhole技術允許路由選擇器複製資訊包的微片並把它們從路由選擇器的多個輸出通道輸出, 以實現m ul t ica s t 和b r o a d e a s t 的功能。
近兩年來, 出現了許多利用w or m h ol e 尋徑技術發展起來的高效可靠的尋徑演算法模型。儘管w or m h ol e 尋徑技術以硬體支援的動態流控制技術和簡單的尋徑演算法, 使互連網路在通訊延時和吞吐量兩方面都取得了十足的進展, 但仍不能滿足並行處理系統對互連通訊技術的日益增長的無止境要求。在今後很長一段時間內, 互連技術仍將是並行處理系統研究中的乙個十分活躍的領域。
計算機系統結構試題
姓名學號 一 名詞解釋 每題3分，共15分 1.系列機 3.2 1cache經驗規則 2.強制性失效 4.指令級並行 二 試從目的 技術途徑 組成 分工方式 工作方式等5個方面對同構型多處理機和異構型多處理機做一比較 列表 10分 三 有哪幾種向量處理方式？它們對向量處理機的結構要求有何不同？6分 ...
計算機系統結構複習總結
1 計算機系統結構概念 1.1 計算機系統結構 程式設計師所看到的計算機的基本屬性，即概念性結構與功能特性。注意 對不同層次上的程式設計師來說，由於使用的程式語言不同，可能看到的概念性結構和功能特性會有所不同。1.2 計算機系統的層次結構 現代計算機是一種包括機器硬體 指令系統 系統軟體 應用程式和...
計算機系統結構試題試題
姓名學號 一 填空題 20分，每空2分 1 在處理機中，若指令序列完成的順序總是與它們開始執行的順序保持一致，則只可能出現 相關，否則就有可能出現和 相關。2 設計i o系統的三個標準是和 3 單機和多機並行性發展的技術途徑有和 二 簡答題 20分，每題10分 1 在進行計算機系統設計時，乙個設計者...