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

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

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