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

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

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

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