VLSI物理設(shè)計(jì)中布局及有約束的布局優(yōu)化.pdf

1、隨著微電子技術(shù)的高速發(fā)展，VLSI的集成度急劇增加，特征尺寸迅速下降至深亞微米甚至納米級(jí)，導(dǎo)致VLSI物理設(shè)計(jì)階段的任務(wù)更重，難度更大。布圖規(guī)劃和布局是VLSI物理設(shè)計(jì)中的早期階段，其結(jié)果不但直接影響VLSI的整體設(shè)計(jì)質(zhì)量，而且會(huì)對(duì)后續(xù)的布線(xiàn)設(shè)計(jì)產(chǎn)生決定性的影響。因而，布圖規(guī)劃和布局已成為VLSI設(shè)計(jì)的關(guān)鍵問(wèn)題之一。本文在分析影響VLSI布圖規(guī)劃和布局相關(guān)因素的基礎(chǔ)上，從布圖規(guī)劃及布局的表示法、布局算法中所采用的數(shù)據(jù)結(jié)構(gòu)、布圖規(guī)劃的結(jié)構(gòu)

2、分析以及模塊放置的優(yōu)化方法等方面，對(duì)布局算法的優(yōu)化、有約束的布圖規(guī)劃和布局、布線(xiàn)優(yōu)化和標(biāo)準(zhǔn)單元模式布局等問(wèn)題作了一些探索性研究，主要工作和取得的成果概括如下：
　　 ⑴在布局算法上，詳細(xì)研究了布局算法中所采用的輔助數(shù)據(jù)結(jié)構(gòu)和模塊放置方法對(duì)算法運(yùn)行效率的影響，提出了角輪廓結(jié)構(gòu)（Corner-Contour）數(shù)據(jù)結(jié)構(gòu)，證明其從左至右階梯下降的重要特性，并結(jié)合O-tree和Single-Sequence（簡(jiǎn)稱(chēng)SS）表示法編碼各自的特性

3、，簡(jiǎn)化并優(yōu)化了基于這兩種表示法的布局算法；提出凹輪廓（Concave-Contour）數(shù)據(jù)結(jié)構(gòu)，并用其實(shí)現(xiàn)有固定外框約束的布局；在布局算法中考慮矩形外框?qū)Σ季值挠绊懀跃匦瓮饪驅(qū)蔷€(xiàn)為準(zhǔn)線(xiàn)引導(dǎo)模塊放置，加快了布局算法的收斂；利用邊界約束條件，在不執(zhí)行模塊放置程序的條件下快速評(píng)價(jià)布局編碼，以縮小搜索范圍，加快布局算法的收斂。
　　 ⑵在有約束的布局方面，詳細(xì)研究了SS表示法的編碼特性，提出并證明了基于該表示法的邊界約束的充要條件，

4、給出了邊界約束條件的數(shù)字串表達(dá)式并用算法實(shí)現(xiàn)。對(duì)SS表示法邊界約束條件的研究進(jìn)一步完善了這種新式表示法。
　　 ⑶在布線(xiàn)優(yōu)化方面，詳細(xì)研究了SS表示法與對(duì)應(yīng)布圖規(guī)劃之間的關(guān)系，提出基于該表示法的邊界約束對(duì)布圖規(guī)劃進(jìn)行分層結(jié)構(gòu)分析、通過(guò)引導(dǎo)模塊放置以?xún)?yōu)化布線(xiàn)結(jié)構(gòu)的方法，不但使SS編碼對(duì)應(yīng)的布圖規(guī)劃圖形結(jié)構(gòu)更加清晰，而且實(shí)現(xiàn)了布局對(duì)布線(xiàn)的指導(dǎo)作用和基于布線(xiàn)優(yōu)化的布局；基于B*-tree編碼，用插入虛擬模塊的方法實(shí)現(xiàn)了緊致型布局中任意