一種基于氣泡流控的改進多播路由算法*

婁 輝，肖燦文，董德尊, 龐征斌，李存祿

(國防科學技術大學計算機學院，湖南 長沙 410073)

1 引言

隨著人們對芯片計算性能需求的不斷提升，單純依靠提高芯片時鐘頻率來提高整體計算性能的方法已經很難滿足性能的需要，因此當前片上系統大多通過增加芯片上集成的處理器核的數目來進一步提升性能。片上網絡通過通信鏈路連接多個處理器核，這種方式與基于總線的互連相比，能夠實現更低的通信延遲、更高的吞吐量和更低的能耗。片上網絡作為不同處理器核之間的通信部件，其性能對片上系統的整體性能會產生很大影響。當前片上多處理器系統研究大多致力于提升單播通信的性能，然而許多并行應用和程序模型都需要支持多播。例如，在基于目錄的 Cache 一致性[1]協議中，大量依賴多播和廣播通信特性去維持請求間的順序，并通過廣播作廢不同Cache節點上的共享數據塊；而在基于令牌的 Cache 一致性協議[2]中也需要使用多播收集令牌。在不同的Cache 一致性協議通信模型中，多播通信占網絡總通信量的3.1%～12.4%[3]。因此，設計一種針對多播通信的高效的路由算法將會有效提升片上網絡的通信性能。表1列出了不同協議下多播通信占系統總通信量的比例。從表1可以看出，多播通信在網絡中所占的比例很大，這些聚合通信對多核系統的性能會產生顯著的影響，即使網絡中注入很少的多播包，網絡吞吐量也會明顯下降。為了避免這些重要的聚合通信成為整個片上系統性能提升的瓶頸，片上網絡必須支持多播通信這種重要的通信模式。路由算法決定了網絡中報文的通信形式，同時不同的路由算法對網絡中帶寬的利用、平均報文時延、飽和吞吐率以及能耗等都有很大的影響。對于多播也是一樣，不同的多播路由算法也會顯著影響網絡資源的利用效率。因此，一個高效的多播路由算法對多處理器系統來說至關重要。

Table 1 Proportion of multicast in the network

多播和廣播是一個源節點向一個目的節點集合發送同樣的數據信息的通信模型。多播報文通信的主要目標是為多播報文選擇一條最優路徑，使得報文在該路徑上傳播所占用的通道帶寬盡可能少，并使該報文的傳播延遲盡可能短。報文死鎖會明顯降低多播通信的性能，因此在多播路由設計中應保證報文傳播不會產生死鎖。多播通信對網絡的整體性能產生很大影響，因此當前的許多工作對如何設計高效的多播路由算法以提高片上網絡整體性能進行了研究。

當前已有很多針對多播通信的路由算法，例如，基于樹的多播路由算法[4]保證多播報文盡可能地沿著共同路徑傳輸，當需要發往不同方向的目標節點時進行報文復制，從而使多播報文以樹的形式發送到所有目標節點。該方法的一個明顯缺陷是容易產生擁塞，當傳播樹中有一個分支擁塞時，其它的分支也會被阻塞，擁塞的產生使得該方法的網絡吞吐率很低。基于路徑的多播路由算法限制多播報文沿著同一路徑依次通過各個目標節點，報文首先到達離源節點最近的目的節點，然后到達較遠的節點，并在報文到達目的節點時進行復制。這種方法往往使得報文傳播的路徑很長，從而增加了報文的傳輸延遲。由于片上網絡在面積、能耗和性能等方面都有嚴格的限制，因此這些方法不適合在片上網絡使用。虛電路樹多播路由VCTM(Virtual Circuit Tree Multicasting)[3]是片上網絡中一種重要的多播路由算法。該算法只需要添加較少的存儲空間就能夠有效地支持多播與廣播。但是，該算法有三個缺點：(1)為維持多播信息需要額外的存儲空間，從而增加了芯片的面積；(2)傳播過程中需要多播包的建立信號，從而增加了網絡中的延時；(3)即使是同樣的目的節點集，如果多播源節點改變，VCTM也必須重新建立多播樹進行多播通信。這些缺陷使得VCTM不能很好地運用到大規模網絡中。支持廣播的邏輯劃分路由BLBDR(Broadcast Logic-Based Distributed Routing)[5]通過劃分工作區域來有效隔離有缺陷的區域，同時關閉不需要的網絡區域，從而有效降低能耗。該方法確定了NOC中層虛擬化的概念，對網絡的不同區域進行隔離通信。但是，如果目的節點集合散落到不同的網絡部分，則該算法的性能會明顯降低，這是因為該方法很難確定一個能夠覆蓋所有的目的節點的區域，因此該調度算法在片上網絡多播通信中并不適用。遞歸劃分多播路由算法RPM (Recursive Partitioning Multicast)[6]由于存在緩存資源利用的不均衡，其性能也受到了相應影響，本文后續部分將進行詳細分析。均衡自適應多播路由算法BAM (Balanced Adaptive Multicast)[7]采用的死鎖避免方法，影響了網絡通道資源的利用率，本文就是針對RPM和BAM算法的不足提出了新的基于氣泡流控的多播路由算法。

