[發(fā)明專利]基于最優(yōu)適應(yīng)啟發(fā)式序列與多目標(biāo)組織進(jìn)化的集成電路布圖方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310733370.1
• 申請(qǐng)日: 2013-12-24
• 公開（公告）號(hào): CN103714210A
• 公開（公告）日: 2014-04-09
• 發(fā)明（設(shè)計(jì)）人: 劉靜;焦李成;朱園;王景潤(rùn);馬文萍;馬晶晶
• 申請(qǐng)（專利權(quán)）人: 西安電子科技大學(xué)
• 主分類號(hào): G06F17/50
• 分類號(hào): G06F17/50
• 代理公司: 西安吉盛專利代理有限責(zé)任公司 61108
• 代理人: 張培勛

1.一種基于最優(yōu)適應(yīng)啟發(fā)式序列與多目標(biāo)組織進(jìn)化的集成電路布圖方法，其特征是：具體步驟如下：

步驟101：開始基于最優(yōu)適應(yīng)啟發(fā)式序列與多目標(biāo)組織進(jìn)化的集成電路布圖方法；

步驟102：參數(shù)設(shè)定：最大進(jìn)化代數(shù)T，種群規(guī)模num，外部Pareto集規(guī)模N_p，一個(gè)合法組織所允許的最大規(guī)模num_max，最優(yōu)適應(yīng)度Best，t為大于或等于0的整數(shù)，表示進(jìn)化到第t代；

步驟103：初始化每個(gè)個(gè)體，更新最優(yōu)值Best，令t=0，采用隨機(jī)生成的方法產(chǎn)生模塊的放置順序，模塊的長(zhǎng)寬比序列，芯片的初始化寬度；

步驟104：循環(huán)調(diào)用基于最優(yōu)適應(yīng)啟發(fā)式序列的算法對(duì)每個(gè)模塊個(gè)體進(jìn)行編碼和解碼；

步驟105：使每個(gè)個(gè)體成為一個(gè)組織，將分裂算子作用在組織上，分裂算子根據(jù)條件:

(org_p.num＞num_max)or{(1＜o(jì)rg_p.num≤num_max)and(U(0,1)＜o(jì)rg_p.num/N_member)}把一個(gè)組織orgp分裂成兩個(gè)非空組織，其中U(0,1)是0到1之間的一個(gè)任意值，N_member是所有組織中所有個(gè)體的總數(shù)，每個(gè)組織中的個(gè)體按適應(yīng)度從大到小進(jìn)行排列；

步驟106：將吞并算子作用在兩個(gè)組織上，隨機(jī)選擇兩個(gè)組織org_p1和org_p2，合并成組織org_c，org_p1和org_p2各自的Pareto解集為P1和P2，把P1和P2合并成一個(gè)Pareto集Ph，如果P1在Ph中占的比重大于P2在Ph中的比重，則組織org_p1獲勝，org_p1吞并org_p2；如果P1在Ph中占的比重小于P2在Ph中的比重，則組織org_p1獲勝，org_p2吞并org_p1；如果P1在Ph中占的比重與P2在Ph中的比重相等，則任取一個(gè)吞并另一個(gè)；其具體規(guī)則如下：

假設(shè)組織org_p1吞并org_p2成一個(gè)新的組織org_c，這個(gè)新的組織由三部分組成：

1）org_p1中的所有個(gè)體；

2）由org_p1和org_p2根據(jù)下面公式生成org_p2.num/2個(gè)新的個(gè)體member_new1：

令0≤i≤org_p2.num/2,0≤j≤n，member_new1[i].b＝org_p2.member[0].b

membernew1[i].p[j]=orgp2.member[0].p[j]if(orgp1.member[0].p[j]=orgp2.member[i].p[j])=andorgp1.member[0].p[j]else(U(0,1)=0)]]>

3）隨機(jī)生成org_p2.num/2個(gè)新個(gè)體member_new2；

步驟107：通過(guò)排序比較找出當(dāng)前種群的Pareto解集，其規(guī)模為Np，構(gòu)成外部集；

步驟108：將培訓(xùn)算子作用在從組織中選出的個(gè)體，培訓(xùn)算子對(duì)外部集中的每個(gè)個(gè)體進(jìn)行操作，以縮短非劣前段與Pareto最優(yōu)前端的距離，使非劣前段的分布更廣更均勻，對(duì)個(gè)體進(jìn)行擾動(dòng)，生成新個(gè)體，并計(jì)算新個(gè)體的兩個(gè)目標(biāo)函數(shù)值，如果新個(gè)體支配原來(lái)的個(gè)體，則用新的個(gè)體取代原個(gè)體；否則把新老個(gè)體都保留起來(lái)，形成偽Pareto集，最后對(duì)該集進(jìn)行排序選擇生成下一代的外部集；對(duì)培訓(xùn)后的個(gè)體進(jìn)行最優(yōu)啟發(fā)式序列編碼和解碼，從所有組織中找出Pareto解；其中對(duì)每個(gè)組織的代表個(gè)體進(jìn)行培訓(xùn)的具體規(guī)則如下：

