片上網(wǎng)絡(luò)路由算法關(guān)鍵問題研究.pdf

1、隨著半導(dǎo)體工藝的不斷發(fā)展，單個芯片上集成的晶體管數(shù)量將越來越多。屆時，它們將被組合成上千個各自獨立又相互通信的處理單元。為了充分利用它們的處理能力，需要高效的通信結(jié)構(gòu)來完成它們之間的通信。傳統(tǒng)的連接這些處理單元的總線結(jié)構(gòu)在功耗、延遲、同步、線路可靠性以及帶寬等方面很難適應(yīng)新的需要。為了滿足片上系統(tǒng)的通信需要，研究者提出了片上網(wǎng)絡(luò)(Network-on-Chip，NoC)的通信架構(gòu)，并從多個方面闡述了以片上網(wǎng)絡(luò)代替總線通信結(jié)構(gòu)的必要性。片

2、上網(wǎng)絡(luò)與通用的計算機網(wǎng)絡(luò)一樣，也采用分層的體系結(jié)構(gòu)。片上網(wǎng)絡(luò)的設(shè)計包括拓撲結(jié)構(gòu)、路由算法、交換技術(shù)、流控制策略等方面。但是，由于片上網(wǎng)絡(luò)是在單個芯片上實現(xiàn)的微型網(wǎng)絡(luò)，所以它的設(shè)計有區(qū)別于通用計算機網(wǎng)絡(luò)的獨特的地方。因為片上網(wǎng)絡(luò)結(jié)構(gòu)需要與同一個芯片上的計算單元競爭空間，所以，片上網(wǎng)絡(luò)所占的面積必須盡可能小。同時也需要盡量減少它的功耗開銷。研究者對適用于片上網(wǎng)絡(luò)的各種拓撲結(jié)構(gòu)進行了廣泛的研究。網(wǎng)格(Mesh)結(jié)構(gòu)由于具有結(jié)構(gòu)簡單、容易實現(xiàn)、

3、可擴展性好等方面的優(yōu)勢得到最多的關(guān)注。在交換技術(shù)方面，蟲孔(Wormhole)交換技術(shù)由于需要較少的緩存空間，并且數(shù)據(jù)包延遲較小，所以適合在片上網(wǎng)絡(luò)中應(yīng)用。本論文主要研究采用網(wǎng)格結(jié)構(gòu)和蟲孔交換技術(shù)的片上網(wǎng)絡(luò)的路由算法相關(guān)問題。
　　 本文具體內(nèi)容分為三大部分：第一部分為第一章和第二章，主要內(nèi)容為緒論和相關(guān)研究；第二部分為第三章到第五章，主要介紹關(guān)于路由算法的三個研究成果；第三部分為第六章、第七章以及結(jié)語部分，介紹了兩種流控制策略

4、和論文總結(jié)。
　　 本文的主要研究成果如下：首先，提出了一種為特定應(yīng)用計算路由的算法(RABC)。RABC方法通過打破信道依賴圖中所有的圈來確保得到的路由算法不會形成死鎖。由它得到的路由算法具有較高的自適應(yīng)度，且性能不依賴于它打破這些圈的順序。同時RABC算法的計算復(fù)雜度儀為O(n)。
　　 其次，提出了一種減少路由表查詢次數(shù)的方法(RQRT)。在基于表格實現(xiàn)的路由中，為了降低數(shù)據(jù)包延遲，從而提高系統(tǒng)性能，需要對路由表的

5、查詢方法進行改進。由于網(wǎng)格結(jié)構(gòu)比較規(guī)則，從而為其生成的路由表也有一定的規(guī)律可循。RQRT方法充分利用網(wǎng)格拓撲結(jié)構(gòu)路由表的規(guī)律特性，減少了50％的路由表查詢次數(shù)，極大地提高了系統(tǒng)的性能。
　　 第三，提出了ANoP選擇策略。當(dāng)路由算法計算出多個輸出端口時就需要選擇策略從中選擇一個恰當(dāng)?shù)妮敵龆丝?。ANoP選擇策略能公平地選擇所有由路由算法計算出的輸出端口，使流量在網(wǎng)絡(luò)中均勻分布，從而能夠充分利用網(wǎng)絡(luò)資源，提高系統(tǒng)性能。
　　

6、 第四，提出了注入水平流控制策略(ILFC)。在該流控制策略中，源節(jié)點發(fā)送數(shù)據(jù)的速率被劃分成若干個水平(Injection Level)。然后源節(jié)點在發(fā)送數(shù)據(jù)的時候根據(jù)網(wǎng)絡(luò)的狀態(tài)自動選擇最大且不會使網(wǎng)絡(luò)發(fā)生擁塞的注入率水平。模擬結(jié)果表明，應(yīng)用了IJFC流控制后，片上網(wǎng)絡(luò)就會運行在比較平穩(wěn)的狀態(tài)，不再發(fā)生擁塞。
　　 第五，提出了四分之一負載門限(QLT)流控制策略。通過記錄網(wǎng)絡(luò)的狀態(tài)，我們發(fā)現(xiàn)，為了避免片上網(wǎng)絡(luò)進入一種惡性擁塞狀

7、態(tài)，網(wǎng)絡(luò)的負荷存在著一個門限值(具體為路由器緩存空間的四分之一)。當(dāng)網(wǎng)絡(luò)的負載低于該門限值時，網(wǎng)絡(luò)中就不會出現(xiàn)擁塞。反之，當(dāng)網(wǎng)絡(luò)的負荷超過該門限值時，網(wǎng)絡(luò)中就會出現(xiàn)嚴重的擁塞。而且該門限值規(guī)律在網(wǎng)絡(luò)的局部范圍內(nèi)仍然起作用。根據(jù)這個發(fā)現(xiàn)，我們設(shè)計了QLT流控制策略。它基本思想是記錄路由器被占用的緩沖區(qū)的總和，如果它超過了指定門限值，則認為該路由器所在的路徑已經(jīng)發(fā)生擁塞了，應(yīng)該推遲向該路徑發(fā)送數(shù)據(jù)。否則認為該路徑?jīng)]有發(fā)生擁塞，可以繼續(xù)發(fā)送數(shù)