片上網絡路由算法關鍵問題研究.pdf

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

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

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

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

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

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

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