《基於半周長線長的VLSI布局模型及其算法研究》是依託福州大學，由陳建利擔任項目負責人的數學天元基金項目。
基本介紹
- 中文名：基於半周長線長的VLSI布局模型及其算法研究
- 依託單位：福州大學
- 項目類別：數學天元基金項目
- 項目負責人：陳建利
項目摘要,結題摘要,
項目摘要
布局是超大規模積體電路（VLSI）物理設計自動化的關鍵環節之一。隨著積體電路規模的不斷增大及工藝上的要求越來越高，對VLSI布局最佳化目標及最佳化方法提出了更高的要求。VLSI布局問題的目標是最小化半周長線長計算的匯流排長。半周長線長是一個不連續可微的凸函式。當前基於分析方法的各種布局算法都是對半周長線長作光滑化近似，不能很好地反應實際布局的目標。針對該問題，本項目對基於半周長線長計算的VLSI布局問題展開研究。通過建立問題模型，給出目標函式的處理方法、約束條件的處理技術及所採用的最佳化算法，並分析所建立的問題模型的凸性、可分離性、梯度單調性及採用的最佳化算法的收斂性等。在此基礎上，結合VLSI分層技術，獲得高質量、高效率的基於解析方法的布局算法，最終生成工業上可用的布局軟體。
結題摘要
針對當前基於分析方法的各種超大規模積體電路（VLSI）布局算法都是對半周長線長(不連續可微的凸函式)作光滑化近似，不能很好地反應實際布局的目標，本項目對基於半周長線長計算的VLSI布局問題展開研究。通過建立不同的線長模型及約束模型，給出線長函式的處理方法、約束條件的處理技術及所採用的最佳化算法，並分析所建立的問題模型的凸性、可分離性、梯度單調性及採用的最佳化算法的收斂性等。在此項目資助下，已發表論文兩篇，投稿論文兩篇，申請國家發明專利一項，軟體著作權二項。 本項目中，最主要的工作為提出一種非光滑但可精確計算半周長線長的l1-norm線長模型。在l1-norm線長模型和精確計算單元與BIN的密度的基礎上，將線長目標及密度約束轉化為無約束的非線性規劃問題。採用一種非光滑的最佳化技術對此非線性規劃問題進行求解，並及分析所採用的算法的局部收斂性。採用IBM及相關ISPD競賽的測試例子集對我們所提出的算法進行測試，實驗結果表明，由此形成的布局工具，解的質量比當前最好的布局工具EPLACE提高1.1%。