本文的主要貢獻總結如下：

(1)改進了多播路由算法(RPM和BAM)的死鎖避免方法。通過加入氣泡(即空閑虛通道)的方法來避免死鎖，該方法釋放了為了防止死鎖而預留的網絡緩存資源，從而更有效地利用了網絡的緩沖資源，提升了網絡的性能。

(2)對該方法的無死鎖性進行了論述。

(3)評估了不同流量模型下改進的RPM和BAM的性能，同時評估了改進的BAM在不同網絡資源下的敏感性及可擴展性。

本文其余部分組織如下：第2節介紹了我們的多播路由算法的實現過程；第3節介紹路由器流水線和微體系結構；第4節評估了不同路由算法的性能，并與我們提出的方法進行了比較，同時總結了模擬結果；最后是本文的結論。

2 多播路由算法

本文針對RPM和BAM兩種多播路由算法存在的不足，提出一種新的多播路由算法。RPM能夠根據包當前所在的地址，將網絡劃分成八個區域。根據報文目的節點在這八個區域的位置，采用一系列的優先級規則計算出報文去每個區域的優先的輸出端口。RPM盡可能多地使報文沿著同一條路徑傳輸來減小網絡帶寬的使用，之后進行復制操作，將復制的包傳輸到各個目的節點。但是，為了防止多播路由的死鎖，RPM采用了兩個虛擬網絡VN0和VN1，VN0只傳輸向上的報文，VN1只傳輸向下的報文。這種死鎖避免的方法使水平方向的緩存成為了性能的瓶頸，它被VN0和VN1同時使用而垂直方向的只有一個方向使用。這種方法由于不同維度的緩存資源的使用不均衡影響了它的性能。BAM也是根據包當前所在的地址，將網絡劃分成八個區域，但它根據各輸出端口的擁塞程度選擇到達目的區域具有較低擁塞程度的輸出端口，從而高效地使用鏈路帶寬。BAM為了防止死鎖，將Duato 的單播死鎖避免理論[8]運用到多播路由算法上，將網絡中的虛通道劃分為適應性虛通道和逃逸虛通道。一旦多播包進入逃逸虛通道，后續路由算法就按維序路由進行報文復制。這種死鎖避免的方法，當網絡要發生死鎖的時候才用逃逸虛通道，所以網絡中的逃逸虛通道在網絡使用的概率比較小。它使網絡的虛通道的資源沒有充分利用，造成資源浪費，導致網絡性能不能充分發揮。當多播報文進入逃逸虛通道時報文只能夠進行維序路由。這種路由方法是為了保證無死鎖而犧牲了網絡中的帶寬，從而使帶寬不能充分利用，網絡延時增大。由于在逃逸虛網絡中向北和向南傳輸的報文不能夠轉變方向，造成了網絡不同維度間的資源的不均衡。

基于對RPM和BAM的觀察與分析，本文提出了一種新的多播死鎖避免方法。這種死鎖避免方法是在網絡的垂直方向注入氣泡(Bubble)，取消RPM和BAM的兩個網絡。以BAM為例簡述新死鎖避免方法，改進BAM簡稱BAM-B。

