[發明專利]基于多目標遺傳算法的片上網絡內存控制器布局方法

有效

• 申請號: 202011054962.7
• 申請日: 2020-09-29
• 公開（公告）號: CN112181867B
• 公開（公告）日: 2022-07-26
• 發明（設計）人: 魏雯婷;李林峰;顧華璽;王康
• 申請（專利權）人: 西安電子科技大學
• 主分類號: G06F12/0811
• 分類號: G06F12/0811;G06F15/173;G06N3/12;G06N20/00
• 代理公司: 陜西電子工業專利中心 61205
• 代理人: 田文英;王品華

1.一種基于多目標遺傳算法的片上網絡內存控制器布局方法，其特征在于，進行建模預處理，將片上網絡的布局形式轉化為二進制矩陣；計算二進制矩陣中“0”、“1”節點間的平均曼哈頓距離f₁、各節點與其最近“0”之間的曼哈頓距離的方差f₂，以及各行列的“0”數量方差f₃；將f₁，f₂和f₃作為多目標遺傳算法的適應度函數；對算法中的交叉和變異過程做修改，滿足約束條件并保證交叉變異的隨機性和產生優秀子代的效果；完成搜索后得到模型最優布局集，使用黃金分割法結合全系統仿真篩選出實際最優布局，該方法的步驟包括如下：

(1)將一種片上網絡的布局形式轉化為二進制矩陣：

1a)將有n個路由器的片上網絡布局形式以Mesh拓撲相連，選擇Mesh網絡中m個位置連接內存控制器(mn)，若這m個位置與已有布局形式中內存控制器的位置重合，則重新創建布局形式，若這m個位置與已有布局形式中內存控制器的位置不重合，則新布局創建成功，各路由器繼續分別連接一個本地處理器；

1b)將所創建布局形式轉化為二進制矩陣：對應拓撲定義一個的空矩陣，定義空矩陣中s個位置對應1a)中連接內存控制器的m個路由器的位置，s＝m，將這s個位置賦值為“0”，將空矩陣中n-s個剩余位置賦值為“1”，“1”表示在片上網絡中僅連接處理器核的路由器的位置，由此將該布局形式的位置信息轉化成的二進制矩陣；

(2)計算平均曼哈頓距離：

2a)計算每個節點與每個“0”對應位置之間的曼哈頓距離；

2b)按照公式計算平均曼哈頓距離，其中，∑表示求和操作，H(i,j)表示第i個節點到第j個“0”的曼哈頓距離；

(3)按照下式，計算各節點與其最近“0”之間的曼哈頓距離的方差f₂：

其中，H(i,i_n0)表示第i個節點到最近的“0”的距離，即到i_n0的距離；

(4)按照下式，計算二進制矩陣中行和列的“0”數量方差f₃：

其中，y表示二進制矩陣行的總數，z表示二進制矩陣列的總數，p表示行的序號，q表示列的序號，N(p)表示二進制矩陣中第p行“0”的個數，M(q)表示二進制矩陣中第q行“0”的個數，μ₂表示二進制矩陣中行和列的“0”個數的平均值；

(5)將該二進制矩陣平鋪為w位的二進制序列，w＝n；將f₁、f₂和f₃依次添加到二進制序列末尾后作為一個布局個體；

(6)重復執行步驟(1)-(5)100次，將得到的100個布局個體組成一個100行w+3列的布局種群p_a；

(7)使用多目標遺傳算法求模型最優布局集：

7a)將變異率設置為0.2、交叉率設置為0.8；

7b)對布局種群p_a中所有布局進行非支配排序和擁擠度排序；得到各布局的非支配等級和擁擠度值；

7c)依據各布局的非支配等級和擁擠度值，進行錦標賽選擇得到種群p_b；

7d)對種群p_b依次進行交叉、變異操作，得到種群p_c；種群p_c中的二進制矩陣被更新；采用與步驟(2)相同的方法，計算更新后的二進制矩陣的平均曼哈頓距離；采用與步驟(3)相同的方法，計算更新后的二進制矩陣的各節點與其最近“0”之間的曼哈頓距離的方差；采用與步驟(4)相同的方法，計算更新后的二進制矩陣的各行列“0”數量的方差；接著進行父代子代種群合并得到下一個種群p_d，再次對種群p_d中的布局進行非支配排序和擁擠度排序，利用求出的非支配等級和擁擠度值進行精英策略操作，得到種群p_e；

所述的精英策略操作指的是，在合并父代子代后的200個個體中，根據Pareto等級從低到高的順序，將整個等級的種群放入下一代種群p_n，直到某一級該級個體不能全部放入p_n，將該級個體根據擁擠度從大到小排列，依次放入p_n，直到p_n填滿數量100；

7e)重復步驟7c)到7d)600次，將得到的100個模型最優布局組成模型最優布局集；

(8)篩選實際最優布局：

使用黃金分割法，結合最優布局集的全系統仿真，對模型最優布局集進行搜索，得到實際最優布局。