一種適應(yīng)于二路胖樹的多目標(biāo)編址方法

摘要：組播作為一種聚合操作其他聚合操作的基礎(chǔ)操作，對并行系統(tǒng)的性能有著重要的影響。本文提出了一種適應(yīng)與二路胖樹的多目標(biāo)編址方法：多區(qū)域位串編址。該方法可以縮短目標(biāo)地址長度，并且可以實現(xiàn)路由器節(jié)點的快速解碼。

關(guān)鍵詞：二路胖樹；聚合通信；樹型組播；多目標(biāo)編址

中圖分類號：TP338 文獻標(biāo)識碼：A 文章編號：1674-7712 (2012) 16-0034-02

一、引言

組播作為一種聚合操作和其它聚合操作實現(xiàn)的基礎(chǔ)[0]，對并行系統(tǒng)的性能有著重要的影響。組播傳統(tǒng)的實現(xiàn)方法是使用軟件通過多個點到點的單消息通信完成，其硬件實現(xiàn)簡單，但是產(chǎn)生的網(wǎng)絡(luò)流量大，會造成頻繁的網(wǎng)絡(luò)擁塞，導(dǎo)致通信延遲的增加。文獻[0]中通過研究發(fā)現(xiàn)，通過Switch支持的樹型組播可以取得最高的性能，硬件實現(xiàn)的性能高于使用二項式樹結(jié)構(gòu)的軟件實現(xiàn)。

樹型網(wǎng)絡(luò)拓撲對于樹型組播的實現(xiàn)提供了比將樹嵌入到直接網(wǎng)絡(luò)中更加自然的支持。二路胖樹結(jié)構(gòu)不是一種可擴展的互連拓撲，但是在支持基于蟲孔交換的組播中表現(xiàn)出了良好的特性。本文根據(jù)二路胖樹的拓撲特性，提出了一種高效的多目標(biāo)編址方法：多區(qū)域位串編址。

二、背景知識

2.路由算法

文獻[3]中提出了蟲孔交換雙向多級互連網(wǎng)絡(luò)（BMIN）中的Turnaround路由算法，Turnaround路由算法可以用于基于蟲孔交換的二路胖樹中，并且不會產(chǎn)生死鎖。

二路胖樹的任意子樹的兩個根結(jié)點在邏輯上是等價的。信息從源結(jié)點發(fā)出后，上行的過程中可以任意的選擇一個當(dāng)前結(jié)點的父結(jié)點，下行過程中也可以任意選擇目標(biāo)結(jié)點所在子樹的兩個根結(jié)點中的任意一個。對于任意給定的子樹，只要一個根結(jié)點工作正常，則網(wǎng)絡(luò)仍然是連接的。

要將一個消息發(fā)送到目標(biāo)結(jié)點，消息頭中需要包含最近公共父結(jié)點與源結(jié)點的距離、目標(biāo)結(jié)點的編號信息和消息頭當(dāng)前所處的層號（初始值為）。消息上行過程中，每經(jīng)過一個Switch距離信息和當(dāng)前層號都減1，當(dāng)距離信息減到0時表示已經(jīng)到達了最近公共父結(jié)點，執(zhí)行turnaround操作。消息下行過程中每經(jīng)過一個Switch，當(dāng)前層號加1，若是層號為（，則Switch根據(jù)編號的判斷所要輸出的下行端口號，否則Switch根據(jù)編好信息的（為當(dāng)前層號）判斷目標(biāo)結(jié)點在當(dāng)前結(jié)點的左子樹還是右子樹。

由消息路由的上行過程和下行過程可以看出，Switch根據(jù)報文頭攜帶的信息對輸出路徑作出選擇，不需要記錄自身在網(wǎng)絡(luò)中的位置。

三、多區(qū)域位串編址

（一）性能指標(biāo)

多目標(biāo)編址是實現(xiàn)硬件組播的一種有效方法。多目標(biāo)地址帶來網(wǎng)絡(luò)開銷和路由器解碼開銷，因此編址方式應(yīng)希望達到以下目標(biāo)：

1.長度盡量短；

2.利于路由信息的計算；

3.編碼方式不假定交換節(jié)點知道自己在整個網(wǎng)絡(luò)拓撲中的位置；

4.系統(tǒng)擴展后編址方式能夠繼續(xù)使用。

（二）編址方式

多區(qū)域位串編址適合于幾個相鄰區(qū)域的節(jié)點組。二路胖樹中可以通過最近公共父節(jié)點表示區(qū)域，區(qū)域中位串的長度根據(jù)表示區(qū)域的最近公共父節(jié)點和處理節(jié)點之間的距離來判定。

對于樹型結(jié)構(gòu)存儲方式，本文設(shè)計了一種帶度數(shù)的深度優(yōu)先的先根次序表示法。樹的先根次序表示如1(a)所示。帶度數(shù)表示的節(jié)點結(jié)構(gòu)如1(b)所示。其中Info是該節(jié)點相對于父節(jié)點的位置，Degree是當(dāng)前節(jié)點的子節(jié)點數(shù)目。