BAM-B是在BAM基礎上提出來的，首先敘述BAM的均衡自適應多播路由算法。BAM首先根據報文的位置將網絡劃分成八個區域，分別為 0、1、2、3、4、5、6、7，如圖1所示。位于 1、3、5 和 7 中的目標節點只有一個輸出端口到達, 因此多播報文目標節點中有處于 1、3、5 或 7的，則對應的北、西、南或東輸出端口一定會被選擇使用，這些端口被稱作必須輸出端口。而處于區域0、2、4、6的多播報文目標節點，源節點有兩個方向輸出端口可以到達它們。網絡中報文傳輸遵守如下規則：(1)如果目標節點只有一個必須端口，則沿著必須端口傳輸數據。(2)如果沒有必須輸出端口或有兩個必須輸出端口，則報文沿最低擁塞的輸出端口方向傳輸。以上是BAM與BAM-B相同的地方，下面是本文提出的改進算法不同的地方。

Figure 1 Network regional division schematic diagram圖1 網絡區域劃分示意圖

不同的主要地方在于對死鎖的處理方式。不失一般性，考慮多播源節點位于如圖1所示的位置，考慮多播包向北輸出端口傳輸，且目標節點集都在北向這一維的不轉維的情況，即目的節點集中不帶有0和2區域的節點，則不需要加入氣泡(即空虛通道)，虛通道全部分配給包進行虛通道VC(Virtual Channel)分配。當去目標節點存在一次路由轉維時，此例子中即目的節點集中存在0或2區域的目的節點，則將VC中加入氣泡，即留一個切片緩存區，其它的全部分配給包進行VC分配。

死鎖發生的情況如圖2所示，A包占據通道U請求通道V，B包占據通道V請求通道W,C包占據通道W請求通道X，D包占據通道X請求通道U。

Figure 2 Packet deadlock situation圖2 報文發生死鎖情況

文獻[9]證明了在Mesh網絡中通過注入氣泡來提高單播完全自適應路由網絡性能的方法是無死鎖的。但是，它沒有涉及網絡中存在多播的情況。由于Cache 一致性協議的多播包大量用于傳輸網絡中的控制信息，同時片上有大量的連線資源，所以可以將這些信息用單切片的多播包傳輸。在網絡中傳輸的單切片的多播包，各個復制的切片相互獨立，類似于單播包。

所以新的多播路由算法與網絡中注入氣泡的單播完全自適應路由算法有類似的性質且都是無死鎖的。下面將描述新的多播路由算法是無死鎖的：

(1)如果X中的虛通道中所有的報文都請求U，由改進新的路由算法知X通道中必然存在一個空閑VC。W中請求X虛通道的報文必有一個能夠請求成功，則W中的報文可以繼續向X通道傳輸。因此，W中將有空閑VC，V可以請求W，則這種情況下存在一個報文可以移動。

(2)如果X中的所有VC都被占用，由改進的新路由算法知X通道中必然存在一個報文到達目的節點(可以排出)或脫離該環(不請求U，向上傳輸)，則將產生新的空閑VC。W中請求X虛通道的報文必有一個能夠請求成功，W中的報文可以繼續向X通道傳輸，則在這種情況下存在一個報文可以移動。

綜上所述，這種新的多播路由算法是無死鎖的。與RPM的死鎖避免方法不同，新的多播死鎖避免方法解決了RPM 為了防止死鎖而采用兩個虛擬網絡造成的網絡緩存資源使用不均衡的問題；與BAM的死鎖避免方法也不同，解決了BAM為防止網絡死鎖采用逃逸虛通道而造成的虛通道的資源沒有充分利用，和逃逸虛通道中帶寬的不充分利用等問題。

3 路由器流水線和微體系結構

本文選擇的基準路由器是交叉開關分配虛通道路由器[10,11]。路由器使用預先選擇策略來提前選擇擁塞比較小的輸出端口，其原理是前一個時鐘預先選擇每個象限下一時鐘的優先輸出端口。多播報文和單播報文采用經典的五步流水線，單播報文流水線如圖3a所示和多播報文流水線如圖3b所示。

Figure 3 Packet pipeline圖3 報文的流水線

在多播通信模式下，在中間路由器，一個包需要去復制幾個拷貝的包。為了支持多播包的復制，路由器需要增加復制部件，修改在單播包情況下的虛通道分配器VA(Virtual Channel Allocator)和交叉開關分配器SA(Switch Allocator) 。由于Cache 一致性協議的多播報文一般傳輸的是控制信號，故網絡上傳輸的多播報文都是單切片報文。路由器增加的復制部件僅僅是一些控制邏輯，多播包只有SA和VA分配成功才復制切片向下傳輸。這種情況下不需要等待所有的地址都分配成功才發送切片。滿足一個輸出端口則發送一個復制切片，只有當所有的請求輸出端口都得到滿足時 ，多播報文才能夠從輸入虛通道中移除。

