[發明專利]最小化平均和最大移動的混合高度單元合法化方法

有效

• 申請號: 201810542123.6
• 申請日: 2018-05-30
• 公開（公告）號: CN108804793B
• 公開（公告）日: 2021-11-26
• 發明（設計）人: 陳建利;朱文興;李興權;朱自然;陳宇航
• 申請（專利權）人: 福州大學
• 主分類號: G06F30/392
• 分類號: G06F30/392;G06F30/398
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

本發明涉及一種最小化平均和最大移動的混合高度單元合法化方法，把電路表示為超圖模型；將單元設置方向后，對齊到臨近且正確匹配的電源軌道行上；對多倍行高標準單元進行預處理，并通過對目標函數和約束的分析和重構，將混合高度標準單元合法化模型規劃為混合整數二次規劃模型；將混合整數二次規劃模型轉換成二次規劃模型；將二次規劃模型轉化為對應的線性互補模型；用基于模數的矩陣分裂迭代法來求解線性互補模型；進行行重分配以及對多倍行高標準單元進行復原；采用基于線性規劃的方法和Kuhn?Munkres算法對最小移動單元進行合法化。本發明提出的方法同時對所有的單元進行優化，可滿足目前VLSI的混合高度標準單元合法化階段的需求。

技術領域

本發明涉及VLSI混合高度標準單元合法化的自動化技術，特別是一種最小化平均和最大移動的混合高度單元合法化方法。

背景技術

隨著現代電路設計的日益復雜，標準單元通常根據面積、功率和速度等特性產生不同的單元高度。例如，更高的單元能夠給予更大的驅動力和更好的可布通性，以此同時需要更大的面積和功率成本。反之，較矮的單元的驅動力和可布通性較差，但所需要耗費的面積和功率成本較小。因此，為了滿足各種各樣的電路設計要求，混合高度標準單元的電路變得越來越流行，簡單的標準單元被設計為單倍行高的結構，而復雜的標準單元被設計為多倍行高的結構。為了保持現有全局布局的質量，一個理想的合法化方法應該使平均單元移動和最大單元移動都最小化。

一個現代的布局流程通常包括三個主要階段：(1)全局布局：允許單元之間有少量重疊，通過求解最小化線長及滿足一定約束的布局問題來產生單元的最佳位置；(2)合法化：將單元對齊到行上，并消除全局布局之后遺留的重疊，目標是最小化單元的移動量(或線長增加)；(3)詳細布局：在合法化的基礎上局部移動部分單元，進一步改善結果。由于異構的單元結構(較大的解空間)和額外的電源軌道的限制，多倍行高標準單元布局設計產生了具有挑戰性的問題，特別是混合高度標準單元的合法化問題。

一般的混合高度標準單元的合法化問題是NP-難問題，因為它本質上是一個strippacking問題。Tetris和Abacus是用來解決傳統的單倍行高標準單元最流行的合法化方法；然而，現有的工作表明，直接修改這兩種方法不能有效的來處理混合高度標準單元的合法化問題。在單倍行高標準單元合法化中，單元的重疊在行與行之間是互相獨立的。但是，在混合高度標準單元合法化中，單元的重疊在行與行之間是不獨立的，即在一行中移動單元可能會導致另一行的單元重疊。因此，在合法化多倍行高的標準單元時，需要考慮多個行之間是否會有單元重疊。

現有的混合高度標準單元的合法化方法存在下列兩個問題：(1)均是用啟發式的方法逐個對單元進行合法化，處理問題的角度過于局部；(2)缺乏理論依據，不能很好的保證合法化的質量。(3)不能同時最小化平均和最大單元移動，現有全局布局的質量難以保證。因此，為了得到更好的合法化結果，從一個更加全局的角度來考慮該合法化問題，并設計相應的有一定理論基礎的高效算法是值得考慮的。

發明內容

本發明的目的在于提供一種最小化平均和最大移動的混合高度單元合法化方法，以克服現有技術中存在的缺陷。

為實現上述目的，本發明的技術方案是：一種最小化平均和最大移動的混合高度單元合法化方法，包括如下步驟：

步驟S1：把電路表示為超圖模型H＝{V,E}；

步驟S2：將單元設置方向后，對齊到臨近且正確匹配的電源軌道行上；

步驟S3：對多倍行高標準單元進行預處理，并通過對目標函數和約束的分析和重構，將混合高度標準單元合法化模型轉換為一個考慮平均、最大、第二、第三大等單元移動的混合整數二次規劃模型；

步驟S4：將混合整數二次規劃模型轉換成二次規劃模型；

步驟S5：將二次規劃模型轉化為對應的線性互補模型；