帶約束的VLSI布圖規(guī)劃算法的研究.pdf

1、隨著片上系統(tǒng)(SOC)設(shè)計的不斷發(fā)展，在現(xiàn)階段層次化設(shè)計中，許多學者根據(jù)片上系統(tǒng)的性能和可靠性的需求，在布圖優(yōu)化問題中增加了一些與實際需求相關(guān)的約束，其中包括模塊問的位置約束，比如固定邊框約束，邊緣約束，對齊約束和鄰接約束等；還有電性能約束，比如電壓降約束，電子遷移約束以及最小電源線寬約束?，F(xiàn)代布圖規(guī)劃問題已經(jīng)從傳統(tǒng)的、簡單的布圖規(guī)劃問題向具有各種約束的，復雜的布圖規(guī)劃問題轉(zhuǎn)變。
　　 在解決帶約束的布圖規(guī)劃問題時，本文采用的是

2、一種有效且非常靈活的布圖表示法……B*-Tree表示法。
　　 本文提出了一種新穎的位置約束問題，即邊界聚集約束。該約束是針對宏模塊而言的，它要求所有的宏模塊都必須放置在或者聚集的放置在版圖的邊緣。該約束有利于減小互連線長和布線時空問的不連續(xù)性。在解決基于該約束的布圖規(guī)劃問題時，本文對B*-Tree表示法進行了深入的研究，并在滿足一定限制條件的前提下提出了四個充分條件。本文提出的優(yōu)化算法可以動態(tài)的將隨機產(chǎn)生的非法解有效、快速的轉(zhuǎn)

3、化為合法解，從而大大提高了搜索效率，而不是采用懲罰函數(shù)法。本文提出的優(yōu)化算法通過了基于MCNC和GSRC標準電路中五個基本電路的測試和驗證。實驗結(jié)果表明，本文提出的解決帶有邊界聚集約束的布圖規(guī)劃算法是非常有效的。
　　 同時，基于電性能約束的布圖規(guī)劃問題已經(jīng)成為一個研究熱點。本文也對電源/地線網(wǎng)絡(luò)和布圖規(guī)劃的協(xié)同設(shè)計進行了深入研究。電源/地線網(wǎng)絡(luò)和布圖規(guī)劃協(xié)同設(shè)計的主要目標是獲得一個比較優(yōu)秀的布圖結(jié)果并且同時產(chǎn)生一個相對應的電源

4、/地線網(wǎng)絡(luò)使其在滿足所有相關(guān)電性能約束的前提下繞線資源最少。本文提出了一種模式選擇機制，它有效的提高了整個優(yōu)化流程的效率。本文同時也提出了一個基于電源/地線網(wǎng)絡(luò)的增量式布圖方法，它可以有效的修復優(yōu)化流程中產(chǎn)生的非法解?？紤]到電源/地線網(wǎng)絡(luò)資源的優(yōu)化，本文提出了合理分配電源/地線引腳和改變電源線線寬的方法，并把它們嵌入到整個優(yōu)化過程中。實驗結(jié)果證明了本文采用的方法不僅提高了優(yōu)化流程的效率，也在保證版圖解的質(zhì)量的同時，優(yōu)化了電源/地線網(wǎng)絡(luò)的