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

有效

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

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

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

步驟2、初始化兩個不同規模的螢火蟲種群，分別為TAM分配種群與順序分配種群，即在(0,M)開區間內，按照TAM分配個體編碼方式，隨機生成NP1個D維的TAM分配個體形成TAM分配種群；其中TAM分配個體編碼方式采用實數編碼方式，即：在隨機初始化TAM分配個體時舍去小數部分，并確保不存在未被分配IP核的空閑TAM，或者將IP核分配至系統中不存在的TAM編號，否則重新初始化；在此基礎上，針對每一個TAM分配個體，都在(0,1)開區間內，按順序分配個體編碼方式，隨機生成NP2個順序分配個體形成順序分配種群；其中順序分配個體編碼方式采用二維矩陣編碼方式，即：首先，通過TAM分配個體確定各個IP核被劃分至哪條TAM；接著，在固定TAM分配的情況下，對每條TAM上IP核的測試先后順序，用(0,1)區間內的小數進行隨機初始化；最后，根據升序重新排列IP核的順序，從而針對每個TAM分配個體產生一定數量的順序分配個體；其中M、NP1、NP2、D均為設定值，M為TAM條數，D為IP核數量，NP1≥NP2；

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

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

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

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

步驟4.3、比較步驟4.1所選出的螢火蟲優選變遷發生序列個體和步驟4.2所選出的差分優選變遷發生序列個體的適應度值，并將兩者中適應度值較小的個體作為最優變遷發生序列個體進入步驟4.4；

步驟4.4、采用混沌優化方法，對步驟4.3所選出的最優變遷發生序列個體進行單維結合多維的混沌擾動更新，得到本次迭代的最優TAM分配個體與最優順序分配個體的組合；即：

步驟4.4.1、設置最大混沌局部搜索次數M_s，初始時混沌局部搜索次數k＝1；

步驟4.4.2、判斷混沌局部搜索次數k的奇偶：

若混沌局部搜索次數k為奇數，則對最優變遷發生序列個體的某一維進行混沌擾動，得到1個混沌個體，并將該混沌個體保存至混沌種群中；

若混沌局部搜索次數k為偶數，則對最優變遷發生序列個體的每一維進行混沌擾動，得到1個混沌個體，并將該混沌個體保存至混沌種群中；

步驟4.4.3、判斷混沌局部搜索次數k是否達到最大混沌局部搜索次數M_s，若是，則轉至步驟4.4.4；否則，令k加1，轉至步驟4.4.2；

步驟4.4.4、選出當前混沌種群中適應度值最小的混沌個體作為優選混沌個體；

步驟4.4.5、若優選混沌個體的適應度值小于最優變遷發生序列個體的適應度值，則用該優選混沌個體位置替換原最優變遷發生序列個體；否則保留原最優變遷發生序列個體不變；

步驟4.4.6、將當前最優變遷發生序列個體作為本次迭代的最優TAM分配個體與最優順序分配個體的組合；

步驟5、判斷當前迭代是否達到混沌差分螢火蟲算法的最大迭代次數：沒達到則返回步驟3，進入下一次迭代尋優；若達到，則輸出當前迭代所得到的最優變遷發生序列個體，作為最佳TAM分配與順序分配方案。

2.根據權利要求1所述的基于Petri網與混沌差分螢火蟲算法的3D NoC測試規劃方法，步驟1中，所建立的增廣時延變遷Petri網模型在原型Petri網的基礎之上，為每個變遷賦予時延與功耗，并增添一種從庫所引向變遷有控制作用的抑止弧。