基于約束的VLSI布圖算法研究與實(shí)現(xiàn).pdf

1、當(dāng)今，隨著片上系統(tǒng)(SoC)以及片上網(wǎng)絡(luò)(NoC)的不斷發(fā)展，在層次化設(shè)計(jì)中，許多學(xué)者根據(jù)芯片的性能和可靠性的需求，在布局中增加了一些與實(shí)際需求相關(guān)的約束，其中包括模塊間的位置約束，比如對齊約束、邊緣約束、性能約束、電性能約束等等。現(xiàn)代布局問題已經(jīng)從簡單的、傳統(tǒng)的布局問題，向具有各種條件約束的、復(fù)雜的布局問題轉(zhuǎn)變。在解決帶約束的布局問題時(shí)，本文采用B*-Tree表示法進(jìn)行布局。它是一種靈活高效的有序二叉樹表示方法。
　　 本文針

2、對兩種約束布局進(jìn)行了研究，即對齊約束布局和性能約束布局。由于模塊的排布是用坐標(biāo)來表示，因此對齊約束可按方向分為水平方向?qū)R約束和豎直方向?qū)R約束。本文基于B*-tree表示法進(jìn)行約束布局，實(shí)現(xiàn)了水平方向?qū)R約束布局、豎直方向?qū)R約束布局和性能約束布局的混合約束布局。并深入地研究了B*-tree的構(gòu)造及特點(diǎn)，提出了三個(gè)對應(yīng)約束的充分條件，提出優(yōu)化算法可快速篩選合法解。針對模擬退火算法，也提出了它的優(yōu)化流程。即在每次降溫迭代的過程中，我們要

3、檢測其布局是否合法，如果是非法的，則動(dòng)態(tài)的將之合法化，完成此溫度下的布局。在降溫迭代產(chǎn)生新的解空間的過程中，加入判斷步驟以減少時(shí)間的開銷來提高效率。實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證，本文約束的實(shí)現(xiàn)是成功的、優(yōu)化流程是行之有效的。
　　 隨著VLSI的不斷大型化、復(fù)雜化，晶元的個(gè)數(shù)成指數(shù)增長，在現(xiàn)階段芯片的設(shè)計(jì)過程中，布局時(shí)延成了布圖規(guī)劃瓶頸。所以，把布局中一些重復(fù)勞動(dòng)省去，達(dá)到減少時(shí)延的目的增量式算法成為研究的熱點(diǎn)。本文通過深入的分析研究，我們采取