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

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

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