圖4描述了路由器微體系結構。Pre-selection 模塊為每個象限預先選擇了優先的輸出端口，由于預先選擇模塊在報文進行路由計算之前已經預先選擇了優先的輸出端口，故不會影響路由器關鍵路徑的延時，單播報文和多播報文路由計算都會使用該模塊的預先選擇輸出信號來提前確定每個象限的優先方向。

Figure 4 Router microarchitecture圖4 路由器微體系結構

4 實驗評估

本節評估所提出的死鎖避免方法與RPM和BAM結合使用時網絡性能的改進。實驗中主要使用合成流量模式[11]，使用時鐘精確模擬器Booksim[11]，對改進的多播路由器微體系結構進行了細粒度建模。合成流量模式下評估RPM、BAM和本文提出的基于氣泡流控的RPM和BAM(分別記做RPM-B、BAM-B)。RPM需要將網絡劃分成兩個虛擬網絡(分別用于傳輸向上和向下的報文)，故不需要配置逃逸虛通道，不會發生死鎖；BAM 的多播虛擬網絡也需要劃分兩個虛擬網絡(自適應網絡和逃逸虛網絡)，逃逸虛網絡是為了防止死鎖。而RPM-B和BAM-B只有一個網絡，它通過向網絡注入氣泡來防止死鎖。本實驗在二維Mesh網絡中進行評估。

多播報文與單播報文都包含一個切片，實驗中使用多種合成流量模型[11]，包括uniform random、transpose、bit rotation 和random permutation。網絡拓撲結構使用4×4、8×8的Mesh網絡，多播報文目的節點數目與位置在網絡中均勻分布。表2給出了基準實驗配置參數和用于算法敏感性分析和它的擴展性分析的參數。

Table 2 Configuration parameters in these experiments

4.1 性能

實驗測試了RPM、RPM-B、BAM和BAM-B網絡的整體性能。RPM：兩個虛擬網絡分別用于傳輸向上和向下的報文；RPM-B： RPM路由算法的改進，只有一個虛擬網絡，在其網絡加入氣泡，即空VC避免死鎖；BAM：兩個虛擬網絡分別是自適應網絡；逃逸虛網絡和BAM-B：BAM路由算法的改進，只有一個虛擬網絡，在其網絡加入氣泡，即空VC。

4.1.1 網絡的整體性能

圖5給出了網絡的路由算法在uniform random、transpose、bit rotation 和random permutation四種不同的合成流量模型下網絡的整體性能。

Figure 5 Performance of different synthetic loads圖5 不同合成負載下的性能

將RPM-B和BAM-B與RPM和BAM 進行比較，從圖5中看到取得了性能的提升，報文的平均延時都得到了降低，而網絡的飽和吞吐量除了bit rotation合成流量負載下RPM-B的性能比RPM性能稍差外，其他的飽和吞吐率得到了提升。uniform random 合成流量模型下BAM-B飽和吞吐率提升了6.3%，網絡平均延時下降了8.6%。而RPM-B相對于RPM來說，網絡的平均延時在注入率比較高時得到了下降，而網絡吞吐率沒有明顯提升。因為RPM分為兩個網絡，在流量比較低的時候資源和RPM-B基本上一樣，對性能沒有多大的影響，當網絡流量比較高時，RPM不同維度間緩存資源的不均衡性顯現，導致報文的延時增大。transpose和random permutation合成流量模型下BAM-B相對于BAM飽和吞吐率分別提升了4.1%、5.5%，平均網絡延時降低了15.4%、15.0%;而RPM-B相對于RPM飽和吞吐率分別提升了71.4%、75%，網絡平均延時降低了24.9%、12.7%。由于transpose和random permutation兩種合成流量負載模型對于RPM將網絡分成兩個虛擬網絡的算法，更容易造成網絡中不同維度間緩存資源的不均衡，所以網絡中的平均吞吐率提升和網絡平均延時的下降都比較明顯。BAM在不同維度緩存資源相對均衡，只有逃逸虛通道網絡存在緩存資源不均衡問題，所以網絡平均吞吐率相對增加較少，網絡平均延時下降沒有RPM-B的明顯。而在bit rotation模型下，BAM-B相對于BAM飽和吞吐率沒有得到提升，網絡平均延時降低了12.2%;RPM-B相對于RPM飽和吞吐率和網絡平均延時都沒有得到很好的提升。

