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

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

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

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

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

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

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

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

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