[發明專利]基于Petri網與混沌差分螢火蟲算法的3D NoC測試規劃方法

有效

• 申請號: 201810927745.0
• 申請日: 2018-08-15
• 公開（公告）號: CN109102062B
• 公開（公告）日: 2020-03-13
• 發明（設計）人: 胡聰;鄭嵐;周甜;朱愛軍;許川佩;朱望純;萬春霆
• 申請（專利權）人: 桂林電子科技大學
• 主分類號: G06N3/00
• 分類號: G06N3/00;G01R31/28
• 代理公司: 桂林市持衡專利商標事務所有限公司 45107
• 代理人: 陳躍琳

本發明公開一種基于Petri網與混沌差分螢火蟲算法的3D NoC測試規劃方法，首先通過在原型Petri網的基礎之上增加時延與帶抑止弧的概念，能有效描述測試規劃中的IP核調度問題、簡化模型；模型建立后，為了在Petri網的變遷發生序列集合中實施高效尋優，對基本螢火蟲算法進行了兩處改進，即分別采用單維結合多維的混沌優化方法，使基本螢火蟲算法具備精細的局部尋優能力，采用與差分進化算法之間的信息共享機制，增強基本螢火蟲算法的全局尋優能力。將實驗結果與其他測試方法的實驗結果進行比較，結果顯示本發明測試方法在測試時間與程序運行時間方面都展現出較明顯的優勢。

技術領域

本發明涉及三維片上網絡(three Dimensional Network-on-Chip，3D NoC) 技術領域，具體涉及一種基于Petri網與混沌差分螢火蟲算法的3D NoC測試規劃方法。

背景技術

三維片上網絡通過硅通孔(Through Silicon Via，TSV)技術，將二維片上網絡(Network-on-Chip，NoC)結構進行層間銜接，有效緩解了制造工藝水平與設計能力之間的“剪刀差”。雖然3D NoC具備互連線短、集成度高、功耗及延遲低、可拓展性及電路抗噪聲能力強等種種優勢，但與此同時，單位芯片面積上包含資源內核數目的增長、芯片系統結構復雜度的攀升，將對芯片的并行測試效率帶來新一輪的考驗。因此，以縮減測試成本為目標，考慮軟硬件等多種約束條件的限制，如何實施高效的并行傳輸與測試，成為一個NP難題，同時也具有較大研究價值。

由于Petri網能夠便捷地對分布式系統中的順序、同步、并發及沖突等現象進行描述，因此通過Petri網對3D NoC測試規劃問題建立模型，不僅可以通過圖形刻畫調度過程，同時易于觀察這一過程的動態變化。然而當系統規模不斷擴大時，通過可達標識圖求解Petri網將使得狀態空間矩陣的大小以指數規律急劇上升。

發明內容

本發明針對現有的測試規劃Petri網模型的狀態空間過大，測試規劃算法對測試時間尋優效果不佳的問題，提供一種基于Petri網與混沌差分螢火蟲算法的3D NoC測試規劃方法。

為解決上述問題，本發明是通過以下技術方案實現的：

基于Petri網與混沌差分螢火蟲算法的3D NoC測試規劃方法，具體包括步驟如下：

步驟1、根據3D NoC中每個資源內核的測試資源需求建立增廣時延變遷 Petri網模型，并計算增廣時延變遷Petri網模型的輸入矩陣、輸出矩陣以及狀態空間矩陣，確定初始標識與終止標識；

步驟2、初始化兩個不同規模的螢火蟲種群，分別為TAM分配種群與順序分配種群，即在(0,M)開區間內，按照TAM分配個體編碼方式，隨機生成 NP1個D維的TAM分配個體形成TAM分配種群；在此基礎上，針對每一個 TAM分配個體，都在(0,1)開區間內，按順序分配個體編碼方式，隨機生成 NP2個順序分配個體形成順序分配種群；其中M、NP1、NP2、D均為設定值， M為TAM條數，D為IP核數量，NP1≥NP2；

步驟3、根據TAM分配種群的TAM分配個體與順序分配種群的順序分配個體生成相應的變遷發生序列個體，并計算每一個變遷發生序列個體的適應度值即總變遷時延及功耗；

步驟4、采用混沌差分螢火蟲算法對變遷發生序列個體進行尋優和更新，尋找出最優變遷發生序列個體，即最優TAM分配個體與最優順序分配個體的組合；即：

步驟4.1、采用螢火蟲算法，更新變遷發生序列個體位置，得到螢火蟲算法在本次迭代中適應度值最小的變遷發生序列個體，即螢火蟲優選變遷發生序列個體；

步驟4.2、采用差分進化算法，更新變遷發生序列個體的位置，得到差分進化算法在本次迭代中適應度值最小的變遷發生序列個體，即差分優選變遷發生序列個體；