對(duì)下面三步獨(dú)立進(jìn)行操作，每步執(zhí)行5次。

1）改變模塊的放置順序：對(duì)模塊b[i]（0≤i≤n），從b中選擇另一個(gè)模塊與其交換位置；

2）改變模塊的長(zhǎng)寬比：對(duì)長(zhǎng)寬比p[j]（0≤j≤n），用[min?h_w，max?h_w]中的任意值替換它；

3）改變芯片的寬度：隨機(jī)生成一個(gè)正實(shí)數(shù)代替W，每次改變后都可以得到一個(gè)新的個(gè)體，如果新的個(gè)體的COST小于選出的代表的COST，則用新的個(gè)體代替原來(lái)的個(gè)體，否則保留原有個(gè)體；

培訓(xùn)完以后，將培訓(xùn)的個(gè)體標(biāo)記為1，表示該個(gè)體已經(jīng)培訓(xùn)過(guò)；

步驟109：用最優(yōu)適應(yīng)啟發(fā)式進(jìn)行編碼和解碼每個(gè)個(gè)體，找出最優(yōu)個(gè)體；

步驟110：如果滿足結(jié)束條件，即超過(guò)最大進(jìn)化代數(shù)，則轉(zhuǎn)向步驟111；否則，令t自加1，并轉(zhuǎn)向步驟105；

步驟111：輸出布圖結(jié)果；

步驟112：結(jié)束基于最優(yōu)適應(yīng)啟發(fā)式與多目標(biāo)組織進(jìn)化的集成電路布圖方法。

2.根據(jù)權(quán)利要求1所述的基于最優(yōu)適應(yīng)啟發(fā)式序列與組織進(jìn)化的集成電路布圖方法，其特征在于：所述步驟104，包括如下步驟：

步驟201：開始基于最優(yōu)適應(yīng)啟發(fā)式的算法，對(duì)模塊進(jìn)行編碼和解碼；

步驟202：第一個(gè)模塊b[0]被放在第一象限的左下角，它的長(zhǎng)寬比為p[0]；芯片的初始化寬度為W，令i=0；

步驟203：每個(gè)模塊都遵循左下緊布局原則，放置在頂線上最低最適合的位置上；只有一種情況例外：當(dāng)最低線段和次最低線段相鄰，且最低段在次最低段的左邊時(shí)，模塊遵循右下緊布局原則放置。軟矩形模塊的最低最適合的位置滿足兩個(gè)條件：(1)在頂線上，該位置是所有能放置該軟矩形模塊的最低段；(2)在長(zhǎng)寬比允許的限度內(nèi)，軟矩形模塊能放置在該位置上，并且盡可能占滿該位置，使它留下的空白區(qū)最少；

步驟204：判斷ylowest是否為0，ylowest為放置第一排模塊；如果ylowest為0，轉(zhuǎn)向步驟205；否則，轉(zhuǎn)向步驟207；

步驟205：軟矩形模塊的形狀由它的初始長(zhǎng)寬比決定；

步驟206：放置模塊，當(dāng)被放置的模塊的右邊界超出了芯片的右邊界即Rside的限制時(shí)，用該模塊的右邊界更新Rside的值，至此，第一排模塊放置完成，以后再放置的任何模塊都不允許超出Rside的限制；轉(zhuǎn)向步驟209；

步驟207：調(diào)整軟矩形模塊的長(zhǎng)寬比；

步驟208：為模塊尋找最低最合適的位置放置模塊；依次在最低線段、次最低線段以及最低線段和次最低線段相鄰的三種情況中尋找，如果找到，則放置該模塊；否則，抬高最低線段，重新開始尋找，直到模塊被放置在最優(yōu)合適的位置上；

步驟209：每放置一個(gè)模塊或抬高最低線段后，都更新頂線；

步驟210：i=i+1；

步驟211：如果i<n，轉(zhuǎn)向步驟203；否則，轉(zhuǎn)向步驟212；

步驟212：被放置完時(shí)，結(jié)束最優(yōu)適應(yīng)啟發(fā)式序列的編碼和解碼。