直接最佳化半周長線長的VLSI兩階段疊代布局算法研究

《直接最佳化半周長線長的VLSI兩階段疊代布局算法研究》是依託福州大學，由陳建利擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：直接最佳化半周長線長的VLSI兩階段疊代布局算法研究
• 依託單位：福州大學
• 項目類別：青年科學基金項目
• 項目負責人：陳建利

項目摘要

布局是超大規模積體電路（VLSI）物理設計的關鍵環節之一，是典型的大規模NP困難問題。隨著電路晶片的集成度不斷提高，VLSI布局對最佳化目標的準確性和最佳化方法的效率提出了更高要求。VLSI布局的目標是最小化半周長之和的匯流排長。由於半周長線長是一個非光滑凸函式，當前基於分析方法的各種布局算法都是採用不同的線長模型對其進行近似，存在較大誤差，不能很好反映布局的實際線長。針對該問題，本項目研究直接最佳化半周長線長的VLSI布局算法。在具有較大優勢的基於分析方法的兩階段疊代布局框架下，設計求解半周長線長函式的第一階段問題的算法並分析算法的收斂性，改進第二階段的單元散開方式，研究第一階段與第二階段的互動技術，分析與選擇疊代終止準則，從而得到直接最佳化半周長線長的兩階段疊代布局算法。在此基礎上，利用多極框架進一步提高該算法求解更大規模布局問題的能力，最終獲得高效率、高質量的基於兩階段疊代的布局工具。

結題摘要

布局是超大規模積體電路（VLSI）物理設計的關鍵環節之一，是典型的大規模NP困難問題。隨著電路晶片的集成度不斷提高，VLSI布局對最佳化目標的準確性和最佳化方法的效率提出了更高要求。VLSI布局的目標是最小化半周長之和的匯流排長。由於半周長線長是一個非光滑凸函式，當前基於分析方法的各種布局算法都是採用不同的線長模型對其進行近似，存在較大誤差，不能很好反映布局的實際線長。針對該問題，本項目研究直接最佳化半周長線長的VLSI布局算法,並考慮不同約束的布局問題。 我們提出一種基於分離變數法和精確的密度函式的解析方法求解泊松方程，可實現當前全局布局工具中最好的線長；在利用近端群域多乘子交替方向法同時考慮在全局布局中霧化效應和鄰近效應約束，可顯著提高布局質量。對多倍高的布局合法化問題，我們在儘量保持全局布局單元位置不變的基礎上，提出了一個快速且接近最優的算法（MMSIM）來解決混合高度單元的合法化問題。在單元合法化過程中，我們額外考慮了最小植入區域約束，技術約束和區域約束，相比當前最先進的合法化布局工具，我們的合法化算法均可實現更好的布局質量。對包含不同約束的超大規模積體電路設計問題，我們通過離散鬆弛最佳化算法和整數規划算法來處理DSA的通孔層掩模板和模板分配問題，並提出了一種自適應混合模型算法來處理多目標熱感知非切片布局規劃最佳化問題，同時最佳化晶片的面積、匯流排長、最高溫度和平均溫度。 在本項目支持下，項目組成員取得的主要成就如下：獲第54屆設計自動化會DAC 2017最佳論文獎；獲第36屆國際積體電路計算機輔助設計會議（ICCAD 2017）所舉行的CAD學術競賽全球第一名；蟬聯第37屆國際積體電路計算機輔助設計會議（ICCAD 2018）所舉行的CAD學術競賽全球第一名；在第37屆國際積體電路計算機輔助設計會議（ICCAD 會議）發表論文4篇，並且其中一篇論文獲得ICCAD 2018最佳論文提名獎；獲首屆中國計算機學會（CCF）積體電路Early Career Award。