BBL布局結(jié)構(gòu)及算法研究.pdf

1、作為電子信息產(chǎn)業(yè)發(fā)展的核心和基礎(chǔ)，集成電路技術(shù)正迅速向著更高集成度，超小型化，高性能、高可靠性的方向發(fā)展。隨著系統(tǒng)芯片(SOC)設計方法和知識產(chǎn)權(quán)(IP)模塊技術(shù)在集成電路設計中的不斷發(fā)展和應用，布圖規(guī)劃和布局日漸成為超大規(guī)模集成(VLSI)電路與系統(tǒng)物理設計的關(guān)鍵環(huán)節(jié)。布圖規(guī)劃和布局的主要目標是在滿足用戶約束條件的前提下確定芯片上模塊的最佳形狀、位置以及模塊的引線端位置，使得芯片的面積以及模塊之間的互連線總長最小。由于布圖規(guī)劃和布局是

2、芯片物理設計的第一個重要步驟，其結(jié)果將影響芯片的最終性能。 在VLSI設計流程中，物理設計是既關(guān)鍵又復雜的一步，而布局又是物理設計中最重要的一步，布局的諸多問題都是NP完全問題，需要啟發(fā)式算法來求解。隨著VLSI集成度的迅猛提高，尋求有效的優(yōu)化算法應用于布局問題，以提高布局質(zhì)量和速度已成為當務之急；同時如何高效地表示布局結(jié)構(gòu)，從而提高布局質(zhì)量成為物理設計中的一個國際研究熱點。本文正是在這樣的背景下，對VLSI物理設計中的關(guān)鍵環(huán)節(jié)

3、——布局，展開了一些研究工作。 本文概括地介紹了布局結(jié)構(gòu)表示研究的進展。針對不可二劃分的BBL布局問題，近年來國內(nèi)外涌現(xiàn)出如：CBL、BSG、SP、O-tree等優(yōu)秀的布局結(jié)構(gòu)表示方法，但它們在解空間的大小、編碼的費用、編碼與布局之間的轉(zhuǎn)換時間等方面各有差異。 本文提出了一種求解VLSI布局問題的啟發(fā)式算法。該算法通過設計模塊的優(yōu)先順序進行合理的布局，再輔助于邊界矩形來減少邊界浪費，對于模塊布局放置的多個可能位置進行比較