局部扭曲立方體路由算法研究.pdf

1、多計(jì)算機(jī)系統(tǒng)中的互連網(wǎng)絡(luò)為處理器之間相互通信提供了一種有效的機(jī)制，是決定系統(tǒng)性能的重要因素之一。在互連網(wǎng)絡(luò)中，節(jié)點(diǎn)間的通信由路由算法實(shí)現(xiàn)。路由算法決定了一條消息或報(bào)文到達(dá)目的節(jié)點(diǎn)所經(jīng)過的路徑。當(dāng)代并行機(jī)的互連網(wǎng)絡(luò)一般都采用蟲孔交換作為網(wǎng)絡(luò)互連的機(jī)制。而蟲孔交換路由算法很容易產(chǎn)生死鎖現(xiàn)象，導(dǎo)致消息不能到達(dá)目的節(jié)點(diǎn)，通信無法完成。這些都是設(shè)計(jì)路由算法時(shí)必須考慮的問題。 局部扭曲立方體是一種新型的互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。作為超立方體的一種變

2、體，其直徑大約只有超立方體的一半左右。一個(gè)局部扭曲立方體可由兩個(gè)低一維的子立方體根據(jù)一定規(guī)則連邊得到。對于這種結(jié)構(gòu)的路由算法，目前尚沒有進(jìn)行詳細(xì)研究。本文的主要工作就是基于局部扭曲立方體進(jìn)行的。 本文首先介紹了互連網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中路由器模型和各種交換技術(shù)，接著介紹了現(xiàn)有的單播和多播路由算法和其中的無死鎖路由理論。然后，在對局部扭曲立方體結(jié)構(gòu)進(jìn)行了詳細(xì)介紹。本文對局部扭曲立方體路由算法的主要研究工作如下： 在單播方面，本文提

3、出了四種算法。首先是一種基于轉(zhuǎn)彎模型的單播最短自適應(yīng)路由算法。該算法利用將物理通道分成兩條虛通道進(jìn)而形成兩個(gè)不相交的虛擬網(wǎng)絡(luò)，將不同的點(diǎn)對之間的路由限定在某一個(gè)虛擬網(wǎng)絡(luò)中，從而有效地避免了死鎖的產(chǎn)生。在此基礎(chǔ)上，利用局部扭曲立方體的特點(diǎn)，本算法對局部的子立方體采用了P-cube路由，使其能在局部子立方體中自適應(yīng)路由。接下來，在保證無死鎖的條件下，通過提高通道的利用率，提出了一種更具自適應(yīng)性的路由算法。本文提出來的第三種算法針對死鎖產(chǎn)生的

4、特點(diǎn)，犧牲了一部分最短路由，不需要采用虛通道。雖然這種算法中路由不一定是最短的，但它在局部的子立方體中能最大限度地進(jìn)行P-cube路由，自適應(yīng)性有了明顯提高。最后，本文還首次提出了一種基于路徑的單播自適應(yīng)算法，對局部扭曲立方體進(jìn)行編號，依照編號來確定路由路徑。它同樣被證明是無死鎖的。 在多播路由算法研究方面，本文首先給出了局部扭曲立方體的廣播樹算法。只適合支持SAF和VCT交換技術(shù)的網(wǎng)絡(luò)，當(dāng)與蟲孔路由結(jié)合時(shí)，很容易產(chǎn)生死鎖。然后