[發明專利]基于多路徑路由的片上網絡重組緩存的上界優化方法有效

申請號：	201410199100.1	申請日：	2014-05-12
公開（公告）號：	CN103955584B	公開（公告）日：	2017-08-25
發明（設計）人：	杜高明;李苗;宋宇鯤;張多利;王春來;劉鑫;尹勇生	申請（專利權）人：	合肥工業大學
主分類號：	G06F17/50	分類號：	G06F17/50;H04L12/721;G06F15/173
代理公司：	安徽省合肥新安專利代理有限責任公司34101	代理人：	何梅生
地址：	230000 ***	國省代碼：	安徽;34
權利要求書：	查看更多	說明書：	查看更多
摘要：
搜索關鍵詞：	基于路徑路由網絡重組緩存上界優化方法
鉆瓜網技術展會專利詞庫專利權人專利榜在售專利公布日期熱門專利

【說明書】：

技術領域

本發明屬于集成電路片上網絡設計技術領域，涉及基于多路徑路由的片上網絡重組緩存的上界優化方法。

背景技術

《Very Large Scale Integration Design》2007年1-11頁中‘Amethod for routing packets across multiple paths in NoCs with in-order delivery and fault-tolerance guarantees’一文提出針對無交叉子業務流的多路徑路由方法，以降低網絡帶寬需求和功耗需求，并針對瞬時和永久錯誤提出容錯方案；不足之處在于沒有討論如何設置重組緩存的大小，從而存在丟包或重組緩存面積過大的風險；

《Design,Automation & Test in Europe》2009年1058–1063頁中‘In-network reorder buffer to improve overall NoC performance while resolving thein-order requirement problem’一文中介紹了通過將重組緩存從路由器外邊移到路由器里邊，通過共享給其他業務流來提高重組緩存的利用率；不足之處同樣沒有給出重組緩存的設置方案，存在丟包或重組緩存面積過大的風險；

《IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS》2010年12期1973-1986頁中‘Buffer Optimization in Network-on-Chip Through Flow Regulation’一文基于網絡演算理論提出了片上路由器輸入緩存的分析模型及其大小的分析方法；不足之處在于沒有進一步研究位于業務流輸出端的包重組緩存大小的分析方法。

《IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS》第31卷第一期(2012年1月)第146-159頁文章‘Memory-Efficient On-Chip Network with Adaptive Interface’提出使用一種流線型的重新排序機制來實現業務在目的節點的排序，不足之處仍然沒有給出重組緩存大小的設置方案，存在丟包或重組緩存面積過大的風險。

《中國科技論文在線電子雜志》2013年64期中‘多路徑路由NoC重組緩存區的分析及優化’一文基于網絡驗算提出了計算兩條目標子流的重組緩存區模型，不足之處在于該文章在優化重組緩存上界中采用傳統全遍歷法，分析時間長，算法復雜度大。

基于以上背景，本發明提出來一種沖突預測片上網絡重組緩存上界的優化方法，通過沖突矩陣，推導出每條子業務流的沖突系數，進而從無交叉路徑組沖突系數表中選出最大最小范圍，來預測重組緩存的最大值和最小值。

發明內容

本發明的目的在于提供基于多路徑路由的片上網絡重組緩存的上界優化方法，解決了現有技術沒有給出重組緩存上界的設置方案，存在重組緩存面積過大、浪費成本的問題。

本發明所采用的技術方案是通過以下步驟來實現：

步驟a：計算片上網絡的路由節點沖突矩陣；

步驟b：計算每條目標子業務流沖突系數；

步驟c：求目標業務流無交叉路徑組的沖突系數表；

步驟d：從沖突系數表得出最大最小預測范圍；

步驟e：根據預測路徑計算重組緩存值，得出優化結果。

進一步，所述路由為多路徑最短路由，所述片上網絡為N×N(N≥2)的網絡結構。

進一步，業務流為分析路徑得到的業務流劃分為目標業務流和沖突業務流，目標業務流定義為所需要研究的對象，拆分為兩條目標子業務流；沖突業務流定義為對目標業務流造成沖突的業務流，由于沖突的存在導致目標流中數據包后發先至形成重組緩存區。