總體布線是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。 2100433B

總體布線是物理設計中極為重要的一個環節。非曼哈頓結構帶來物理設計諸多性能的提高，該結構的引入和多層工藝的普及，使得總體布線算法更為復雜，且目前研究工作只就某些局部目標展開，缺乏一個該結構下有效完整的多層總體布線方案。為此，本課題研究在非曼哈頓結構下高效的VLSI多層總體布線器的構建：（1）利用X結構Steiner樹的幾何性質，定義其編解碼方式和操作算子，繼而構造X結構Steiner最小樹；（2）定義不同程度的擁擠區域為權重各異的障礙物，融入懲罰機制，構建X結構繞障Steiner樹，并利用分治思想和整數規劃模型，構建擁擠線網的重布方法；（3）將緩沖器插入問題轉換成求解最小半徑最小代價生成樹，構造求解該問題的多目標粒子群優化算法，以期優化時延；（4）定義線網順序的評價函數，分析串擾的計算方法，構造同時優化串擾和通孔數的X結構層分配多目標粒子群優化算法，以還原之前映射到平面上的多層總體布線資源。

VLSI總體布線的結果對詳細布線的成功與否和芯片的性能影響極大，其本質是典型的NP困難多目標組合優化問題。非曼哈頓結構的引入使物理設計的諸多性能得到提高，但目前研究主要集中在通道布線，缺乏一個該結構下有效完整的總體布線方案。本課題研究在非曼哈頓結構下帶粒子群優化的高效總體布線器的構建，其分為三個階段：（1）構建各線網的非曼哈頓結構Steiner最小樹集，定義擁擠度估算函數確定處于擁擠區域的線網，并對其構造擁擠度驅動的非曼哈頓結構Steiner樹集；（2）引入能克服線網順序依賴性的整數線性規劃模型，并同時采用優化時延和功耗目標的緩沖器插入技術，構建非曼哈頓結構下基于整數線性規劃的總體布線多目標優化模型，給出其相應的多目標粒子群優化算法；（3）通過定義線網關鍵性評價函數以獲得基于啟發式策略的初始層分配方案，繼而以最小化擁擠度、通孔數和串擾為目標給出對初始方案進一步優化的非曼哈頓結構層分配算法。

超大規模集成電路物理設計中布圖規劃和線長估計問題是集成電路設計的重要環節，布圖規劃和線長估計問題是高度復雜的。我們已對其做了比較深入的研究，分析布圖規劃和線長估計問題的圖論性質，給出問題解的構造方法，構造了一個多目標粒子群優化算法框架，繼而研究求解布圖規劃和線長估計問題的有效多目標粒子群優化算法。本課題研究在非曼哈頓結構下帶粒子群優化的高效總體布線器的構建，我們深入研究非曼哈頓結構下總體布線問題的相關性質，選取X結構作為非曼哈頓結構開展研究，取得的主要研究成果如下：（1）針對X結構Steiner最小樹問題，分析非曼哈頓結構Steiner樹性質，重新構造非曼哈頓結構 Steiner 樹的編解碼方式，提出來一種改進的離散粒子群優化算法用以求解X結構Steiner最小樹；（2）定義擁擠度估算函數確定處于擁擠區域的線網和引入最小化線長最小半徑的性能驅動布線樹模型，構造不同目標和不同約束下的非曼哈頓結構布線樹模型，從而構建其相應的粒子群優化算法，繼而從適應度函數的構造、算法參數模型調整策略和性能提高策略三個方面來研究算法；（3）針對非曼哈頓結構下層分配問題，通過定義線網關鍵性評價函數以獲得基于啟發式策略的初始層分配方案，繼而以最小化擁擠度、通孔數和串擾為目標給出對初始方案進一步優化的非曼哈頓結構層分配算法，分析算法的收斂性并檢驗這些算法的有效性和可行性。本項目的研究成果將為粒子群優化算法的進一步應用打下基礎，并進一步提高我國關于超大規模集成電路設計基礎理論研究水平。 2100433B

ECC(橢圓曲線密碼系統)是已寫入我國無線局域網標準WAPI和我國正在制定其算法標準的一種公鑰密碼，在信息安全領域具有重要應用。本項目研究ECC算法的有效實現，重點是ECC算法VLSI實現時的算法結構和電路結構，具體包括兩方面內容。一是為了更好地滿足ECC軟件實現或VLSI實現對各種具體實現算法的需求，要尋找ECC實現中的新算法、新方法，或者要優化各種已存在的ECC實現算法。二是如何依據這些新算法、新方法或優化算法，再結合VLSI實現的不同設計目標，要提出各種VLSI實現的算法結構、電路結構，并要獲取各種VLSI實現的實驗數據與結果。研究內容與擬解決的關鍵問題凝練于申請者近年來從事高速ECC密碼芯片研制時所遇到的科學問題。研究成果對于豐富ECC算法VLSI實現的理論、方法和實驗數據，支撐基于我國ECC標準的芯片研發具有重要意義。 2100433B