[發明專利]基于電場能建模技術的VLSI標準單元布局方法

有效

• 申請號: 201710207076.5
• 申請日: 2017-03-31
• 公開（公告）號: CN107526860B
• 公開（公告）日: 2019-12-31
• 發明（設計）人: 朱文興;黃志鵬;陳建利
• 申請（專利權）人: 福州大學
• 主分類號: G06F17/50
• 分類號: G06F17/50
• 代理公司: 35100 福州元創專利商標代理有限公司
• 代理人: 蔡學俊

本發明涉及一種基于電場能建模技術的VLSI標準單元布局方法，該方法通過建立問題的電場能模型，利用全局密度函數及泊松方程的解析解，求解VLSI標準單元全局布局問題。技術方案要點如下：(1)通過將布局問題與靜電系統進行類比，將單元比作電荷，將原先的密度約束轉化為零勢能約束。構建了微分方程，并通過對其求解顯式表達式來更為精確的刻畫勢能約束。再采用罰函數方法將VLSI全局布局的線長目標及勢能約束轉化為無約束的非線性規劃問題并選擇合適的優化技術進行優化。(2)與之前使用均勻劃分bin的方法得到離散的密度函數值不同，此發明計算單元與整個布局區域重疊約束的全局密度表達式，從而更準確的刻畫單元在布局區域上的分布狀況。

技術領域

本發明涉及VLSI物理設計自動化技術領域，特別是涉及基于電場能建模技術的VLSI標準單元布局方法。

背景技術

在當前的VLSI布局中，集成電路規模的不斷增大及工藝上的要求越來越高，對VLSI布局優化目標及優化方法提出了更高的要求，布局結果的好壞直接影響著整個芯片的性能。隨著芯片上單元個數的快速增長，尤其是百萬門級芯片的普遍應用，對VLSI布局設計自動化提出了巨大的挑戰。因此，尋求更高效、更實用的集成電路布局算法具有重要的意義

用來解決VLSI布局問題的算法可分為以下三類：基于劃分的布局方法、基于劃分技術的方法和基于分析的布局方法。在這三類方向中，基于分析的布局方法取得的布局效果較好，因而成為當前主流布局工具所采用的方法。由于VLSI 布局問題的規模很大，現有的基于解析的布局工具很難直接求解。在分析方法的 VLSI布局算法中，主要分三個步驟處理：全局布局(global placement)、合法化布局(legalization)和詳細布局(detailedplacement)。全局布局中，在允許有少數單元互相重疊的情況下，找到每個單元的最佳位置，使得總線長最短。由于全局布局大體上決定了布局的質量，全局布局被認為是分析法中最重要的一步。

目前，基于分析方法的全局布局算法可以分為兩類:(1)直接法,該方法被應用于Kraftwerk2,FastPlace3,RQL,SimPL等布局工具中；(2)非線性方法，該方法被應用于APLace2,NTUplace3,mPL6，ePlace等布局工具中。根據學術上和工業界布局器的比較,基于非線性規劃方法的布局工具取得的實驗結果最好。

但是，現有的基于分析方法的全局布局方法存在下列兩個問題：(1)在全局布局過程中，均使用對布局區域均勻劃分為bin的方法進行密度的近似計算，由于密度函數是非光滑的，還需要進行光滑化近似。因此近似后計算出來的密度約束與實際密度分布存在較大的誤差，不是對布局實際密度很好的反映，從而不能保證布局的質量；(2)已有的布局工具有利用泊松方程進行求解，但使用的是數值求解的求解方法，對解的質量也有一定的影響。

發明內容

有鑒于此，本發明的目的是提供一種基于電場能建模技術的VLSI標準單元布局方法，將摒棄離散計算密度分布與數值求解微分方程的方法，采用全局密度函數并對微分方程求得解析解。進而選擇利普西斯步長預測的Nesterov’s方法進行求解得到高質量的布局結果。其基本思想是結合全局密度函數和不需要線搜索的利普西斯步長預測的Nesterov’s方法，運用電場能建模的思想，構建泊松方程并進行求解，從而得到一種性能優越的基于分析方法的全局布局方法。

本發明采用以下方案實現：一種基于電場能建模技術的VLSI標準單元布局方法，基于電場能建模技術的超大規模集成電路標準單元布局方法，先把電路表示為超圖；然后，通過與靜電系統進行類比將布局問題建模為電場能問題；接著，計算問題的全局密度函數，構建泊松方程并求解析解。在該方法中，使用罰函數的思想將線長和密度結合作為目標函數，然后在每步迭代中利用Nesterov’s算法優化求解，包括如下步驟：

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

步驟S2：把電路基于電場能技術進行建模；