摘要：并行處理機(jī)MPP由于其良好的可擴(kuò)展性和聯(lián)高性能價(jià)格比，已成為實(shí)現(xiàn)超高性能計(jì)算的重要支持工具。MPP系統(tǒng)性能的發(fā)揮極大程度上依賴于互連網(wǎng)絡(luò)的通信性能，對(duì)于并行計(jì)算來(lái)說(shuō)，尋徑技術(shù)是至關(guān)重要的。互連網(wǎng)絡(luò)中采用的尋徑算法決定了消息在網(wǎng)絡(luò)中如何選取路徑，其性能對(duì)網(wǎng)絡(luò)效率的發(fā)揮起著重要作用。該文以多機(jī)系統(tǒng)中的各種消息尋徑方式概述為背景，著重討論wormhole消息尋徑方式。
　　關(guān)鍵詞：直連網(wǎng)絡(luò)；wormhole尋徑；死鎖的避免和恢復(fù)；虛擬通道
　　中圖分類號(hào)：TP393文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)03-0558-02
　　對(duì)于大規(guī)模問(wèn)題求解時(shí)，要求很高的計(jì)算求解的速度，電子技術(shù)的發(fā)展曾使計(jì)算機(jī)的運(yùn)算速度獲得驚人的提高，但現(xiàn)在已接近電子傳輸?shù)奈锢順O限，傳統(tǒng)的大型機(jī)和向量巨型機(jī)由于自身物理因素和工藝水平的限制，在性能上很難進(jìn)一步達(dá)到要求。因此，傳統(tǒng)計(jì)算機(jī)的串行結(jié)構(gòu)是阻礙速度提高的關(guān)鍵因素，并行處理技術(shù)就成了進(jìn)一步提高性能的主要途徑。
　　并行處理技術(shù)是并行計(jì)算機(jī)的關(guān)健技術(shù)，它涉及的范圍很廣，包括并行結(jié)構(gòu)、并行算法、并行操作系統(tǒng)、并行語(yǔ)言及其編譯系統(tǒng)等，其中并行結(jié)構(gòu)是關(guān)鍵因素。
　　計(jì)算機(jī)根據(jù)指令流和數(shù)據(jù)流是單一的還是多個(gè)的進(jìn)行分類，并行處理機(jī)可以分為SIMD（單指令流多數(shù)據(jù)流）和MIMD（多指令流多數(shù)據(jù)流）兩大類。SIMD比較專用，世界上裝用的數(shù)量并不多，MIMD則應(yīng)用廣泛，發(fā)展出多種類型。MIMD可進(jìn)一步劃分為以下五種類型：并行向量處理機(jī)（PVP）、對(duì)稱多處理機(jī)（SMP）、大規(guī)模并行處理機(jī)（MPP）、分布共享存儲(chǔ)器（DSM）多處理機(jī)、機(jī)群系統(tǒng)（COW）。
　　本文討論當(dāng)今較為常用的MPP計(jì)算機(jī)組成的關(guān)鍵部分——互連網(wǎng)絡(luò)的結(jié)構(gòu)，并對(duì)wormhole尋徑技術(shù)展開分析和討論。
　　 1基本術(shù)語(yǔ)與性能指標(biāo)
　　1.1消息、包和片
　　消息（Message）是在多計(jì)算機(jī)系統(tǒng)的處理接點(diǎn)之間傳遞包含數(shù)據(jù)和同步消息的信息包。它是一種邏輯單位，可由任意數(shù)量的包構(gòu)成。包（Packet）的長(zhǎng)度隨協(xié)議不同而不同，它是信息傳送的最小單位，64-512位。片（Flit）的長(zhǎng)度固定，一般為8位。1.2互連網(wǎng)絡(luò)技術(shù)指標(biāo)
　　互連網(wǎng)絡(luò)用來(lái)在多計(jì)算機(jī)系統(tǒng)的處理結(jié)點(diǎn)之間傳遞消息?；ミB網(wǎng)絡(luò)性能的兩個(gè)重要指標(biāo)是傳輸時(shí)延（Transmission Latency）和吞吐量（Throughput）。吞吐量指系統(tǒng)在每秒內(nèi)發(fā)送或接收到的消息的字節(jié)數(shù)，它取決于節(jié)點(diǎn)的體系結(jié)構(gòu)和通信機(jī)制。傳輸時(shí)延主要有三個(gè)部分組成：
　　一個(gè)消息的傳輸時(shí)延：從它在源結(jié)點(diǎn)進(jìn)行發(fā)送初始化到它在目的結(jié)點(diǎn)完整的被接收所耗費(fèi)的時(shí)間。一個(gè)網(wǎng)絡(luò)的傳輸時(shí)延：在一定條件下發(fā)送消息的平均時(shí)延。
　　網(wǎng)絡(luò)的吞吐量：?jiǎn)挝粫r(shí)間內(nèi)網(wǎng)絡(luò)所能傳輸?shù)南?shù)目或長(zhǎng)度。
　　
　　圖1 wormhole尋徑
　　 2 Wormhole尋徑（Wormhole Routing）
　　首先把一個(gè)消息分成許多片，消息的頭片包含了這個(gè)消息的所有尋徑信息，尾片是一個(gè)其最后包含了消息結(jié)束符的片，中間的片均為數(shù)據(jù)片。片是最小信息單位。每個(gè)結(jié)點(diǎn)上只需要緩沖一個(gè)片就能滿足要求。
　　Wormhole尋徑方式如圖1所示。
　　當(dāng)消息的頭片到達(dá)一個(gè)結(jié)點(diǎn)A的尋徑器后，尋徑器根據(jù)頭片的尋徑信息立即做出尋徑選擇：如果所選擇的通道空閑而且所選擇的結(jié)點(diǎn)B的通信緩沖器可用，那么這個(gè)頭片就不必等待，直接通過(guò)結(jié)點(diǎn)A傳向下一個(gè)結(jié)點(diǎn)B；隨后的其它片跟著相應(yīng)的向前“蠕動(dòng)”一步。當(dāng)消息的尾片向前“蠕動(dòng)”一步后，它剛才所占用的結(jié)點(diǎn)就被放棄了。如果所選擇的通道非空閑或者所選擇的結(jié)點(diǎn)的通信緩沖器非可用，那么這個(gè)頭片就必須在此結(jié)點(diǎn)的通信緩沖器中等待，直到上述兩者都可用為止；其它片也在原來(lái)的結(jié)點(diǎn)上等待。此時(shí)，被阻塞的消息不從網(wǎng)絡(luò)中移去，片不放棄它所占有的結(jié)點(diǎn)和通道。這是Wormhole技術(shù)和其它流控制技術(shù)都不同的地方。
　　Wormhole方式從管道消息流的概念中所繼承的。它的優(yōu)點(diǎn)是每個(gè)結(jié)點(diǎn)的緩沖器的需求量小，易于用VLSI實(shí)現(xiàn)；較低的網(wǎng)絡(luò)傳輸延遲；所有的片以流水方式向前傳送。而在存儲(chǔ)轉(zhuǎn)發(fā)中，消息是整個(gè)的從一個(gè)結(jié)點(diǎn)“跳”向另一個(gè)結(jié)點(diǎn)，通道的使用是串行的。Wormhole與線路開關(guān)的網(wǎng)絡(luò)傳輸延遲正比于消息包的長(zhǎng)度，傳輸距離對(duì)它的影響很小（消息包較長(zhǎng)時(shí)的情況）。通道共享性好、利用率高。對(duì)通道的預(yù)約和釋放是結(jié)合在一起的一個(gè)完整的過(guò)程：占有一段新的通道后將立即放棄用過(guò)的一段舊通道。易于實(shí)現(xiàn)Multicast和Broadcast。允許尋徑器復(fù)制消息包的片并把它們從多個(gè)輸出通道輸出。
　　由于wormhole技術(shù)淡化了路徑長(zhǎng)度對(duì)網(wǎng)絡(luò)性能的負(fù)面影響，使人們有希望采用簡(jiǎn)單、規(guī)整的低維網(wǎng)格結(jié)構(gòu)來(lái)實(shí)現(xiàn)高性能的大規(guī)模并行處理（MPP）互連網(wǎng)絡(luò)。所以，wormhole技術(shù)已被廣泛用于MPP互連網(wǎng)絡(luò)中，并收到了較好的效果。
　　 3虛擬通道與死鎖
　　對(duì)于wormhole尋徑方式最重要的問(wèn)題在于防止消息傳遞的阻塞和死鎖。一個(gè)消息有可能在一個(gè)向相反方向傳遞的消息后阻塞，如圖2所示。
　　
　　圖2 Wormhole尋徑的阻塞
　　圖中，源2與目的2兩各節(jié)點(diǎn)之間首先開始傳輸片，這樣就阻塞了源1到目的1的片的傳送。在這種情況下，通常使用虛擬通道來(lái)解決阻塞的問(wèn)題。一個(gè)虛擬通道是一個(gè)物理通道的邏輯抽象概念，與一個(gè)物理通道關(guān)聯(lián)的所有虛擬通道具有不同的片緩存，并且它們時(shí)分復(fù)用該物理通道。與此類似，每個(gè)與虛擬通道相關(guān)聯(lián)的緩存實(shí)際上是該物理通道的緩存的一部分，如圖3所示。
　　
　　圖3虛通道示意圖
　　在圖3所示的虛通道示意圖中，兩個(gè)虛通道共用一個(gè)物理通道，實(shí)現(xiàn)了物理通道的時(shí)分復(fù)用，從而解決了阻塞的問(wèn)題。在虛擬通道中，一條物理通道在邏輯上分成兩個(gè)傳輸方向相反的通道，每一個(gè)虛擬通道為單向且有自己的緩存區(qū)；一條物理通道上的虛擬通道邏輯上被劃分成多個(gè)虛擬通道，這些虛擬通道共享這條物理通道發(fā)送或接收信息。由于虛擬通道能夠有效的減小沖突和阻塞，因此為增強(qiáng)性能和設(shè)計(jì)非死鎖的尋徑算法方面，在多計(jì)算機(jī)系統(tǒng)尤其是MPP中使用的非常頻繁。
　　綜上所述，wormhole技術(shù)的通道具有共享性好，靈活的連接方式，較高的吞吐率等優(yōu)點(diǎn)。在wormhole技術(shù)中，對(duì)通道的預(yù)約和釋放是結(jié)合在一起的一個(gè)完整過(guò)程。當(dāng)占有一段新的通道后，將立即釋放用過(guò)的一段舊通道，充分考慮多個(gè)數(shù)據(jù)包對(duì)通道資源的共享。數(shù)據(jù)包經(jīng)過(guò)的每一段通道既不在數(shù)據(jù)包到達(dá)之前預(yù)約，也不在數(shù)據(jù)包通過(guò)之后繼續(xù)占有，僅僅在數(shù)據(jù)包到達(dá)時(shí)才被使用。對(duì)于某一段通道來(lái)講，在數(shù)據(jù)包到達(dá)之前它不必空閑等待，當(dāng)數(shù)據(jù)包經(jīng)過(guò)之后它立即可以為其它數(shù)據(jù)包所利用。
　　 4避免死鎖的wormhole尋徑方式
　　4.1維序?qū)?br/>　　維數(shù)排序路由是一種確定的wormhole尋徑方式，它規(guī)定了消息傳遞時(shí)所選擇的路徑的維數(shù)即方向的順序。這種網(wǎng)絡(luò)的維數(shù)按照時(shí)限定好的單調(diào)的順序排序。消息首先在最高維或最低維進(jìn)行置換，直到它在這一維的方向上到目的節(jié)點(diǎn)的距離為0，然后消息再在一個(gè)相鄰的維上進(jìn)行交換，重復(fù)這個(gè)過(guò)程，直到該消息抵達(dá)目的節(jié)點(diǎn)。所有的消息不會(huì)反向傳送，不會(huì)形成循環(huán)，因此就保證了死鎖的避免。
　　維數(shù)排序路由將最短路徑分布在整個(gè)網(wǎng)絡(luò)中，這樣同時(shí)均衡分布了網(wǎng)絡(luò)的通信量。對(duì)于不對(duì)稱工作量的網(wǎng)絡(luò)來(lái)說(shuō)，有些通道就會(huì)比其他通道繁忙得多，而由于這種算法將路徑限制在一個(gè)固定的通道上，即使在沖突或網(wǎng)絡(luò)發(fā)生錯(cuò)誤的情況下也不能夠分散流量。對(duì)于所有的確定的wormhole尋徑方式中，都存在這個(gè)問(wèn)題。因此，這是確定的wormhole尋徑方式的局限性。
　　（下轉(zhuǎn)第591頁(yè)）
　　4.2轉(zhuǎn)向模型（Turn Model）
　　轉(zhuǎn)向模型開創(chuàng)了避免死鎖的自適應(yīng)算法新方向。它要求通道獨(dú)立圖中沒(méi)有自環(huán)。轉(zhuǎn)向模型針對(duì)無(wú)附加通道的網(wǎng)絡(luò)提供了一套發(fā)展自適應(yīng)尋徑算法的系統(tǒng)方法，無(wú)論是完全自適應(yīng)還是部分自適應(yīng)。在這樣的情況下死鎖的發(fā)生是因?yàn)榘膶睫D(zhuǎn)向形成了自環(huán)。
　　參考文獻(xiàn)：
　　[1] Duat