集成電路互連時序優(yōu)化算法研究.pdf

1、隨著集成電路工藝的發(fā)展,互連線延時增大,而門延時逐漸減小,有研究表明,當(dāng)工藝特征尺寸減小到180納米以下時,互連線延時甚至可以占整個系統(tǒng)延時的50％以上，因此,互連線延時優(yōu)化在大規(guī)模集成電路設(shè)計中變得至關(guān)重要。
　　在互連線延時優(yōu)化中,論文通過緩沖器插入及尺寸調(diào)整和互連線線寬調(diào)整兩個方面來優(yōu)化互連線的延時。首先研究已有的緩沖器插入及尺寸調(diào)整算法和互連線線寬調(diào)整算法,分析它們的時間復(fù)雜度和運算速度的瓶頸,然后改進已有算法。針對緩沖器

2、插入及尺寸調(diào)整和互連線線寬調(diào)整兩種優(yōu)化方法,分別提出了相應(yīng)的改進算法。
　　論文基于Van Ginneken算法提出了一種新的緩沖器插入及尺寸調(diào)整算法。Van Ginneken算法是一種非常典型的緩沖器插入及尺寸調(diào)整優(yōu)化算法并且它的時間復(fù)雜度為O(b2n2),b為緩沖器的種類數(shù),n為候選緩沖器插入點個數(shù)。新算法中提出了一種快速冗余判別方法,并且使用紅黑樹結(jié)構(gòu)保存候選解,從而可以利用紅黑樹操作時間復(fù)雜度為O(log2n)的優(yōu)勢。經(jīng)過

3、改進,新算法的時間復(fù)雜度降至理論上為O(b2n(log2n)2)。利用標(biāo)準(zhǔn)測試電路ISCAS89對算法進行測試,測試結(jié)果表明,新算法相對于Van Ginneken算法的運算速度優(yōu)勢隨著電路規(guī)模的變大而變大,同時隨著候選緩沖器種類數(shù)的增加而增大,當(dāng)僅有1種緩沖器可選時,新算法運行時間大約是Van Ginneken算法的73.28%,而如果有8種和20種緩沖器可選,新算法運行時間大約是Van Ginneken算法運行時間的67.34%和63

4、.05%。
　　本文提出的線寬調(diào)整算法是在有效集合算法的基礎(chǔ)上提出的一種新算法,有效集合算法是解決二次規(guī)劃問題非常有效的方法,而線寬調(diào)整問題實際上就是凸二次規(guī)劃問題。新算法利用線寬調(diào)整問題中系數(shù)矩陣是對稱可分解矩陣的特點,實現(xiàn)逆矩陣的快速求解;并且本問題中的不等式約束條件非常特殊,如果某一個約束條件是有效的,那么其對應(yīng)的變量等于零,所以可以直接刪除這個變量,從而減少變量數(shù)。通過使用上述兩個技巧使得新算法的時間復(fù)雜度最壞情況下可從O