《非曼哈頓結構下帶粒子群最佳化的VLSI總體布線算法研究》是依託福州大學，由陳國龍擔任項目負責人的專項基金項目。
基本介紹
- 中文名：非曼哈頓結構下帶粒子群最佳化的VLSI總體布線算法研究
- 依託單位：福州大學
- 項目類別：專項基金項目
- 項目負責人：陳國龍
項目摘要,結題摘要,
項目摘要
VLSI總體布線的結果對詳細布線的成功與否和晶片的性能影響極大，其本質是典型的NP困難多目標組合最佳化問題。非曼哈頓結構的引入使物理設計的諸多性能得到提高，但目前研究主要集中在通道布線，缺乏一個該結構下有效完整的總體布線方案。本課題研究在非曼哈頓結構下帶粒子群最佳化的高效總體布線器的構建，其分為三個階段：（1）構建各線網的非曼哈頓結構Steiner最小樹集，定義擁擠度估算函式確定處於擁擠區域的線網，並對其構造擁擠度驅動的非曼哈頓結構Steiner樹集；（2）引入能克服線網順序依賴性的整數線性規劃模型，並同時採用最佳化時延和功耗目標的緩衝器插入技術，構建非曼哈頓結構下基於整數線性規劃的總體布線多目標最佳化模型，給出其相應的多目標粒子群最佳化算法；（3）通過定義線網關鍵性評價函式以獲得基於啟發式策略的初始層分配方案，繼而以最小化擁擠度、通孔數和串擾為目標給出對初始方案進一步最佳化的非曼哈頓結構層分配算法。
結題摘要
超大規模積體電路物理設計中布圖規劃和線長估計問題是積體電路設計的重要環節，布圖規劃和線長估計問題是高度複雜的。我們已對其做了比較深入的研究，分析布圖規劃和線長估計問題的圖論性質，給出問題解的構造方法，構造了一個多目標粒子群最佳化算法框架，繼而研究求解布圖規劃和線長估計問題的有效多目標粒子群最佳化算法。本課題研究在非曼哈頓結構下帶粒子群最佳化的高效總體布線器的構建，我們深入研究非曼哈頓結構下總體布線問題的相關性質，選取X結構作為非曼哈頓結構開展研究，取得的主要研究成果如下：（1）針對X結構Steiner最小樹問題，分析非曼哈頓結構Steiner樹性質，重新構造非曼哈頓結構 Steiner 樹的編解碼方式，提出來一種改進的離散粒子群最佳化算法用以求解X結構Steiner最小樹；（2）定義擁擠度估算函式確定處於擁擠區域的線網和引入最小化線長最小半徑的性能驅動布線樹模型，構造不同目標和不同約束下的非曼哈頓結構布線樹模型，從而構建其相應的粒子群最佳化算法，繼而從適應度函式的構造、算法參數模型調整策略和性能提高策略三個方面來研究算法；（3）針對非曼哈頓結構下層分配問題，通過定義線網關鍵性評價函式以獲得基於啟發式策略的初始層分配方案，繼而以最小化擁擠度、通孔數和串擾為目標給出對初始方案進一步最佳化的非曼哈頓結構層分配算法，分析算法的收斂性並檢驗這些算法的有效性和可行性。本項目的研究成果將為粒子群最佳化算法的進一步套用打下基礎，並進一步提高我國關於超大規模積體電路設計基礎理論研究水平。
