一種適應于二路胖樹的多目標編址方法

摘要：組播作為一種聚合操作其他聚合操作的基礎操作，對并行系統的性能有著重要的影響。本文提出了一種適應與二路胖樹的多目標編址方法：多區域位串編址。該方法可以縮短目標地址長度，并且可以實現路由器節點的快速解碼。

關鍵詞：二路胖樹；聚合通信；樹型組播；多目標編址

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

一、引言

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

樹型網絡拓撲對于樹型組播的實現提供了比將樹嵌入到直接網絡中更加自然的支持。二路胖樹結構不是一種可擴展的互連拓撲，但是在支持基于蟲孔交換的組播中表現出了良好的特性。本文根據二路胖樹的拓撲特性，提出了一種高效的多目標編址方法：多區域位串編址。

二、背景知識

2.路由算法

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

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

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

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

三、多區域位串編址

（一）性能指標

多目標編址是實現硬件組播的一種有效方法。多目標地址帶來網絡開銷和路由器解碼開銷，因此編址方式應希望達到以下目標：

1.長度盡量短；

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

3.編碼方式不假定交換節點知道自己在整個網絡拓撲中的位置；

4.系統擴展后編址方式能夠繼續使用。

（二）編址方式

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

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