[發(fā)明專利]一種兩步模迭代法應用于混合尺寸單元電路設計

在審

• 申請?zhí)枺?/td>: 202210327630.4
• 申請日: 2022-03-29
• 公開（公告）號: CN114970435A
• 公開（公告）日: 2022-08-30
• 發(fā)明（設計）人: 周晨璨;施佺;曹陽;邱潔
• 申請（專利權）人: 南通大學
• 主分類號: G06F30/392
• 分類號: G06F30/392;G06F17/16;G06F17/12
• 代理公司: 南京瑞弘專利商標事務所(普通合伙) 32249
• 代理人: 許潔

本發(fā)明提供了基于兩步模系矩陣分裂迭代的混合尺寸單元電路設計方法，首先對多倍行高單元預處理成單倍行高子單元，然后對所有單元建立網(wǎng)絡流，對其進行擴散，避免局部擁擠，接著將合法化問題等價為凸二次規(guī)劃，并將二次規(guī)劃問題等價地轉(zhuǎn)換成線性互補問題，利用兩步模系矩陣分裂迭代法求解，最后將多倍行高標準單元進行復原并放置到行中的可放置位上，并對余下的非法單元進行處理；與現(xiàn)有技術相比，本發(fā)明通過一種前向掃描和向后掃描技術，通過選取兩對合適的分裂矩陣M₁,N₁,M₂,N₂，能夠加快迭代過程的收斂速度，快速得到合法化問題的高質(zhì)量鄰域解，能減少線性互補問題求解過程中的迭代次數(shù)以及運行時間，進一步提升布局階段設計效率。

技術領域

本發(fā)明涉及超大規(guī)模集成電路物理設計自動化領域，具體涉及一種兩步模迭代法應用 于混合尺寸單元電路設計，可用于混合尺寸標準單元電路的合法化過程。

背景技術

多年來，單倍行高標準單元布局一直占據(jù)著主導地位。然而，隨著高級技術節(jié)點設要 求的復雜性增加，混合尺寸標準單元電路布局逐漸被引入到超大規(guī)模集成電路設計中。通 常，如反相器這類簡單的單元被設計成單倍行高，而觸發(fā)器這類復雜單元則被設計成多倍 行高；在物理設計綜合中，布局階段的目標是確定各個單元在版圖中的位置以及方向。

布局問題是NP-難問題，且每個電路設計中的標準單元數(shù)據(jù)龐大，使得解空間爆炸， 精確求解幾乎變得不可能；因此通常采用一些近似方法來獲得近似最優(yōu)解，以避免直接求 解的計算時間復雜度；然而，如何快速、高效地逼近最優(yōu)解是當前亟待解決的一個問題。

為簡化布局階段的設計復雜度，通常將該階段進行分解成三個子階段，即全局布局、 合法化、詳細布局階段。全局布局階段中會暫時忽略單元間重疊，以最小化線長為目標； 合法化則是消除上一階段中產(chǎn)生的單元重疊，并間單元對齊到行中的可放置位置中去；詳 細布局階段會通過單元交換等操作來進一步細化前序階段的布局結果；由于標準單元的異 質(zhì)結構，使得合法化問題變得愈加復雜；現(xiàn)有的合法化算法主要有啟發(fā)式算法、解析式算 法；啟發(fā)式算法具有求解速度快的優(yōu)點，然而容易陷入局部最優(yōu)解；解析式算法則能從全 局角度對問題模型進行分析，更有可能產(chǎn)生高質(zhì)量鄰域解；陳建利等(CN106971042 A) 提出了將合法化問題中二次規(guī)劃問題轉(zhuǎn)化成線性互補問題，并應用模系矩陣分裂迭代法對 線性互補問題進行求解；從全局角度出發(fā)，進一步提高求解線性互補問題的收斂速度，但 是其迭代次數(shù)以及運行時間都比較長，布局階段設計效率低。

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

發(fā)明目的：本發(fā)明的目的是為了解決現(xiàn)有技術中的不足，本發(fā)明提供一種兩步模迭代 法應用于混合尺寸單元電路設計，該方法由前向掃描和向后掃描組成，能減少線性互補問 題求解過程中的迭代次數(shù)以及運行時間，進一步提升布局階段設計效率。

為了實現(xiàn)以上目的，本發(fā)明提供一種兩步模迭代法應用于混合尺寸單元電路設計，用于混 合尺寸標準單元電路的合法化過程，包括如下步驟：

S1:對標準單元進行預處理，將多倍行高標準單元分割為多個單倍行高標準子單元；

S2:將標準單元進行擴散；

S3:將混合尺寸標準單元合法化問題表示為二次規(guī)劃數(shù)學模型；

S4:將二次規(guī)劃模型轉(zhuǎn)換成線性互補問題；

S5:利用兩步模系矩陣分裂迭代法求解線性互補問題；

S6:將多倍行高標準單元分割成的子單元的x坐標進行統(tǒng)一，并對齊到行中的可放置 位上；

S7:對剩余的非法單元進行合法化處理。