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

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

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

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

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

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

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

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