超大規(guī)模集成電路物理設(shè)計(jì)中的直角斯坦納樹(shù)問(wèn)題.pdf

1、本文首先介紹了超大規(guī)模集成電路的物理設(shè)計(jì)流程，在此基礎(chǔ)上引出直角斯坦納樹(shù)問(wèn)題。許多已知算法考慮了有障礙的直角斯坦納樹(shù)問(wèn)題，但是對(duì)于布線區(qū)域存在邊界的情況并沒(méi)有涉及。布線區(qū)域的邊界不能簡(jiǎn)單地看作一維障礙的拼接，因?yàn)檫@樣會(huì)把凹的邊界切割下去，從而使導(dǎo)線跑到布線區(qū)域外邊。同時(shí)，在布線區(qū)域邊界不規(guī)則時(shí)會(huì)帶來(lái)不必要的運(yùn)算。
　　 本文介紹的賦權(quán)李算法就很好地克服了這個(gè)問(wèn)題。該算法的時(shí)間復(fù)雜度為O(n2(n+m)2log(n+m))，其中n

2、是終端的個(gè)數(shù)，m是障礙和邊界的頂點(diǎn)個(gè)數(shù)之和。
　　 同時(shí)本文提出了最小凸多邊形的技術(shù)，大大縮減了布線區(qū)域的面積，并且證明了在這個(gè)最小凸多邊形中存在最優(yōu)解，然后利用改進(jìn)的賦權(quán)李算法，給出次優(yōu)解。
　　 本文提到的算法，可以在運(yùn)算中剔除不需要考慮的障礙，從而進(jìn)一步減小運(yùn)算規(guī)模。實(shí)踐證明，該算法在布線區(qū)域邊界不規(guī)則，且終端成對(duì)角線狀排列時(shí)，能獲得最高的效率。
　　 對(duì)于多層布線的模型，本文將賦權(quán)李算法擴(kuò)展到三維，同時(shí)將