總體布線是VLSI物理設(shè)計中極為重要的一個環(huán)節(jié)。非曼哈頓結(jié)構(gòu)的提出為物理設(shè)計帶來諸多性能的提高，但該結(jié)構(gòu)的引入和多層工藝的普及，使得總體布線問題更為復(fù)雜，且目前研究工作只就某些局部目標(biāo)展開，缺乏一種該結(jié)構(gòu)下有效完整的總體布線方案。正是在這樣的背景下，本項目對非曼哈頓結(jié)構(gòu)VLSI總體布線相關(guān)問題展開一些研究工作，選取X結(jié)構(gòu)作為非曼哈頓結(jié)構(gòu)的代表，完成的主要工作如下：（1）基于多目標(biāo)PSO和Elmore時延模型提出了一種構(gòu)建時延驅(qū)動X結(jié)構(gòu)Steiner樹的有效算法，從而有助于性能驅(qū)動X結(jié)構(gòu)總體布線問題的研究。（2）繞障Steiner最小樹的構(gòu)建是VLSI物理設(shè)計中一個極為重要問題，為此，提出一種基于粒子群優(yōu)化的有效算法用于求解X結(jié)構(gòu)下的繞障Steiner最小樹問題。考慮到粒子群優(yōu)化算法存在收斂速度慢的不足，進一步設(shè)計一種四步驟的高效啟發(fā)式算法用于求解該問題。（3）針對ML-OAXSMT問題，以最小化布線總代價為目標(biāo)，并同時考慮到通孔數(shù)的優(yōu)化，提出了一種基于PSO算法和懲罰機制的ML-OAXSMT構(gòu)建算法。為了進一步提高求解多ML-OAXSMT問題的算法質(zhì)量，基于查找表的思想，提出了一種高效的繞障策略，可以準(zhǔn)確獲得多層環(huán)境下的Steiner點位置，從而構(gòu)建一棵高質(zhì)量的ML-OAXSMT。(4) 針對X結(jié)構(gòu)下的總體布線問題，提出一種基于ILP模型、劃分策略及PSO等技術(shù)的高質(zhì)量X結(jié)構(gòu)總體布線算法。 本項目進一步擴寬研究思路，針對曼哈頓結(jié)構(gòu)下繞障Steiner樹構(gòu)建問題并且將PSO擴展應(yīng)用于VLSI電路劃分階段，主要完成以下工作：（1）研究了電壓轉(zhuǎn)換速率的計算模型和RSMT-RERR問題中的電壓轉(zhuǎn)換速率約束，基于SPCF算法框架提出考慮電壓轉(zhuǎn)換速率約束的直角Steiner樹構(gòu)造算法。（2）研究了ML-OARSMT問題的特征，提出了該問題布線圖的構(gòu)造方法。考慮避開障礙和連通相鄰層，選擇了三種類型候選通孔位置。 （3）電路劃分作為VLSI物理設(shè)計中的首個關(guān)鍵環(huán)節(jié)，通過附加考慮時延因素，構(gòu)造了電路劃分的多目標(biāo)問題模型，引入局部搜索策略以及基于小生境技術(shù)的表現(xiàn)型共享粒子評價機制，設(shè)計了一個求解多目標(biāo)電路劃分問題的混合DPSO。 2100433B

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

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

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

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