超大規(guī)模集成電路布局算法研究.pdf

1、當(dāng)今信息時代，作為電子信息技術(shù)發(fā)展的核心和基礎(chǔ)，集成電路得到了迅猛的發(fā)展，這除了由于半導(dǎo)體工藝技術(shù)、設(shè)備、原材料等方面的不斷改進(jìn)之外，計算機(jī)輔助設(shè)計技術(shù)的采用也是一個重要原因。然而，隨著半導(dǎo)體制造工藝的特征尺寸越來越小，芯片的集成度越來越大，電路的工作頻率越來越高，布圖工藝越來越復(fù)雜，這些發(fā)展都對集成電路計算機(jī)輔助設(shè)計技術(shù)提出了新的要求。布局作為集成電路版圖設(shè)計中一個基本而且非常重要的環(huán)節(jié)，也面臨著嚴(yán)峻的挑戰(zhàn)，在大規(guī)模(上百萬門的單元需

2、要布局)和復(fù)雜的設(shè)計約束(時延、噪聲、功耗、擁擠度等)條件下，如何獲得高質(zhì)量的布局結(jié)果同時花費(fèi)較少的布局時間非常關(guān)鍵。本文正是圍繞這些問題展開計算機(jī)輔助設(shè)計領(lǐng)域內(nèi)的超大規(guī)模集成電路布局算法研究工作的，通過改進(jìn)現(xiàn)有的方法以及提出新的布局算法，嘗試更好地解決當(dāng)前和未來集成電路設(shè)計中的一些問題。 首先介紹了本文的研究對象——標(biāo)準(zhǔn)單元設(shè)計模式和基本的布局理論，然后對傳統(tǒng)的以線網(wǎng)總長為優(yōu)化目標(biāo)的基本布局算法進(jìn)行了分類分析。在此基礎(chǔ)上，提出

3、了一個基于改進(jìn)等分節(jié)點(diǎn)法的啟發(fā)式迭代優(yōu)化布局算法，該算法對原有的等分節(jié)點(diǎn)法進(jìn)行了改進(jìn)，使得單元的目標(biāo)位置在更廣的范圍內(nèi)得到搜尋，從而提高了迭代法的優(yōu)化質(zhì)量，而且通過使用啟發(fā)式策略使迭代優(yōu)化跳出局部最優(yōu)，設(shè)定合理的局部尋優(yōu)次數(shù)來有效地終止布局優(yōu)化，并采用記憶裝置記錄最優(yōu)布局結(jié)果，使整個優(yōu)化布局過程在沒有花費(fèi)過多時間的情況下，得到了較充分的迭代優(yōu)化。實(shí)驗(yàn)表明，與接近全局最優(yōu)的()Wolf7.0布局算法相比，該算法能夠獲得更好的布局質(zhì)量。

4、 針對超大規(guī)模集成電路線長優(yōu)化布局中布局質(zhì)量和花費(fèi)時間的嚴(yán)峻挑戰(zhàn)，討論了面向高復(fù)雜度、大規(guī)模問題的有效解決策略——分級設(shè)計方法，分析了基于分級設(shè)計的各種超大規(guī)模集成電路線長優(yōu)化布局算法。在此基礎(chǔ)上，提出了一個基于劃分的迭代優(yōu)化布局算法，該算法采用分級設(shè)計將大規(guī)模的布局問題分拆，借鑒好的遞歸劃分方法將電路分解，采用和改進(jìn)結(jié)群、終端傳遞等技術(shù)提高了劃分質(zhì)量，并且結(jié)合本文提出的啟發(fā)式迭代優(yōu)化方法在劃分所得的各個子電路內(nèi)進(jìn)行并行布局優(yōu)化，在

5、保證布局質(zhì)量的同時提高了布局速度。實(shí)驗(yàn)表明，與當(dāng)前流行的FengShui布局工具相比，該算法在花費(fèi)稍長一點(diǎn)的時間內(nèi)獲得了更好的布局質(zhì)量。 時序約束作為保證電路正常工作性能的一個重要因素，本文討論了以路徑時延為優(yōu)化目標(biāo)的布局算法。首先介紹了有關(guān)時序問題的基本知識，分析了互連線時延的估算模型，并對當(dāng)前的各種時延驅(qū)動布局算法進(jìn)行了分類分析。在此基礎(chǔ)上，提出了一個時延驅(qū)動布局算法，該算法基于對電路時延圖的拓?fù)浣Y(jié)構(gòu)分析，將優(yōu)化路徑時延的問

6、題轉(zhuǎn)換成優(yōu)化路徑上單元位置的問題，通過建立優(yōu)化單元位置的隊列鏈表，采用一種新的等分節(jié)點(diǎn)法尋找路徑上單元的目標(biāo)位置，使得關(guān)鍵路徑的時延得到了有效地減小，路徑時延的分布更加合理。在優(yōu)化路徑時延的同時還結(jié)合了優(yōu)化線長的布局算法，在獲得好的路徑時延優(yōu)化效果的同時，能夠盡量保留原有已取得的好的線長優(yōu)化效果，使兩種布局優(yōu)化目標(biāo)能夠有機(jī)地結(jié)合。 在深亞微米及更先進(jìn)的工藝條件下，芯片的設(shè)計密度問題變得嚴(yán)峻起來，它會導(dǎo)致對布線資源需求的大幅度增加

7、，當(dāng)芯片某些區(qū)域內(nèi)的布線資源無法滿足實(shí)際的走線需要時，就會迫使線網(wǎng)繞道而行從而惡化設(shè)計性能，甚至無法實(shí)現(xiàn)100﹪布通率，造成布線擁擠，因此本文對以布線密度為優(yōu)化目標(biāo)的擁擠度驅(qū)動布局算法進(jìn)行了研究。首先介紹了布局階段使用的布線密度分析方法和常見的布線密度估計模型，在對現(xiàn)有的各種擁擠度驅(qū)動布局算法分析的基礎(chǔ)上，提出了一個用于布局后處理的擁擠度驅(qū)動布局算法，該算法對原有的線網(wǎng)邊框布線估計模型進(jìn)行了改進(jìn)，在保留估算速度快，易于編程實(shí)現(xiàn)等優(yōu)點(diǎn)的同

8、時，提高了分析布線密度的精度；在優(yōu)化布線擁擠度時，提出以線網(wǎng)為中心，通過逐步擴(kuò)大或者縮小布線擁擠區(qū)域內(nèi)線網(wǎng)邊框尺寸的方法，最終達(dá)到降低布線擁擠度的目的。實(shí)驗(yàn)結(jié)果顯示，電路的布線溢出總量和布線溢出峰值都明顯減小，電路的布線擁擠情況得到了明顯的緩解。 最后，將本文布局算法的研究成果進(jìn)行了軟件實(shí)現(xiàn)，開發(fā)了具有自主知識產(chǎn)權(quán)的布局自動設(shè)計工具。論文首先介紹了布局程序系統(tǒng)的結(jié)構(gòu)框架，然后針對系統(tǒng)中各個軟件模塊分別進(jìn)行了解釋和說明，并給出了用