[發(fā)明專利]SoC 集成電路自動布局設(shè)計中的模組、宏單元、標(biāo)準(zhǔn)單元同步布局的收斂方法和系統(tǒng)

無效

• 申請?zhí)枺?/td>: 200710093867.6
• 申請日: 2007-06-14
• 公開（公告）號: CN101145169A
• 公開（公告）日: 2008-03-19
• 發(fā)明（設(shè)計）人: 蔡震
• 申請（專利權(quán)）人: 上海芯域微電子有限公司
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種自動布局設(shè)計中的模組、宏單元、標(biāo)準(zhǔn)單元同步布局的收斂方法和系統(tǒng)，其特征在于集成電路版圖中包含引腳PAD組、模組(或稱軟模組)(Soft?Block)、宏單元(MacroCell)及標(biāo)準(zhǔn)單元(Standard?Cell)；引腳PAD組內(nèi)的空間為布局空間，布局空間與引腳PAD組間預(yù)留一定的空間用于電源及內(nèi)部部件與引腳之間的連線；模組內(nèi)的布局還未完成，其邊界可以改變；宏單元的面積、高度通常比較大，且邊界是確定的；標(biāo)準(zhǔn)單元具有統(tǒng)一高度的已設(shè)計完成的基本單元電路。

2.根據(jù)權(quán)利要求1所述的自動布局設(shè)計中的模組、宏單元、標(biāo)準(zhǔn)單元同步布局的收斂方法和系統(tǒng)，其特征在于對于所述的模組、宏單元、標(biāo)準(zhǔn)單元且具有相同或不同的幾何尺寸、互相連接，不具有在布局空間中的合法位置，需要自動地以最優(yōu)化的方法放置到布局空間中。

3.一種模組、宏單元、標(biāo)準(zhǔn)單元自動布局的收斂方法，使用權(quán)利2所述的布局系統(tǒng)，其特征在于具體步驟如下：

(1)標(biāo)準(zhǔn)單元集合提取

把關(guān)系密切的多個標(biāo)準(zhǔn)單元節(jié)點提取成一個集合(Cluster)，用集合當(dāng)作新的節(jié)點。

(2)4-分法分割給定的布局空間

把一個給定的布局空間平均地分成4等份，并計算出每個區(qū)域的中心位置作為布局時節(jié)點所處的坐標(biāo)。

(3)??初始布局

隨機(jī)地把所有節(jié)點一個一個地分布到以上所分的區(qū)域中的中心位置上，并確保每個區(qū)域中所分到的節(jié)點的總面積不會超過給定區(qū)域所容許的面積。

(4)??布局優(yōu)化

對所有節(jié)點在不同的區(qū)域中進(jìn)行交換，并計算交換后的目標(biāo)函數(shù)值，當(dāng)所有節(jié)點都交換一次后結(jié)束，并把具有最小目標(biāo)函數(shù)值的布局找出來作為結(jié)果，具體過程如下：

(4.1)計算當(dāng)前布局的目標(biāo)函數(shù)值，目標(biāo)函數(shù)一般有節(jié)點間的連線長度、時域延遲、連線密度等構(gòu)成；

(4.2)計算每一個節(jié)點對于當(dāng)前目標(biāo)函數(shù)值的貢獻(xiàn)值，并把其對于其他區(qū)域的貢獻(xiàn)值也計算出來，并按最大值至最小值遞降排序；

(4.3)選擇當(dāng)前排序中處于最前面的節(jié)點，并選擇與之函數(shù)值最大的一個區(qū)域，進(jìn)行節(jié)點交換，并保證相關(guān)區(qū)域的面積不超過區(qū)域所容許的極限，超過區(qū)域面積極限者不進(jìn)行交換處理；

(4.4)記錄每一次交換的過程，并計算此時的目標(biāo)函數(shù)值；

(4.5)重復(fù)過程(4.2)-(4.4)，直至所有的節(jié)點都遍歷一次且每個節(jié)點只遍歷一次；

(4.6)在交換過程的歷史記錄中，找出具有最小目標(biāo)函數(shù)值的交換位置，抹去該位置以后的所有交換，此位置之前的節(jié)點交換記錄即是找到最佳布局的過程。

(5)??模組與宏單元布局

對模組與宏單元在相應(yīng)的區(qū)域中進(jìn)行布局。具體步驟如下：

(5.1)標(biāo)記軟模組及宏單元，區(qū)分已布局的與未布局的；

(5.2)在所有未布局的模組及宏單元中進(jìn)行一次評估，評估的標(biāo)準(zhǔn)是在所有可放置模塊的空間中，對每一個模塊進(jìn)行一次試探性的放置，并計算其連線長度、擁擠程度、時域性能等指標(biāo)；

