[發(fā)明專利]一種面向非規(guī)則三維集成電路片上網(wǎng)絡的路由方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 201610057261.6
• 申請日: 2016-01-27
• 公開（公告）號: CN105577539B
• 公開（公告）日: 2018-08-10
• 發(fā)明（設計）人: 李曉維;周君;李華偉
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: H04L12/707
• 分類號: H04L12/707;H04L12/721;H04L12/751;H04L12/753
• 代理公司: 北京律誠同業(yè)知識產(chǎn)權代理有限公司 11006
• 代理人: 祁建國;梁揮

本發(fā)明提出一種面向非規(guī)則三維集成電路片上網(wǎng)絡的路由方法及系統(tǒng)，該方法包括根據(jù)所述非規(guī)則三維集成電路片上網(wǎng)絡的拓撲結構，判斷采用基于漢密爾頓路徑的容錯路由算法路由數(shù)據(jù)包，或基于生成樹的容錯路由算法路由數(shù)據(jù)包；若采用基于所述漢密爾頓路徑的容錯路由算法路由數(shù)據(jù)包，根據(jù)源節(jié)點與目的節(jié)點的位置確定使用按照節(jié)點編號單調上升或單調下降的順序進行路由容錯；若采用基于所述生成樹的容錯路由算法路由數(shù)據(jù)包，則選擇生成樹根節(jié)點，根據(jù)根節(jié)點，以及源節(jié)點與目的節(jié)點的位置，選擇傳輸路徑完成所述數(shù)據(jù)包的傳輸。

技術領域

本發(fā)明涉及集成電路的技術領域，特別涉及一種面向非規(guī)則三維集成電路片上網(wǎng)絡的路由方法及系統(tǒng)。

背景技術

三維集成技術是一種將芯片不同的器件層堆疊起來，垂直集成在一起的一種封裝技術(Banerjee K,et al.,“3-D ICs:a novel chip design for improving deep-submicrometer interconnect performance and systems-on-chip integration,”inProceedings of the IEEE,Volume:89,Issue:5,2001,pp.602-633.)。這種技術可以縮短芯片內物理連線長度，達到降低系統(tǒng)時延和功耗的作用。圖1是一個簡單的4*2*3三維芯片片上網(wǎng)絡(network-on-chip，NoC)的示意圖，拓撲結構是常見的三維Mesh結構。圖中有3個不同器件層，24個處理單元(processing element，PE)分別連接各自不同的路由器節(jié)點(下稱“節(jié)點”)，節(jié)點之間通過水平或者垂直方式互連。

網(wǎng)絡拓撲是三維片上網(wǎng)絡的一個重要架構屬性，三維片上網(wǎng)絡的規(guī)則網(wǎng)絡拓撲有很多種，例如三維Mesh、三維Torus，三維Folded Torus和三維BFT(Butterfly Fat-Tree)等，然而，在實際的工業(yè)界三維多處理器芯片(chip multi-processor，CMP)中，由于處理單元一般都采用異構方式設計，不同的處理單元通常設置為不同的功能模塊以滿足實際應用的需求，例如，某些處理單元可以安置處理器，其他處理單元可以嵌入二級或三級高速緩存等，因此，三維CMP的片上網(wǎng)絡拓撲多為不規(guī)則拓撲，具體而言，網(wǎng)絡中每一個器件層的結構皆不相同，且每一個節(jié)點與其上下對應的鄰居節(jié)點之間的垂直鏈接的分布也是非均勻的，如圖2所示的典型非規(guī)則三維片上網(wǎng)絡。

由于三維集成電路的復雜度和集成度不斷提高，極大影響了片上網(wǎng)絡的通信效率，同時致使網(wǎng)絡中部件的故障發(fā)生幾率也相應增高，為了保障三維片上網(wǎng)絡的正常通信，需要引入適當?shù)娜蒎e方法，通常，片上網(wǎng)絡的故障分為瞬態(tài)性故障和永久性故障，這些故障可能發(fā)生在處理單元、網(wǎng)絡接口、路由器或者路由器間的鏈路等部件中，在本發(fā)明中，我們主要關注網(wǎng)絡中常見的永久性鏈路故障，這類故障一旦發(fā)生則不能被修復，對于片上網(wǎng)絡的通信將產(chǎn)生比瞬態(tài)性鏈路故障更為嚴重的影響，需要注意的是，由于永久性故障的發(fā)生也可能導致原本規(guī)則的網(wǎng)絡拓撲結構具有不規(guī)則的特點，這種情形同樣適用于本發(fā)明提出的方法及系統(tǒng)。

國內外針對傳統(tǒng)的二維片上網(wǎng)絡的容錯方法研究已經(jīng)比較成熟，但是針對三維片上網(wǎng)絡，尤其是非規(guī)則拓撲結構三維片上網(wǎng)絡(下稱“非規(guī)則三維片上網(wǎng)絡”)的相關成果則較少，一般而言，面向存在永久性鏈路故障的片上網(wǎng)絡的容錯方法通常分為以下幾類：1)使用冗余部件替換失效部件；2)通過在故障部件周圍添加外圍邏輯電路使數(shù)據(jù)包避開故障區(qū)域；3)使用可靠路由方法，直接控制數(shù)據(jù)包繞過故障鏈接。

通常，針對大部分應用設計的片上網(wǎng)絡規(guī)模較小、片上資源有限的現(xiàn)狀，如何設計低成本且高可靠性的容錯方法對于保障此類三維片上網(wǎng)絡的通信質量至關重要，由于冗余技術和外圍電路設計都需要對芯片的物理結構進行改造，會產(chǎn)生一定程度的面積及功耗的開銷，且電路規(guī)模越大該開銷越明顯，另一方面，可靠路由方法作為一種輕量級的片上網(wǎng)絡容錯方法，不僅不會改變芯片的結構，且能在網(wǎng)絡發(fā)生故障時繼續(xù)完成通信任務，并保證較高的通信性能，該類方法已廣泛應用于二維和三維片上網(wǎng)絡中，但主要局限于規(guī)則的三維網(wǎng)絡拓撲結構。