4.1.2 多播的性能

圖6給出了網絡中只有多播報文時網絡的整體性能，BAM-B相對于BAM飽和吞吐率提升了16.7%，網絡平均延時降低17.30%，網絡中全都是多播報文相比網絡中存在單播報文的流量模型，使網絡中的報文更容易進入逃逸網絡，更容易成為網絡的瓶頸，從而改進后使網絡飽和吞吐率提升最大，網絡平均延時降低最大。RPM-B相對于RPM平均網絡延時僅僅在網絡注入率比較高的時候才有少許的性能提高，而網絡飽和吞吐率提升了6.7%，由于網絡中都是多播包，當網絡注入率比較低時RPM和RPM-B都能夠有效地使用網絡的資源，性能基本相當，而當網絡注入率比較高時由于RPM把網絡分成向上和向下的網絡，造成網絡不同維度的通道使用率不同，導致相對于RPM-B更容易發生飽和。

Figure 6 Performance under 100% the proportion of multicast packets圖6 100%多播報文比例下的性能

4.2 敏感性分析

為了分析本文方法對網絡整體性能影響和可擴展性方面的影響，進一步開展敏感性分析實驗。由于RPM與BAM有類似的性質，不再討論RPM與它的改進算法對于各種資源的敏感性分析。我們主要以BAM與BAM-B為分析對象，圖7對多播改進性能在虛通道數目、多播報文比例、多播報文的平均目標節點數、網絡規模四個方面對網絡性能與可擴展性進行分析。

4.2.1 虛通道數目

圖7a給出了虛通道配置分別是8個VC、6個VC、4個VC時網絡的性能。從圖7a中可以看到,當虛通道數為8個VC、6個VC、4個VC時，網絡吞吐量分別提升6.3%、8.8%、14.2%，延時分別下降8.6%、8.1%、14.2%。當配置較小的虛通道時，由加氣泡的方法來避免死鎖帶來了性能的很大提升。

主要有兩個方面因素影響了性能：(1)虛通道比較少時，緩存資源稀缺性增強，增加氣泡的方法可以使逃逸虛通道的緩存資源釋放，釋放稀缺的緩存資源。隨著虛通道數的增加，緩存資源的稀缺性逐漸降低，當8個VC時，網絡飽和吞吐率只有6.3%的提升，而4個VC時，網絡飽和吞吐率提升14.2%。

(2)由于BAM由自適應網絡和逃逸虛網絡組成，逃逸虛網絡中采取維序路由的算法，使多播通道重用的概率降低，增加了網絡延時；同時，由于逃逸虛通道只有符合維序路由的包才能夠注入，使得垂直方向和水平方向的網絡使用情況不均衡，這種不均衡性隨著網絡中虛通道的減小更加明顯，所以虛通道少時，改進算法的延遲下降更明顯。

Figure 7 Performance under different network parameters圖7 不同網絡參數下的性能

4.2.2 多播報文比例

圖7b給出了多播比例配置不同時網絡的性能及可擴展性分析。從圖7b中可以看,到多播比例分別是10%、15%、20%時，網絡的平均延時降低分別為13.80%、14.40%、14.80%，網絡的吞吐率提升分別為8.6%、7.3%、7.9%。改進的多播路由算法隨著網絡多播包比例的提高，平均延時降低越明顯，因為隨著網絡中多播報文的增加，網絡中總的報文數量也在大量增加。在BAM中進入逃逸虛通道的報文數量也增加，從而增加網絡中報文的網絡延時，降低了網絡的吞吐率。多播比例增加時，加入氣泡避免死鎖的方法能夠提供更多的網絡資源，延時下降更為明顯，使得延時下降比例從13.80% 提升到14.80%。

4.2.3 多播報文的平均目標節點數

