資源描述：
《VLSI布局結(jié)構(gòu)表示研究進(jìn)展》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。
1、VLSI布局結(jié)構(gòu)表示研究進(jìn)展作者：徐寧，洪先龍，董社勤2006.11摘要：超大規(guī)模集成電路技術(shù)的迅猛發(fā)展迫切需要高性能CAD工具——電子設(shè)計(jì)自動(dòng)化軟件工具的支持。布局是布圖設(shè)計(jì)中一個(gè)極為重要的環(huán)節(jié)。目前，在深亞微米、超深亞微米工藝下的超人規(guī)模、甚人規(guī)模集成電路設(shè)計(jì)中，布局結(jié)果的好壞直接影響整個(gè)布圖設(shè)計(jì)，因此如何高效地表示布局結(jié)構(gòu)，從而提高布局質(zhì)量成為布圖設(shè)計(jì)中的一個(gè)國(guó)際上的研究熱點(diǎn)。文中介紹并分析了當(dāng)前國(guó)內(nèi)外比較流行的布局結(jié)構(gòu)的表示方法研究工作的進(jìn)展情況。關(guān)鍵詞：VLSI；布局；結(jié)構(gòu)表示；模擬退火布圖設(shè)計(jì)過(guò)程包括劃分、布圖規(guī)劃、布局、布線、壓縮等。隨著制造工藝進(jìn)入了深亞微米工藝
2、階段，電路的尺寸和復(fù)朵度迅速增加，布圖規(guī)劃和布局的地位顯得比以往更加重要。(1)布圖規(guī)劃和布局是布圖設(shè)計(jì)過(guò)程中的早期階段，其完成質(zhì)量的優(yōu)劣對(duì)布線工作的順利完成乃至最終芯片面積和性能的影響非常之大；(2)混合模式(MixeDModuleProblem,MMP)的設(shè)計(jì)越來(lái)越多;(3)模擬電路和數(shù)?；旌想娐吩谛酒O(shè)計(jì)屮的比例大幅度增加；(4)知識(shí)產(chǎn)權(quán)(IP)模塊在VLSI設(shè)計(jì)中的應(yīng)用增加:(5)多芯片模塊(MCM)問(wèn)題也H益受到重視。這些都為研究布圖規(guī)劃乃至布局工具提出了更高的要求。布圖規(guī)劃技術(shù)的產(chǎn)生主要是由于BBL(BuildingBlockLayout)模式分級(jí)設(shè)8BA1的需要。
3、BBL模式又稱宏單元模式，是設(shè)計(jì)中最靈活的一種方法。在這種布局模式中，單元或模塊可以有任意的形狀和尺寸，可以安排在芯片的任意位置上而且沒(méi)有固定的布線區(qū)域，因此具有更高的布局密度。BBL布局的過(guò)程就是將一組模塊或單元安置在芯片合適的位置上，使芯片的面積最小、模塊間的連線最短并容易布通。其輸入一般包括:(1)-個(gè)由模塊或單元組成的集合A={Mi,M2,Mm},其屮每個(gè)模塊是有固定邊長(zhǎng)的矩形或具他形狀的硬模塊，或是面積固定而長(zhǎng)寬比可以變動(dòng)的矩形軟模塊。每一?模塊Mi均有一個(gè)引線端的集合Pi={pii,pi2,.},其中每個(gè)引線端pij都被安置在模塊的邊界上。對(duì)屬于電源線網(wǎng)的引線端，會(huì)
4、記錄其所需的最大吸納電流和允許的最低電壓；(2)網(wǎng)表N={h，L2,.},其中每個(gè)線網(wǎng)Li是一個(gè)引線端的集合。屬于同一個(gè)線網(wǎng)的引線端將由布線工具把它們連結(jié)在一起；(3)由用戶給定的各種約束條件，如芯片的長(zhǎng)寬比或芯片的最大長(zhǎng)(寬)度等幾何方面的約束，關(guān)于引線端或壓焊塊的約束，以及一紐路徑或一組線網(wǎng)上的最人時(shí)間延遲即所謂時(shí)延的約束等。給定輸入以后，需要確定所有模塊的位置和方向，使得在滿足所有約束條件的情況下，達(dá)到芯片面積的最小化。進(jìn)入深亞微米乃至超深亞微米工藝階段后，性能驅(qū)動(dòng)或時(shí)延驅(qū)動(dòng)的算法己經(jīng)成為布圖設(shè)計(jì)的熱門(mén)課題。但由于約束或限制條件增多，設(shè)計(jì)過(guò)程中要考慮的因素也大人增加，因此
5、具復(fù)雜程度是前所未有的，更有效的時(shí)延佔(zhàn)計(jì)模型和時(shí)延驅(qū)動(dòng)算法還有待于進(jìn)一步的深入研究。其中布局結(jié)構(gòu)的表示成為算法的核心部分，也成為EDA(ElecTronicDesignAutomation).!作者研究的熱點(diǎn)課題。布局結(jié)構(gòu)BBL布局結(jié)構(gòu)通常有兩種：一種是可二劃分的結(jié)構(gòu)(Slicing)；另一種是不可二劃分的結(jié)構(gòu)(Non-Slicing)o圖1兩種布局結(jié)構(gòu)Slicing結(jié)構(gòu)是具有特殊性的布局結(jié)構(gòu)。如果一個(gè)布局具有這種結(jié)構(gòu)，那么可以通過(guò)遞歸地使用垂直或水平劃分線，把芯片或劃分芯片后得到的矩形劃分為兩個(gè)部分，直到劃分芯片所得到的每個(gè)子區(qū)域中只包含一個(gè)模塊，如圖1a所示。這種結(jié)構(gòu)可以方
6、便地使用二叉樹(shù)或波蘭表達(dá)式的數(shù)據(jù)結(jié)構(gòu)來(lái)表示，其布局解空間為0(m!23m-3/m15)；但是這種結(jié)構(gòu)不具有一般性，因此可能會(huì)浪費(fèi)芯片的面積。Non-SLicingNon-Slicing結(jié)構(gòu)包括所有可能出現(xiàn)的布局結(jié)構(gòu)，是一種更為一般的布局結(jié)構(gòu)，如圖1b所示。使用NomSlicing結(jié)構(gòu)可以獲得更高的布局密度，具有更大的優(yōu)越性。由于Slicing結(jié)構(gòu)只能解決部分布局問(wèn)題，它是NomSlicing結(jié)構(gòu)的子集，因此對(duì)NorvSIicing結(jié)構(gòu)的布局結(jié)構(gòu)表示研究成為熱點(diǎn)。本文僅對(duì)Nori-Slicing結(jié)構(gòu)的布局結(jié)構(gòu)表示的研究進(jìn)展進(jìn)行論述。布局結(jié)構(gòu)表示研究進(jìn)展求解NomSlicing結(jié)構(gòu)
7、的布局問(wèn)題，就是要在眾多的解屮尋找一個(gè)滿足設(shè)計(jì)約束條件的、最優(yōu)的解。隨著電路規(guī)模的迅速增大，模塊數(shù)越來(lái)越多，耍在合理的時(shí)間內(nèi)找到最優(yōu)解是不可能的，只能找到次優(yōu)解。因此如何表示解，如何降低冗余解，從而降低解空間，成為求解布局問(wèn)題的熱點(diǎn)。布局表示就是用字母或數(shù)字代表各模塊，并將其用一定的數(shù)據(jù)組織形式(如序列、樹(shù)、圖等)組織起來(lái)從而表達(dá)模塊Z間的幾何位置關(guān)系。對(duì)應(yīng)著一個(gè)模塊布局的序列、樹(shù)或圖稱為編碼。從編碼到模塊布局的映射稱為解碼。所有可能的編碼形式稱為這個(gè)布局表示法的組合空間或解空間。在20世紀(jì)
