[發明專利]基于差分進化和捕食搜索策略的胖樹型片上網絡映射方法

有效

• 申請號: 201110276587.5
• 申請日: 2011-09-19
• 公開（公告）號: CN102325089A
• 公開（公告）日: 2012-01-18
• 發明（設計）人: 顧華璽;張碧霞;楊銀堂;王琨;鄧植
• 申請（專利權）人: 西安電子科技大學
• 主分類號: H04L12/56
• 分類號: H04L12/56;H04L29/06
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 王品華;朱紅星

技術領域

本發明屬于網絡技術領域，涉及系統級芯片設計和片上IP核到網絡節點的映射方法，適用于低能耗的大規模胖樹型片上網絡快速IP核映射。

背景技術

基于總線架構的片上系統SoC是以IP核復用為特點的一種集成電路設計方法。這些IP核可以是通用處理器、協處理器、DSP、面向應用的硬件、存儲器模塊和輸入/輸出模塊等等。隨著晶體管工藝的發展和處理器主頻的快速增長，SoC中IP核的數量和復雜度不斷提高，總線結構面臨的主要問題表現在：(1)長互連線問題。隨著與總線相連的IP核數目的增加，必然引起總線長度的增加，由此會給后端布線造成麻煩，還會引起線間串擾問題。(2)時鐘同步問題。總線結構要求與總線相連的模塊采用全局同步時鐘。隨著集成電路頻率的增加和芯片集成度的提高，全局同步越來越難實現。(3)地址空間可擴展性問題，SoC系統中IP核增多，互連線增長，會引入更多的寄生電阻、電容，導致電路延遲增大，最終延遲可能超過時鐘周期，這實際上限制了與總線相連的IP核數目，因此限制了系統的可擴展性。因此，總線結構越來越不能滿足超大規模集成電路VLSI設計的需求。為了更好地組織芯片上數目眾多的IP核，需要一個模塊化、擴展性好、可重用、高性能的互連結構。

近年來，為了克服上述問題，借鑒計算機從單機發展到計算機網絡的歷史經驗，將網絡的概念引入到芯片中來，尋求解決集成電路發展瓶頸的方法，提出了片上網絡NoC結構。NoC采用全局異步局部同步GALS的策略將各個IP核用網絡組件連接起來。它能解決SoC發展所面臨的一系列難題，因此，NoC的研究成為了當今學術界和工業界的研究熱點。

胖樹型拓撲結構由于具有高對分帶寬、低網絡直徑、良好的擴展性和豐富的路徑多樣性等特點，被廣泛應用于片上網絡研究中。

為了更好地在單個芯片上集成更大規模的電路，面積、能耗和速度是設計NoC的主要約束。其中，由于NoC的電路規模很大，且基于納米工藝加工，能耗幾乎是NoC最重要的約束。因此，降低通信能耗成為NoC設計中的關鍵問題。

NoC映射是NoC設計中非常重要的一個步驟。NoC映射問題，就是在給定任務圖和拓撲結構基礎上，針對特定設計目標和約束條件，將每個任務分配到合適的IP核上，最后決定每個IP核在NoC拓撲結構上的位置。NoC映射問題是一個NP難問題，它的搜索空間隨著網絡尺寸成階梯遞增，對于一個IP核個數為N的NoC系統，有N！種映射結果。映射結果對硬件代價、網絡性能、芯片能耗等有重大影響。近年來，映射算法大都采用啟發式算法，有遺傳算法、分支定界算法、蟻群算法、模擬退火算法等，這類算法通過大量迭代得到較為優化的解，但這往往是以時間復雜度為代價，而且易陷入局部最優解，難以應用到大規模快速的IP核映射中，并且不能保證在短時間內獲得低能耗的映射結果。而且目前大部分的映射研究還是基于規則Mesh進行的。

發明內容

本發明的目的在于針對上述現有技術的不足，提出一種基于差分進化和捕食搜索策略的胖樹型片上網絡映射方法，以減少IP核映射運行時間、降低網絡能耗。

為實現上述目的，本發明的技術包括如下步驟：

(1)初始化操作

對映射結果進行初始化：隨機選擇一個映射排序作為映射結果s的初始解，令當前最優映射結果b＝s；

對限制數組進行初始化：定義解空間內以任意一個解作為中心的周圍的多個解組成限制數組，該數組中每個元素對應于該中心的一個鄰域的限制范圍，然后，在當前最優映射結果b的周圍設置限制總數為T的限制數組：R[0]，R[1]，...，R[T-1]，其中T取自然數，給定一個解b和一個限制R[i]，將圍繞b的一個受限鄰域表示為A(b，R[i])；

對中間變量進行初始化：令當前局部搜索所在的限制級數i₁＝0，當前限制級數內的搜索次數i₂＝0；

(2)將當前局部搜索所在的限制級數與設定的限制總數進行比較，如果當前局部搜索所在的限制級數i₁＜設定的限制總數T，則進行局部搜索，并初始化M個種群個體，利用差分進化方法對該初始種群迭代N次，其中N為所設定的差分進化的總迭代次數，將迭代得到的最優映射結果記為p，并轉步驟(3)；否則，將當前最優映射結果b作為最佳映射結果，并輸出；

(3)判斷迭代得到的最優映射結果是否在當前最優映射結果的受限鄰域內，如果迭代得到的最優映射結果p在當前最優映射結果b的受限鄰域A(b，R[i₁])內，則令映射結果s＝迭代得到的最優映射結果p，并轉步驟(4)；否則轉步驟(5)；