圖7c給出了多播目的節點數量配置不同時網絡的性能及可擴展性分析。從圖7c中可以看到,多播目的節點數量分別為6、9、12、15時，網絡的平均延時分別降低13.80%、14.70%、15.30%、16.60%，網絡的吞吐率分別提升8.6%、7.3%。10.50%、8.1%。可見，多播平均節點數目對網絡延時與吞吐率的影響，與多播報文比例對網絡性能的影響類似。

4.2.4 網絡規模

圖7d給出了4×4 Mesh、8×8 Mesh網絡性能，本文方法的網絡平均延時分別下降13.80%、18.1%，網絡飽和吞吐率提升分別為8.6%、9.8%。由于8×8 Mesh網絡中節點數目比4×4 Mesh網絡中的節點數目多，報文需要走過更多的路徑才能到達目的節點。所以，從圖7d中可以看到，對于網絡的延時，8×8網絡比4×4網絡延時明顯增大，同時改進后的網絡平均延時降低比率也從13.8%增加到18.1%，網絡的飽和吞吐率提升比例從8.6%提升到9.8%。由于網絡規模的增大對于BAM來說，包進入逃逸虛通道避免死鎖的機會更大，更容易使逃逸虛通道成為網絡性能提升的瓶頸，而BAM-B能夠更好地利用網絡的資源，去掉了逃逸虛通道，解除了網絡性能提升的瓶頸，使網絡平均延時明顯降低，吞吐率明顯增加。

5 結束語

在當前的眾核系統中，支持多播的片上網絡變得非常重要。它不僅可以提高網絡的飽和吞吐率，也可以降低網絡的平均延時，提高網絡帶寬的利用率。不同多播路由算法對網絡資源的利用和網絡中報文的分布至關重要，從而對網絡的飽和吞吐率和平均網絡延時有極大的影響。

本文提出的通過網絡中加入氣泡，即空閑虛通道的方式來避免網絡中的死鎖，充分釋放了網絡中的緩沖資源，提高了網絡性能。我們提出的新多播路由算法，相對于最先進的多播路由算法，減少了網絡的平均延時和提升了網絡的飽和吞吐率。網絡平均延時相對于最先進的多播路由算法降低了18.1%，飽和吞吐率相對于最先進的多播路由算法提升了16.7%。相對于RPM路由算法改進后的飽和吞吐率最大提升75%，平均延時最大下降24.9%。

[1] Chaiken D,Field C,Kurihara K,et al.Directory-based cache coherence in large scale multiprocessors[J]. Computer,1990, 23 (6):49-58.

[2] Martin M M K, Hill M D, Wood D A. Token coherence:Decoupling performance and correctness[C]∥Proc of the 30th International Symposium on Computer Architecture, 2003:182-193.

[3] Jerger N E, Peh L-S, Lipasti M, et al. Virtual circuit tree multicasting:A case for on-chip hardware multicast support[C]∥Proc of ISCA, 2008:229-240.

[4] Malumbres M P, Duato J, Torrellas J. An efficient implementation of tree-based multicast routing for distributed shared-memory multiprocessors[C]∥Proc of IPDPS,1996:186-189.

[5] Rodrigo S, Flich J, Duato J, et al. Efficient unicast and multicast support for CMPs[C]∥Proc of MICRO’08, 2008:364-375.

[6] Wang L, Jin Yu-hu, Kim H, et al. Recursive partitioning multicast:A bandwidth-efficient routing for networks-on-chip[C]∥Proc of NOCS’09, 2009:64-73.

[7] Ma S, Jerger N E, Wang Z Y. Supporting efficient collective communication in NoCs[C]∥Proc of HPCA’12, 2012:165-176.

[8] Duato J. A new theory of deadlock-free adaptive routing in wormhole networks [J].IEEE Transactions on Parallel and Distributed Systems, 1993,4(12):1320-1331.

[9] Xiao Can-wen, Zhang Min-xuan, Dou Yong, et al. Dimensional bubble flow control and fully adaptive routing in the 2-D mesh network on chip[C]∥Proc of EUC’08,2008:353-358.

[10] Jerger N E, Peh L. On-chip networks [M]. 1st ed. California:Morgan & Claypool Publishers, 2009.

[11] Dally W, Towles B. Principles and practices of interconnection networks [M]. San Francisco:Morgan Kaufmann Publishers Inc, 2003.