(5.3)對步驟(5.2)中的所有結(jié)果進(jìn)行排隊，在隊列中找出一個最適合的模塊進(jìn)行放置；

(5.4)重復(fù)步驟(5.2)和(5.3)，直至所有的模塊放置完畢。

(6)??標(biāo)準(zhǔn)單元集合布局

當(dāng)模組和宏單元布局后，進(jìn)行標(biāo)準(zhǔn)單元集合的布局，具體步驟如下：

(6.1)選擇一個區(qū)域，比如Q0區(qū)，并把標(biāo)準(zhǔn)單元集合從原來位置上卸下；

(6.2)把空置區(qū)域劃分成面積相當(dāng)?shù)?份或2份，劃分方式則根據(jù)空置區(qū)域的形狀，本例中為2份，并把集合節(jié)點隨機(jī)地分配到區(qū)域中，使得每個節(jié)點都有一個區(qū)域，但每個區(qū)域中的節(jié)點總面積不超過該區(qū)域所容許的總面積；

(6.3)調(diào)用步驟(4)的布局優(yōu)化過程，進(jìn)行標(biāo)準(zhǔn)單元集合的布局優(yōu)化過程；

(6.4)重復(fù)過程(6.1)至(6.3)，直至所有4個區(qū)域都完成；

(6.5)對于以上產(chǎn)生的每一個子區(qū)域，判別區(qū)域內(nèi)是否具有2個或以上的集合，如果是，則重復(fù)(6.1)至(6.4)的過程；

(6.6)重復(fù)過程(6.1)至(6.5)，直至每個子區(qū)域包含不超過1個集合，標(biāo)準(zhǔn)單元集合的布局過程結(jié)束。

(7)??產(chǎn)生N1個初始全局布局

(7.4)重復(fù)步驟(3)至(6)N0次，生成N0個初始布局，并記錄下來；

(7.5)按目標(biāo)函數(shù)評估N0個布局，并根據(jù)目標(biāo)函數(shù)值排隊；

(7.6)根據(jù)目標(biāo)函數(shù)排隊結(jié)果，保留最好的N1個布局，丟棄其他的布局結(jié)果。

(8)N1個初始全局布局的二次優(yōu)化

(8.1)對于步驟(7)中的布局結(jié)果，置模組和宏單元的布局狀態(tài)為“未布局”；

(8.2)重復(fù)步驟(5)和(6)N1次，產(chǎn)生N1個新的布局；

(8.3)按目標(biāo)函數(shù)評估N1個布局，并根據(jù)目標(biāo)函數(shù)值排隊；

(8.4)根據(jù)目標(biāo)函數(shù)排隊結(jié)果，保留最好的N2個布局為最終的一組全局布局，丟棄其他的布局結(jié)果，全局布局收斂結(jié)束。

(9)選擇一個最好的全局布局結(jié)果作為標(biāo)準(zhǔn)單元布局的起點，選擇過程可以是自動或人工。

(10)生成標(biāo)準(zhǔn)單元槽(ROW)。

(11)標(biāo)準(zhǔn)單元布局初始化

(11.1)計算標(biāo)準(zhǔn)單元槽的實際面積，并按步驟(2)的方法劃分布局區(qū)域；

(11.2)調(diào)用步驟(6)的過程對標(biāo)準(zhǔn)單元集合進(jìn)行布局；

(11.3)對每一個標(biāo)準(zhǔn)單元集合中的標(biāo)準(zhǔn)單元賦予隨機(jī)坐標(biāo)值，坐標(biāo)值得范圍必須在標(biāo)準(zhǔn)單元集合所處區(qū)域的坐標(biāo)范圍附近。

(12)標(biāo)準(zhǔn)單元布局

(12.1)定義一個布局4分區(qū)域，該區(qū)域應(yīng)包含完整的標(biāo)準(zhǔn)單元槽，并在上下含有相同數(shù)目的標(biāo)準(zhǔn)單元槽；

(12.2)把以上區(qū)域放在包含標(biāo)準(zhǔn)單元槽的一個起始位置；

(12.3)把落在該區(qū)域中的標(biāo)準(zhǔn)單元放入相關(guān)的子區(qū)域中，調(diào)用步驟(4)的優(yōu)化過程，使得標(biāo)準(zhǔn)單元在該子區(qū)域中的位置達(dá)到優(yōu)化分配；

(12.4)移動以上布局4分區(qū)域，調(diào)用步驟(12.3)，直到標(biāo)準(zhǔn)單元布局區(qū)域內(nèi)的所有位置都被覆蓋到后結(jié)束該過程；

(12.5)縮小布局4分區(qū)面積，重復(fù)(12.2)至(12.4)的過程，直至布局4分區(qū)的高度小于2個標(biāo)準(zhǔn)單元槽高度而結(jié)束；