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

有效

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

1.一種面向非規(guī)則三維集成電路片上網(wǎng)絡(luò)的路由方法，其特征在于，包括：

步驟1，根據(jù)所述非規(guī)則三維集成電路片上網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，判斷采用基于漢密爾頓路徑的容錯(cuò)路由算法路由數(shù)據(jù)包，或基于生成樹的容錯(cuò)路由算法路由數(shù)據(jù)包；

步驟2，若采用基于所述漢密爾頓路徑的容錯(cuò)路由算法路由數(shù)據(jù)包，根據(jù)源節(jié)點(diǎn)與目的節(jié)點(diǎn)的位置確定使用按照節(jié)點(diǎn)編號單調(diào)上升或單調(diào)下降的順序進(jìn)行路由容錯(cuò)，所述數(shù)據(jù)包沿選中的漢密爾頓路徑進(jìn)行傳輸過程中，使數(shù)據(jù)包每經(jīng)過一個(gè)節(jié)點(diǎn)都距離目的節(jié)點(diǎn)更近一步；

步驟3，若采用基于所述生成樹的容錯(cuò)路由算法路由數(shù)據(jù)包，則選擇生成樹根節(jié)點(diǎn)，根據(jù)根節(jié)點(diǎn)，以及源節(jié)點(diǎn)與目的節(jié)點(diǎn)的位置，選擇傳輸路徑完成所述數(shù)據(jù)包的傳輸；

步驟4，當(dāng)所述數(shù)據(jù)包到達(dá)節(jié)點(diǎn)時(shí)，查看到達(dá)的節(jié)點(diǎn)的地址與所述目的節(jié)點(diǎn)的地址是否相同，若相同，則所述數(shù)據(jù)包到達(dá)所述目的節(jié)點(diǎn)，否則循環(huán)執(zhí)行步驟2或3，直到數(shù)據(jù)包到達(dá)目的節(jié)點(diǎn)；

其中所述步驟1包括：

若所述非規(guī)則三維集成電路片上網(wǎng)絡(luò)中存在唯一的漢密爾頓路徑，則選用所述唯一的漢密爾頓路徑執(zhí)行基于漢密爾頓路徑的容錯(cuò)路由算法；若所述非規(guī)則三維集成電路片上網(wǎng)絡(luò)中存在多條漢密爾頓路徑，則在所述多條漢密爾頓路徑中任意選擇一條，執(zhí)行基于漢密爾頓路徑的容錯(cuò)路由算法；若網(wǎng)絡(luò)中未發(fā)現(xiàn)漢密爾頓路徑，則采用基于生成樹的容錯(cuò)路由算法路由數(shù)據(jù)包。

2.如權(quán)利要求1所述的面向非規(guī)則三維集成電路片上網(wǎng)絡(luò)的路由方法，其特征在于，所述步驟2中將所述非規(guī)則三維集成電路片上網(wǎng)絡(luò)中的節(jié)點(diǎn)按照漢密爾頓路徑上的順序依次編號。

3.如權(quán)利要求1所述的面向非規(guī)則三維集成電路片上網(wǎng)絡(luò)的路由方法，其特征在于，所述步驟3中所述根節(jié)點(diǎn)滿足：

1)K_r位于第L層上，其中K_r為所述根節(jié)點(diǎn)，J為水平器件層數(shù)，L為水平器件中的某一層水平器件；

2)設(shè)所述非規(guī)則三維集成電路片上網(wǎng)絡(luò)的第層上有I個(gè)節(jié)點(diǎn)，其中層內(nèi)編號為p的當(dāng)前節(jié)點(diǎn)p，0≤p≤I-1，設(shè)Δ_pi為當(dāng)前節(jié)點(diǎn)p與層內(nèi)除節(jié)點(diǎn)p以外的第i個(gè)節(jié)點(diǎn)的最短跳步數(shù)，則K_r距離層內(nèi)除節(jié)點(diǎn)p以外節(jié)點(diǎn)的平均最短跳步數(shù)為N_r，N_r為：

4.如權(quán)利要求1所述的面向非規(guī)則三維集成電路片上網(wǎng)絡(luò)的路由方法，其特征在于，所述步驟3還包括：

在始終為入向，始終為出向、先入向再出向這三種傳輸方向中選擇傳輸路徑完成數(shù)據(jù)包的傳輸， 數(shù)據(jù)包在確定根節(jié)點(diǎn)的生成樹上進(jìn)行傳輸過程中，使數(shù)據(jù)包每經(jīng)過一個(gè)節(jié)點(diǎn)都距離目的節(jié)點(diǎn)更近一步。

5.如權(quán)利要求1所述的面向非規(guī)則三維集成電路片上網(wǎng)絡(luò)的路由方法，其特征在于，還包括：若所述步驟2或者所述步驟3中的下一跳節(jié)點(diǎn)不唯一，則根據(jù)DP-3D機(jī)制，獲得當(dāng)前節(jié)點(diǎn)每個(gè)合法端口的流量感應(yīng)情況，選擇流量最少的合法端口輸出，降低消息碰撞的幾率，避開熱點(diǎn)區(qū)域；

其中將動(dòng)態(tài)規(guī)劃選擇機(jī)制拓展至三維空間中，記為該DP-3D機(jī)制。