[發明專利]一種基于神經網絡和序列對的布圖規劃面積最優方法

在審

• 申請號: 202210324355.0
• 申請日: 2022-03-30
• 公開（公告）號: CN114707460A
• 公開（公告）日: 2022-07-05
• 發明（設計）人: 黃益豪;蔡述庭;邢延;熊曉明
• 申請（專利權）人: 廣東工業大學
• 主分類號: G06F30/392
• 分類號: G06F30/392;G06F30/27;G06K9/62;G06N3/04;G06N3/08;G06F111/06
• 代理公司: 廣東廣信君達律師事務所 44329
• 代理人: 熊冰

1.一種基于神經網絡和序列對的布圖規劃面積最優方法，其特征在于，包括：

構建電路模塊數量為n的數字集成電路布圖規劃數據庫，該數據庫中的數據用于完整表示一個布圖規劃，由四個數組組成：其中一個數組W存儲n個模塊的寬度、一個數組H存儲n個模塊的高度，另外兩個數組Splus和Smin代表最優面積序列對；

將布圖規劃中序列對表示的布圖轉化為機器學習中的分類問題，包括：從數字集成電路布圖規劃數據庫里抽取一組數據[W,H,Splus,Smin]，將序列對Splus和Smin分別存儲在S₁和S₂中；計算出數組S₁和數組S₂中n個元素所構建的n個標簽值index，同時創建正序列對數組P和負序列對數組M用于儲存已經確定位置的元素，未確定位置的元素用-1代替；然后，輸入特征X：{W，H，P，M}和標簽index組成的訓練數據對被寫入新的數據庫，此數據庫將用于神經網絡模型訓練；

采用多層感知機搭建神經網絡模型，整個模型從輸入到輸出依次為展開層、隱藏層和輸出層，模型的輸入特征是一個四維元素{W，H，P，M}；將所述新數據庫中的訓練數據輸入到模型得到預測結果，根據預測結果與標簽之間的差距計算損失量，使用反向傳播方法更新模型參數，進而縮小預測結果與標簽之間的差距，最終得到一個泛化性最優的模型作為訓練好的模型；

利用訓練好的模型對數組S₁和數組S₂中的元素進行預測，直至S1和S2數組已經沒有-1的元素，即完成序列對所有元素的位置預測，此序列對S₁、S₂為這n個模塊布圖規劃面積最優的解。

2.根據權利要求1所述的基于神經網絡和序列對的布圖規劃面積最優方法，其特征在于，所述構建電路模塊數量為n的數字集成電路布圖規劃數據庫，包括：

根據實際的應用場景選擇模塊的數量n和模塊尺寸的大小范圍range；

根據所述模塊的數量n和模塊尺寸大小范圍range，利用隨機函數隨機生成各模塊的具體尺寸，然后將各模塊的寬度和高度分別保存進寬度數組W和高度數組H；

使用兩個大小為n的數組Splus、Smin分別表示n個模塊序列對的正序列S₁、負序列S₂，數組Splus和Smin的初始值為b₀,b₁,b₂,...,b_n-1，其中b_i(i＝0,1,…n-1)表示模塊名；接著分別無序打亂數組Splus、Smin，最后將打亂得到的數組Splus和Smin作為n個模塊布圖規劃初始解；

利用模擬退火方法搜索面積最優的序列對，并將各模塊寬度數組W、高度數組H、布圖規劃面積最優面積序列對Splus、Smin保存到數字集成電路布圖規劃數據庫中。

3.根據權利要求2所述的基于神經網絡和序列對的布圖規劃面積最優方法，其特征在于，所述利用模擬退火方法搜索面積最優的序列對，包括：

模擬退火方法的輸入參數為最高溫度T、最低溫度t、冷卻因子alpha、各模塊寬度數組W、各模塊高度數組H、以及序列對數組Splus和Smin；模擬退火通過在數組Splus和Smin上擾動的方式尋找面積更小的解，擾動后的序列對數組為Splus_disturb、Smin_disturb，其中擾動方式為：隨機交換數組Splus、Smin中兩個相同元素的位置、隨機交換數組Splus中兩個元素、隨機交換數組Smin中兩個元素以及隨機打亂數組Splus、Smin；

在擾動完成之后，計算擾動后的數組Splus_disturb、Smin_disturb所代表的序列對的面積，如果該面積比數組Splus、Smin所代表的序列對的面積小，則將數組Splus_disturb、Smin_disturb分別賦予數組Splus、Smin，以達到將數組Splus_disturb、Smin_disturb作為最優解的目的；如果該面積比數組Splus、Smin所代表的面積大，則以概率exp(-delta/T)接受這個差解，否則丟棄；其中delta是兩個面積之差；當溫度低于最低溫度t結束模擬退火方法，最終將數組Splus、Smin作為n個模塊最優面積序列對。