《超大規模積體電路布局的ell-1模最佳化模型及其算法研究》是依託福州大學，由朱文興擔任項目負責人的面上項目。
基本介紹
- 中文名：超大規模積體電路布局的ell-1模最佳化模型及其算法研究
- 依託單位：福州大學
- 項目類別：面上項目
- 項目負責人：朱文興
項目摘要,結題摘要,
項目摘要
布局是超大規模積體電路物理設計自動化的主要環節之一。由於積體電路的規模越來越大，對布局問題的最佳化目標和最佳化方法提出了更高的要求。超大規模積體電路布局問題的原始的目標函式是用ell-1模計算的，當前基於分析方法的各種布局算法都是對其作光滑化近似，不能很好地反應實際布局的需求。針對該問題，本項目研究該目標函式下的標準單元和混合單元布局問題的最佳化算法。對非光滑密度約束的全局布局問題，本項目將構造基於Lagrange函式的臨近點交替方向法；對光滑化後的密度約束的全局布局問題，利用序列二次規划算法的思想，構造臨近點交替方向法求解該問題，並分析算法的收斂性。同時，利用超大規模積體電路的稀疏結構，改進所構造的算法以求解更大規模的全局布局問題，減少布局算法分層次數。為使得到的解更優，本項目將研究好的初始解的生成方法。最後結合分層等技術實現整個布局算法，並研究其性能，最終形成工業上可用的布局軟體核心技術。
結題摘要
布局是超大規模積體電路物理設計自動化的主要環節之一。由於積體電路的規模越來越大，對布局問題的最佳化目標和最佳化方法提出了更高的要求。當前基於分析方法的各種布局算法都是對半周長線長作光滑化近似，不能很好地反應實際布局的需求。本項目主要針對該問題開展研究，取得了以下主要成果： 我們研究了超大規模積體電路混合單元布局問題，提出了l1模線長目標函式和非光滑密度約束的布局非線性規劃模型，提出了基於非光滑最佳化的布局算法，由此形成的布局工具解的質量比當前最好的布局工具ePlace及工業上所採用的布局工具CAPO10.5、SimPL等有較大幅度的提高，可滿足工業界對布局問題的需求。該研究成果獲得國際學術界和業界的好評，被認為是指出布局研究的新方向，Fuzhou Placer等；我們研究了基於增廣拉格朗日函式法的VLSI全局布局算法，並用來解決超大規模積體電路物理設計中的全局布局問題，改進了以往的基於非線性規劃的布局算法都是採用懲罰函式法求解的缺點；研究了超大規模積體電路兩階段布局算法的第一階段中的凸最佳化問題，基於Nesterov光滑化技術和Excessive gap technique，構造了一個原始-對偶一階最佳化算法，證明了算法的收斂速度是最優的；針對超大規模積體電路的modern mixed-size布局問題，設計並實現了一個新的布局流程。與當前最好的混合單元布局器相比，本算法可有效處理包含可移動宏單元的超大規模積體電路布局問題；研究了從超大規模積體電路全局布局中提取的非凸非線性規劃問題，構造了基於臨近點的交替方向法，在適當條件下證明了算法收斂於問題的KKT點；研究了超大規模積體電路標準單元布局的聚類方法，提出了考慮位置信息的聚類方法，實驗表明該策略對積體電路布局問題是有益的。同時，我們還研究了超大規模積體電路標準單元陣列布局問題的快速遺傳算法，二維strip packing問題，超大規模積體電路劃分問題，圖的最大二等分問題，圖的max-k-cut問題等。 在本項目的資助下，課題組共發表學術刊物論文35篇，其中SCI收錄刊物論文20篇，其中CCF A類刊物論文3篇，CCF B類刊物論文3篇， CCF C類刊物論文2篇；申請發明專利4項。
