[發(fā)明專利]互連網(wǎng)絡系統(tǒng)的自適應路由方法

有效

• 申請?zhí)枺?/td>: 201310039424.4
• 申請日: 2013-01-31
• 公開（公告）號: CN103973564B
• 公開（公告）日: 2017-12-15
• 發(fā)明（設計）人: 向東;虞志剛
• 申請（專利權(quán)）人: 清華大學
• 主分類號: H04L12/721
• 分類號: H04L12/721;H04L12/801
• 代理公司: 北京路浩知識產(chǎn)權(quán)代理有限公司11002
• 代理人: 王瑩

技術領域

本發(fā)明涉及分布式計算技術領域，尤其涉及一種互連網(wǎng)絡系統(tǒng)及自適應路由方法。

背景技術

互連網(wǎng)絡通常實現(xiàn)不同處理節(jié)點間的同步和通信，是多處理器系統(tǒng)中連接處理器、存儲器、I/O設備的重要組成部分。互連網(wǎng)絡是影響整個多處理器系統(tǒng)的性能和擴展性的重要方面。如何在現(xiàn)有技術基礎上，為處理節(jié)點之間的提供低延遲、高效通信成為互連網(wǎng)絡亟待解決的關鍵問題。

微處理器技術的發(fā)展使得單個處理節(jié)點的計算能力迅速提高，這也對互連網(wǎng)絡的性能提出了更高的要求。實際上，互連網(wǎng)絡帶寬的增長與微處理器性能的增長有約30％的差距。因此互連網(wǎng)絡的延遲和帶寬已成為制約多處理器系統(tǒng)性能提高的瓶頸之一。

隨著半導體工藝的不斷發(fā)展以及電路技術的長足進步，串行通道成為有效的信號傳輸方式。高速串行通道的使用可以大幅度提高單管腳的帶寬，從而減少路由器芯片的管腳數(shù)目。九十年代初，路由器的管腳帶寬限制在10Gbps，而到了二十一世紀，管腳帶寬可以達到10～20Tbps。這些技術的進步，使得高階路由器的實現(xiàn)成為可能。

高階路由器將成為互連網(wǎng)絡的發(fā)展趨勢，由高階路由器構(gòu)成的互連網(wǎng)絡通常只需要幾個跳步就可以連接數(shù)以萬計的處理器，可以直接減小網(wǎng)絡直徑，實現(xiàn)處理器節(jié)點之間高效通信，降低消息延遲和實現(xiàn)代價，從而改善系統(tǒng)性能。

2006年Cray公司的Blackwidow超級計算機，首次采用使用了64階路由芯片，通過Clos網(wǎng)絡實現(xiàn)了多達32000處理器之間的互連，其可以保證任意兩個處理器之間的距離不超過7個跳步。2012年Cray公司的Cascade超級計算機，采用了48階路由芯片，通過Droganfly網(wǎng)絡實現(xiàn)370216個處理器之間的互連，任意兩個處理器之間的距離不超過5個跳步，然而需要使用4條虛擬通道實現(xiàn)無死鎖自適應路由。

然而，在現(xiàn)有芯片技術和高階路由器技術的基礎上，如何設計出高效的網(wǎng)絡互連拓撲，并提出高效的路由方法成為一個新的亟待解決的研究課題。Blackwidow Clos網(wǎng)絡首次采用了高階路由器，但是網(wǎng)絡成本較高，而且網(wǎng)絡直徑較大，對系統(tǒng)性能有一定影響；Cascade Dragonfly網(wǎng)絡也采用了高階路由器，具有高可擴展性和低成本的特點，并且能夠提供較小的網(wǎng)絡直徑，然而需要采用4條虛擬通道來避免死鎖，增加了路由器設計復雜度，增大了消息路由延遲，限制了系統(tǒng)性能。

發(fā)明內(nèi)容

(一)要解決的技術問題

本發(fā)明要解決的技術問題是：提供一種基于路由器標號的互連網(wǎng)絡系統(tǒng)及其相應的自適應路由方法。該互連網(wǎng)絡系統(tǒng)及路由方法不僅保持了Dragonfly網(wǎng)絡原有的低成本、高擴展性、低網(wǎng)絡直徑的特點，而且不需要使用虛擬通道即可實現(xiàn)無死鎖部分或完全自適應路由。

(二)技術方案

為解決上述問題，本發(fā)明一方面提供了一種互連網(wǎng)絡系統(tǒng)，所述系統(tǒng)將系統(tǒng)內(nèi)路由器劃分為n個路由器組，所述n個路由器組之間實現(xiàn)全連接，使得任意兩個路由器組之間的通信只需一個跳步；所述每個路由器組包含一個或多個路由器，組內(nèi)路由器之間實現(xiàn)全連接，使得組內(nèi)任意兩個路由器之間距離為一個跳步，其中n為大于或等于1的整數(shù)。

優(yōu)選地，所述每個路由器組包括m個路由器，其中m為大于或等于1的整數(shù)。

優(yōu)選地，所述系統(tǒng)內(nèi)的每個路由器包括a個局部端口，p個處理器端口和g個全局端口；所述a個局部端口用于實現(xiàn)路由器組內(nèi)路由器之間的互連，對應的互連通道即為局部通道；所述p個處理器端口用于實現(xiàn)路由器與處理器節(jié)點之間的互連，對應的互連通道即為處理器通道；所述g個全局端口用于實現(xiàn)路由器組之間的互連，對應的互連通道即為全局通道。

優(yōu)選地，所述每個路由器組內(nèi)路由器個數(shù)m＝a+1，所述系統(tǒng)內(nèi)路由器組數(shù)n＝mg+1,所述每個路由器組的等效端口數(shù)k’＝m(p+g)。

本發(fā)明另一方面提出了一種互連網(wǎng)絡系統(tǒng)的部分自適應路由方法，包括以下步驟：