基于序列對的集成電路版圖布局算法研究.pdf

1、集成電路版圖(Layout)設(shè)計或物理設(shè)計(Physical Design)是VLSI設(shè)計中重要的一環(huán),也是最費時的一步.由于布圖的復(fù)雜性,整個布圖過程往往分成劃分、布圖規(guī)劃、布局、總體布線、詳細(xì)布線和壓縮等若干步驟,每一步驟完成布圖的一部分工作.本文目前所做的研究處于布圖規(guī)劃和布局設(shè)計階段.本文綜述了各種布圖表示方法,并對比各種方法的優(yōu)缺點,在此基礎(chǔ)上選取序列對(Sequence Pair,SP)作為主要的研究基礎(chǔ).以模擬退火算法作為

2、程序框架,實現(xiàn)了多種布局方法,其中提出了一種增量式的布局算法,該算法原理簡單、通用,可用于任何的實現(xiàn)框架之中,在優(yōu)化效果和運行時間上都具有一定的優(yōu)勢.文中還實現(xiàn)了兩個流行的用于搜索的數(shù)據(jù)結(jié)構(gòu):平衡二叉搜索樹和優(yōu)先級隊列,并且把它們用在基于SP的版圖布局中以加快運行速度.對一個給定的布局產(chǎn)生期序列對在很多情況下也是必須的,本文提出了一種快速的序列對的產(chǎn)生方法和相應(yīng)的一個簡便的算法.該算法性能優(yōu)越,實現(xiàn)簡單,并利用它證明了對于n個模塊組成的