《非曼哈頓結構下VLSI多層總體布線算法研究》是依託福州大學，由陳國龍擔任項目負責人的面上項目。
基本介紹
- 中文名：非曼哈頓結構下VLSI多層總體布線算法研究
- 依託單位：福州大學
- 項目類別：面上項目
- 項目負責人：陳國龍
項目摘要,結題摘要,
項目摘要
總體布線是物理設計中極為重要的一個環節。非曼哈頓結構帶來物理設計諸多性能的提高，該結構的引入和多層工藝的普及，使得總體布線算法更為複雜，且目前研究工作只就某些局部目標展開，缺乏一個該結構下有效完整的多層總體布線方案。為此，本課題研究在非曼哈頓結構下高效的VLSI多層總體布線器的構建：（1）利用X結構Steiner樹的幾何性質，定義其編解碼方式和操作運算元，繼而構造X結構Steiner最小樹；（2）定義不同程度的擁擠區域為權重各異的障礙物，融入懲罰機制，構建X結構繞障Steiner樹，並利用分治思想和整數規劃模型，構建擁擠線網的重布方法；（3）將緩衝器插入問題轉換成求解最小半徑最小代價生成樹，構造求解該問題的多目標粒子群最佳化算法，以期最佳化時延；（4）定義線網順序的評價函式，分析串擾的計算方法，構造同時最佳化串擾和通孔數的X結構層分配多目標粒子群最佳化算法，以還原之前映射到平面上的多層總體布線資源。
結題摘要
總體布線是VLSI物理設計中極為重要的一個環節。非曼哈頓結構的提出為物理設計帶來諸多性能的提高，但該結構的引入和多層工藝的普及，使得總體布線問題更為複雜，且目前研究工作只就某些局部目標展開，缺乏一種該結構下有效完整的總體布線方案。正是在這樣的背景下，本項目對非曼哈頓結構VLSI總體布線相關問題展開一些研究工作，選取X結構作為非曼哈頓結構的代表，完成的主要工作如下：（1）基於多目標PSO和Elmore時延模型提出了一種構建時延驅動X結構Steiner樹的有效算法，從而有助於性能驅動X結構總體布線問題的研究。（2）繞障Steiner最小樹的構建是VLSI物理設計中一個極為重要問題，為此，提出一種基於粒子群最佳化的有效算法用於求解X結構下的繞障Steiner最小樹問題。考慮到粒子群最佳化算法存在收斂速度慢的不足，進一步設計一種四步驟的高效啟發式算法用於求解該問題。（3）針對ML-OAXSMT問題，以最小化布線總代價為目標，並同時考慮到通孔數的最佳化，提出了一種基於PSO算法和懲罰機制的ML-OAXSMT構建算法。為了進一步提高求解多ML-OAXSMT問題的算法質量，基於查找表的思想，提出了一種高效的繞障策略，可以準確獲得多層環境下的Steiner點位置，從而構建一棵高質量的ML-OAXSMT。(4) 針對X結構下的總體布線問題，提出一種基於ILP模型、劃分策略及PSO等技術的高質量X結構總體布線算法。 本項目進一步擴寬研究思路，針對曼哈頓結構下繞障Steiner樹構建問題並且將PSO擴展套用於VLSI電路劃分階段，主要完成以下工作：（1）研究了電壓轉換速率的計算模型和RSMT-RERR問題中的電壓轉換速率約束，基於SPCF算法框架提出考慮電壓轉換速率約束的直角Steiner樹構造算法。（2）研究了ML-OARSMT問題的特徵，提出了該問題布線圖的構造方法。考慮避開障礙和連通相鄰層，選擇了三種類型候選通孔位置。 （3）電路劃分作為VLSI物理設計中的首個關鍵環節，通過附加考慮時延因素，構造了電路劃分的多目標問題模型，引入局部搜尋策略以及基於小生境技術的表現型共享粒子評價機制，設計了一個求解多目標電路劃分問題的混合DPSO。
