[發(fā)明專利]一種用于求解給定邊框約束的VLSI版圖設(shè)計方法

在審

• 申請?zhí)枺?/td>: 201710207178.7
• 申請日: 2017-03-31
• 公開（公告）號: CN106777849A
• 公開（公告）日: 2017-05-31
• 發(fā)明（設(shè)計）人: 陳建利;劉巖;朱自然;朱文興
• 申請（專利權(quán)）人: 福州大學(xué)
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 福州元創(chuàng)專利商標(biāo)代理有限公司35100
• 代理人: 蔡學(xué)俊

技術(shù)領(lǐng)域

本發(fā)明涉及VLSI物理設(shè)計自動化技術(shù)領(lǐng)域,特別是一種用于求解給定邊框約束的VLSI版圖設(shè)計方法。

背景技術(shù)

近年來，隨著集成電路制造工藝的迅速發(fā)展，集成電路產(chǎn)業(yè)已經(jīng)進(jìn)入了納米工藝時代，芯片的集成度進(jìn)一步提高，一塊芯片上所能集成的電路元件越來越多，對VLSI設(shè)計方法提出了更高的要求。版圖規(guī)劃是VLSI物理設(shè)計過程中非常重要的一個環(huán)節(jié)，對集成電路的性能指標(biāo)，如可布通性、時延特性、功耗、電路可靠性等有重大影響。隨著版圖規(guī)劃問題的約束不斷增多和芯片上單元個數(shù)的快速增長，對VLSI版圖規(guī)劃問題的算法設(shè)計提出了巨大的挑戰(zhàn)。因此，尋求更高效、更實用的集成電路版圖規(guī)劃設(shè)計算法具有重要的意義。

在是否考慮將模塊放置到給定的區(qū)域約束時，版圖規(guī)劃問題分為傳統(tǒng)版圖規(guī)劃問題和fixed-outline版圖規(guī)劃問題。傳統(tǒng)版圖規(guī)劃問題主要在滿足任何模塊都不重疊約束下，確定模塊的位置，使得布局的面積和模塊間的互連線長最小。Fixed-outline版圖規(guī)劃問題是在給定邊框約束和任何模塊都不重疊約束條件下確定模塊的位置，使得最終的布局面積和模塊間的互連線長度最小。換而言之，fixed-outline版圖規(guī)劃問題不僅要滿足任何模塊都不重疊的約束，而且還要滿足所有的模塊都要放置到給定的邊框內(nèi)。目前已經(jīng)證明了fixed-outline版圖規(guī)劃比傳統(tǒng)版圖規(guī)劃更加復(fù)雜。

用來解決VLSI版圖規(guī)劃問題的算法可分為以下兩類：基于迭代的版圖規(guī)劃設(shè)計方法和基于分析的版圖規(guī)劃設(shè)計方法。在這兩類方向中，通過實驗結(jié)果的對比，基于迭代的版圖規(guī)劃設(shè)計方法取得的布局效果較好，因而成為當(dāng)前主流布局工具所采用的方法。由于VLSI布局問題的規(guī)模很大，現(xiàn)有的基于構(gòu)造的版圖規(guī)劃設(shè)計工具很難直接求解。在迭代方法的VLSI版圖規(guī)劃設(shè)計算法中，主要采用啟發(fā)式策略，如模擬退火算法、遺傳算法和粒子群算法等等。在基于啟發(fā)式策略的迭代方法中，實驗結(jié)果證明模擬退火算法在處理版圖規(guī)劃設(shè)計問題時，能夠得到較好的版圖規(guī)劃結(jié)果。因此，模擬退火算法被認(rèn)為是啟發(fā)式策略迭代法中比較有效的一種算法。

目前，基于分析方法的版圖規(guī)劃算法主要采用線性規(guī)劃算法及混合線性規(guī)劃算法處理VLSI不可二劃分版圖規(guī)劃問題。根據(jù)學(xué)術(shù)上和工業(yè)界布局器的比較,基于迭代方法的版圖規(guī)劃布局工具取得的實驗結(jié)果最好。

發(fā)明內(nèi)容

本發(fā)明的目的在于提供一種用于求解給定邊框約束的VLSI版圖設(shè)計方法，以克服現(xiàn)有技術(shù)中存在的缺陷。

為實現(xiàn)上述目的，本發(fā)明的技術(shù)方案是：一種一種用于求解給定邊框約束的VLSI版圖設(shè)計方法，按照如下步驟實現(xiàn)：

步驟S1：將版圖規(guī)劃表示為B*-tree；

步驟S2：初始化所述步驟S1獲取的B*-tree為完全二叉樹，記為初始解I；

步驟S3：設(shè)置算法迭代次數(shù)iterative＝0，設(shè)置最大的迭代數(shù)目；

步驟S4：判斷所述初始解I是否為可行解；

步驟S5：通過一系列B*-tree擾動產(chǎn)生鄰居解；

步驟S6：對所述步驟S5中的鄰居解采用可行解策略，使得鄰居解滿足邊框約束；

步驟S7：采用混合模擬退火算法在解空間中搜索最優(yōu)解；

步驟S8：令iterative＝iterative+1；

步驟S9：重復(fù)所述步驟S5至所述步驟S8，直到迭代次數(shù)iterative大于預(yù)設(shè)的迭代數(shù)目。

在本發(fā)明一實施例中，在所述步驟S1中將版圖規(guī)劃表示為B*-tree，其中，樹形結(jié)構(gòu)中的每個節(jié)點都代表一個模塊，而且每個節(jié)點至多有兩個子節(jié)點。

在本發(fā)明一實施例中，在所述步驟S2中，所述初始化所述步驟S1獲取的B*-tree為完全二叉樹包括：除了樹結(jié)構(gòu)中的最后兩行的節(jié)點，每個父節(jié)點有兩個子節(jié)點。

在本發(fā)明一實施例中，在所述步驟S5中，對于解空間中每個解都由B*-tree表示，且所述一系列B*-tree的擾動方式包括：模塊旋轉(zhuǎn)、移動模塊到另一個區(qū)域以及交換兩個模塊。

在本發(fā)明一實施例中，在所述步驟S6中，通過可行解策略算法使所述所述步驟S5中獲取的鄰居解為可行解，且所述可行解策略算法采用如下步驟實現(xiàn)：

步驟S61：令j＝＝0；

步驟S62：while(初始解S是不可行的or j≤給定的數(shù)值)；

步驟S63：令j++；

步驟S64：通過一系列B*-tree的擾動產(chǎn)生新的解S₁。

其中，j表示可行解策略在實行過程中的迭代次數(shù)。