基於差分進化和捕食搜索策略的胖樹型片上網絡映射方法
2023-04-22 23:23:41 2
專利名稱：基於差分進化和捕食搜索策略的胖樹型片上網絡映射方法
技術領域：
本發明屬於網絡技術領域，涉及系統級晶片設計和片上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
，R[l]，. . .，R[T_1]，其中T取自然數， 給定一個解b和一個限制R[i]，將圍繞b的一個受限鄰域表示為A(b，R[i])；對中間變量進行初始化令當前局部搜索所在的限制級數I1 = 0，當前限制級數內的搜索次數i2 = o;(2)將當前局部搜索所在的限制級數與設定的限制總數進行比較，如果當前局部搜索所在的限制級數ii 每一限制等級內的最大搜索次數C，令當前局部搜索所在的限制級數I1 = h+1，當前限制級數內的搜索次數i2 = 0，並轉步驟(6)； 否則轉步驟⑵；(6)將當前局部搜索所在的限制級數與終止局部搜索的限制級數進行比較，如果當前局部搜索所在的限制級數I1 =終止局部搜索的限制級數L，則將當前局部搜索所在的限制級數I1設置為終止局部搜索的限制級數L與設定的限制總數T之間的一個限制級數值Lhigh,即令I1 = Lhigh,轉步驟⑵；否則直接轉步驟(2)。本發明與現有的技術相比具有如下優點1)本發明由於將捕食搜索策略引入到差分進化方法中，在限制數組的約束下，可以搜索很大的區域，很快跳出原來所限制的較小區域，同時跳出局部最優，從而克服了差分進化方法易陷入局部最優解的問題；2)本發明由於將差分進化方法與捕食搜索策略相結合，並應用到胖樹型片上網絡映射中，與現有的優化方法相比，得到了更優的能耗結果，而且縮短了映射的運行時間。
仿真結果表明，本發明不僅可快速實現從IP核到胖樹型拓撲結構中網絡節點的映射，而且能保證全網通信的低能耗。
圖1是現有視頻對象平面解碼VOPD的通信核圖；圖2是本發明的映射流程圖；圖3是現有的胖樹型拓撲結構示意圖；圖4是現有方法與本發明的映射結果對比示意圖
具體實施例方式以下以對圖1所示的16核視頻對象平面解碼VOPD通信核圖進行映射為例，對本發明進行詳細描述。為方便描述，本發明對視頻對象平面解碼VOPD的通信核圖中的每個IP核進行編號IP1，IP2，. . .，IP16，編號的順序不影響IP核的映射位置。視頻對象平面解碼VOPD的通信核圖及每個IP核的編號如圖1所示。圖1中，每個頂點表示一個IP核，頂點上的數字代表著IP核的編號，若某兩個頂點之間有邊存在，則表示這兩個IP核之間存在著通信關係， 邊的權重代表著這兩個IP核之間的通信量。參照圖2，本發明的具體實現步驟如下步驟1，初始化操作。1. 1)對映射結果進行初始化隨機選擇一個映射排序作為映射結果s的初始解， 該映射結果為通信核的一個隨機排序，例如16核網絡的一個初始解可選為s = [1,2,3,4, 5，6，7，8，9，10，11，12，13，14，15，16]，令當前最優映射結果匕=s ；1. 2)對限制數組進行初始化定義解空間內以任意一個解作為中心的周圍的多個解組成限制數組，該數組中每個元素對應於該中心的一個鄰域的限制範圍，然後，在當前最優映射結果b的周圍設置限制總數為T的限制數組RW]，R[l]，...，R[T-1]，其中T取自然數，給定一個解b和一個限制R[i]，將圍繞b的一個受限鄰域表示為A(b，R[i])；所述的在當前最優映射結果b的周圍設置限制總數為T的限制數組的具體實施步驟為1. 2a)在當前最優映射結果b的周圍利用2_opt算法搜索T_1次，其中T表示設定的限制總數，得到T-I個映射結果及其對應的能耗值，並將該T-I個映射結果所對應的能耗值按照升序排列，所述的能耗值是參照圖3胖樹型拓撲結構按照公式E = Σ WIPi,IPJ X efflap(IPi), fflap(iPj)進行計算的，其中Wipi,IPj表示兩個IP核IPi與IPj之間的通信量，emap(IPi),map(IPj)表示從IPi所要映射的處理節點map (IPi)到IPj所要映射的處理節點map (IPj)傳輸Ibit數據所需的平均能耗；圖3中，胖樹型拓撲結構是由η行2(η_ 列路由器組成，每個路由器可用二維坐標 (x，y)表示，其中χ取值範圍為O-(n-l)，y取值範圍為Ο-Ο^Μ)，第0行的每個路由器連接兩個處理節點，每個處理節點可以放置一個IP核，因此η行的胖樹型網絡可以連接的處理節點數為2η，第1行的路由器向下與兩個第0行的路由器相連，因此，通過第1行的每個路由器可以到達4個處理節點，而第2行的路由器向下與兩個第1行的路由器相連，因此，通過第2行的每個路由器可以到達8個處理節點，依此類推，通過第r行的路由器可以到達的處理節點數為；胖樹型拓撲結構中採用的路由策略為來自處理節點的通信數據首先向相連接的第O行的路由器即它的父節點轉發，當路由器節點收到一個數據包時，若該數據包的目的節點位於它的子樹中，則向下轉發至相應的孩子節點，否則繼續向其父節點轉發； 本發明對每條路由路徑定義一個層次f，它的值取為路由路徑所經過的行數最大的路由器所在的行數，圖3中的路由路徑的層次f有四種取值，相應的能耗也有以下四種情況第一種情況，f = 0，說明兩個處理節點連接在第0行的同一個路由器上，路由路徑中包括一個路由器，沿該路由路徑從IPi所要映射的處理節點map (IPi)到IPj所要映射的處理節點map (IPj)傳輸Ibit數據所需的平均能耗為emap(IPi),map(IPj) = Ek，其中Ek表示單個路由器傳輸Ibit數據所需的平均能耗；第二種情況，f = 1，路由路徑中包括三個路由器和兩條第0行與第1行路由器相連的鏈路，沿該路由路徑從IPi所要映射的處理節點map (IPi)到IPj所要映射的處理節點 map (IPj)傳輸Ibit數據所需的平均能耗為^^所-哪=^Er +IEh，其中&表示第0行與第1行路由器相連的單條鏈路傳輸Ibit數據所需的平均能耗；第三種情況，f = 2，路由路徑中包括五個路由器和兩條第0行與第1行路由器相連的鏈路以及兩條第1行與第2行路由器相連的鏈路，沿該路由路徑從IPi所要映射的處理節點map (IPi)到IPj所要映射的處理節點map (IPj)傳輸Ibit數據所需的平均能耗為 ^mapiIPrlmapiIm =5ER +2^ ^L2，其中K2表示第1行與第2行路由器相連的單條鏈路傳輸 Ibit數據所需的平均能耗；第四種情況，f = 3，路由路徑中包括七個路由器、兩條第0行與第1行路由器相連的鏈路、兩條第1行與第2行路由器相連的鏈路以及兩條第2行與第3行路由器相連的鏈路，沿該路由路徑從IPi所要映射的處理節點map (IPi)到IPj所要映射的處理節點 map (IPj)傳輸Ibit數據所需的平均能耗為^= +2Eh +2ELi +2Eh，其中\ 表示第2行與第3行路由器相連的單條鏈路傳輸Ibit數據所需的平均能耗；1. 2b)把排序後的這T-I個能耗值依次賦給限制數組R[l]，R[2]，. . .，R[T_1]，而 R
取為當前最優映射結果b所對應的能耗值；1. 3)對中間變量進行初始化令當前局部搜索所在的限制級數I1 = 0，當前限制級數內的搜索次數i2 = 0。步驟2，將當前局部搜索所在的限制級數與設定的限制總數進行比較，如果當前局部搜索所在的限制級數I1 >設定的限制總數T，則將當前最優映射結果b作為最佳映射結果，並輸出；否則，進行局部搜索，並初始化M個種群個體，利用差分進化方法對該初始種群迭代N次，其中N為所設定的差分進化的總迭代次數，該差分進化方法的主要操作如下2. 1)變異操作變異操作是採取兩種變異操作模式進行的，即DE/best/Ι和DE/rand/Ι模式，通過下面公式進行變異得到新個體
權利要求
1.一種基於差分進化和捕食搜索策略的胖樹型片上網絡映射方法，包括如下步驟(1)初始化操作對映射結果進行初始化隨機選擇一個映射排序作為映射結果S的初始解，令當前最優映射結果b = S ；對限制數組進行初始化定義解空間內以任意一個解作為中心的周圍的多個解組成限制數組，該數組中每個元素對應於該中心的一個鄰域的限制範圍，然後，在當前最優映射結果b的周圍設置限制總數為T的限制數組:R
，R[l]，· · ·，R[T-1]，其中T取自然數，給定一個解b和一個限制R[i]，將圍繞b的一個受限鄰域表示為A(b，R[i])；對中間變量進行初始化令當前局部搜索所在的限制級數I1 = 0，當前限制級數內的搜索次數i2 = 0 ；(2)將當前局部搜索所在的限制級數與設定的限制總數進行比較，如果當前局部搜索所在的限制級數I1 每一限制等級內的最大搜索次數C，令當前局部搜索所在的限制級數I1 = h+1，當前限制級數內的搜索次數i2 = 0，並轉步驟(6)；否則轉步驟⑵；(6)將當前局部搜索所在的限制級數與終止局部搜索的限制級數進行比較，如果當前局部搜索所在的限制級數I1 =終止局部搜索的限制級數L，則將當前局部搜索所在的限制級數I1設置為終止局部搜索的限制級數L與設定的限制總數T之間的一個限制級數值 Lhigh,即令I1 = Lhigh,轉步驟(2)；否則直接轉步驟(2)。
2.根據權利要求1所述的基於差分進化和捕食搜索策略的胖樹型片上網絡映射方法， 其中步驟(1)所述的在當前最優映射結果b的周圍設置限制總數為T的限制數組，按如下步驟進行la)在當前最優映射結果b的周圍利用2-opt算法搜索T-I次，其中T表示設定的限制總數，得到T-I個映射結果及其對應的能耗值，並將該T-I個映射結果所對應的能耗值按照升序排列；lb)把排序後的這T-I個能耗值依次賦給限制數組R[1]，R[2]，· · ·，R[T-1]，而R
取為當前最優映射結果b所對應的能耗值。
3.根據權利要求1所述的基於差分進化和捕食搜索策略的胖樹型片上網絡映射方法， 其中步驟(2)所述的利用差分進化方法，包括變異操作、交叉操作和選擇操作所述的變異操作，是採取兩種變異操作模式進行的，即DE/best/Ι和DE/rand/Ι模式， 通過下面公式進行變異得到新個體
全文摘要
本發明公開了一種基於差分進化和捕食搜索策略的胖樹型片上網絡映射方法。其步驟為(1)初始化當前最優映射結果，並定義解空間內以任意一個解作為中心的周圍的多個解組成限制數組；(2)在當前最優映射結果周圍設置限制總數為T的限制數組R
，R[1]，...，R[T-1]，定義當前限制變量為R[i]；(3)在當前限制變量R[i]周圍採用差分進化方法搜索，若找到更優解，則更新當前最優映射結果並返回步驟(2)，否則繼續步驟(4)；(4)更新當前限制變量i＝i+1，若i＜T-1，則返回步驟(3)，否則輸出當前最優映射結果。本發明通過限制的調節克服了局部最優問題，大大降低了網絡能耗並減少了映射運行時間，可用於低能耗、快速的大規模IP核在胖樹型片上網絡中的映射。
文檔編號H04L12/56GK102325089SQ20111027658
公開日2012年1月18日 申請日期2011年9月19日 優先權日2011年9月19日
發明者張碧霞, 楊銀堂, 王琨, 鄧植, 顧華璽 申請人:西安電子科技大學