多計算機互連網(wǎng)絡上聚合通信算法的研究.pdf

1、現(xiàn)代科學、生活的發(fā)展越來越迫切地需要更強大的計算能力，而研制具有每秒萬億次、千萬億次處理速度的并行系統(tǒng)需要設計高性能的互連網(wǎng)絡來連接大量的處理器。同時，隨著系統(tǒng)規(guī)模的不斷擴大，處理器之間的通信問題變得越來越突出。在大規(guī)?？茖W計算和工程應用中，聚合通信的開銷往往占到全部通信開銷的絕大部分。因此研究互連網(wǎng)絡及相關的聚合通信算法對提高并行計算機的性能，進而提高并行應用程序的執(zhí)行效率具有重要的意義。 本文圍繞如何提高互連網(wǎng)絡上聚合通信操

2、作的通信性能這一問題，開展了以下研究工作： 本文首先深入研究了單端口環(huán)網(wǎng)結構上全交換操作的實現(xiàn)算法。環(huán)網(wǎng)結構是一種具有很好拓撲特性和應用前景的互連網(wǎng)絡，是目前很多超級計算機廣泛選用的互連拓撲結構。同時，全交換操作在并行計算領域中有著大量而且重要的應用。本文基于高維單端口環(huán)網(wǎng)結構設計了新型網(wǎng)絡劃分策略，并運用該策略在高維單端口環(huán)網(wǎng)結構上提出了通信量近似最優(yōu)的間接全交換算法。與現(xiàn)有的其它相關算法相比，本文提出的高維全交換算法不僅具有

3、很好的可擴展性，而且通信性能有特別顯著的提高。 其次，本文改進了單端口二維和三維環(huán)網(wǎng)結構上具有最小啟動時間的全交換算法。與原有算法相比，改進后的算法采用“自底向上再回送”的通信模式，在取得最小啟動時間的同時，提高了算法整體的通信性能。 再次，考慮到目前多端口環(huán)網(wǎng)結構上全交換操作的研究不足，本文充分利用了多端口環(huán)網(wǎng)的多個通信端口，首次在多端口一維環(huán)、二維和四維環(huán)網(wǎng)上提出了通信量完全達到理論下限的間接全交換算法。分析結果表明

4、，當消息較長時，與已有的相關算法相比，本文提出的多端口環(huán)網(wǎng)上的全交換算法具有更優(yōu)的通信性能。 然后，基于由多臺以太網(wǎng)交換機分層級聯(lián)而成的機群系統(tǒng)，本文提出通信量達到理論下限的直接全交換算法DCE和間接全交換算法MCCE。全交換算法MCCE不僅達到了通信量的理論下限，而且大幅度地減少了消息啟動開銷和同步開銷，進一步提高了全交換操作的通信性能。實驗結果表明，當消息較長時，本文提出的這兩個全交換算法在上述機群系統(tǒng)中明顯優(yōu)于MPICH和

5、LAM/MPI中實現(xiàn)的全交換算法。 接下來，針對傳統(tǒng)的基于軟件層面的多播技術容易導致路由延遲并加劇內存讀寫瓶頸等問題，本文考慮在路由器和交換機的內部交換結構中采用支持并發(fā)多播等通信方式的多級互連網(wǎng)絡，從而在硬件層面上實現(xiàn)并發(fā)多播等通信方式。在深入研究了廣義非阻塞型多播網(wǎng)絡的低代價構建和多播路由算法的優(yōu)化等問題之后，本文提出了一種低代價的廣義非阻塞四級Clos網(wǎng)絡及相關的多播路由算法。與現(xiàn)有廣義非阻塞多播網(wǎng)絡相比，本文構造的多播網(wǎng)

6、絡具有如下特色：①網(wǎng)絡的硬件代價降低到12Nз/2個交叉點以下，僅相當于廣義非阻塞置換網(wǎng)絡的常數(shù)倍；②時間復雜度為O(N)的多播路由算法簡單、高效，易于硬件實現(xiàn)；③降低了單個交叉開關模塊的引腳(端口)數(shù)目，更有利于VLSI芯片的集成。④增加的一級開關模塊可以有效地平衡多播負載，增加網(wǎng)絡的靈活性。 最后，本文深入研究了能夠支持并發(fā)多播目標端口重疊的廣義非阻塞k-fold多播網(wǎng)絡及相關的多播路由算法。該網(wǎng)絡可以用較低的硬件代價來有效

7、地減少多播連接的外部阻塞，從而為多播通信提供更好的Qos性能。本文通過重新計算廣義非阻塞四級Clos多播網(wǎng)絡的中間兩級開關個數(shù)，以提供足夠的網(wǎng)絡內部路徑來實現(xiàn)k-fold多播路由。基于此思路，本文提出了兩個廣義非阻塞k-fold多播路由算法及相應的硬件條件。 需要說明的是，雖然本文整體的研究工作是根據(jù)并行分布式多處理機系統(tǒng)的特點以及特定的應用需求展開的，但是其中提出的廣義非阻塞多播網(wǎng)絡并不局限于多處理機系統(tǒng)，也適用于廣域網(wǎng)、局域