1、隨著集成電路技術(shù)的發(fā)展,器件的特征尺寸不斷減小。越來(lái)越小的器件尺寸給集成電路設(shè)計(jì)帶來(lái)了許多新的問(wèn)題,時(shí)序收斂是最突出的問(wèn)題之一。在集成電路時(shí)序中,互連線時(shí)序占據(jù)了越來(lái)越重要的地位。當(dāng)工藝尺寸進(jìn)入到納米尺寸之后,互連線延時(shí)超過(guò)了門(mén)延時(shí),成為了影響芯片總延時(shí)的關(guān)鍵因素。因此,為了滿足高性能芯片的時(shí)序收斂要求,互連線的時(shí)序優(yōu)化變得非常重要。
　　緩沖器插入是互連線時(shí)序優(yōu)化的主要策略之一。對(duì)于特定的布局樹(shù),在適當(dāng)?shù)墓?jié)點(diǎn)插入緩沖器可以起到降

2、低互連線關(guān)鍵路徑延時(shí)的作用。為了找到最優(yōu)的緩沖器插入方式,需要研究快速的緩沖器插入優(yōu)化算法。針對(duì)不同的緩沖器種類(lèi)、布局樹(shù)中漏端的數(shù)目和緩沖器待插節(jié)點(diǎn)數(shù)目,以往研究已經(jīng)提出了不同時(shí)間復(fù)雜度的緩沖器插入時(shí)序優(yōu)化算法,如時(shí)間復(fù)雜度為O(b2nlog2n)的算法。當(dāng)待插節(jié)點(diǎn)數(shù)目較大時(shí),該算法的效率仍舊比較低。
　　為了提高算法在緩沖節(jié)點(diǎn)數(shù)目較大時(shí)的效率,論文提出了時(shí)間復(fù)雜度為O(b2n+bmn)的算法。當(dāng)漏端數(shù)目固定時(shí),該算法明顯優(yōu)于時(shí)間

3、復(fù)雜度為O(b2nlog2n)的算法。這是通過(guò)兩個(gè)關(guān)鍵性技術(shù)來(lái)實(shí)現(xiàn)的:新的冗余solution刪除規(guī)則以及交叉節(jié)點(diǎn)預(yù)測(cè)技術(shù)。新的冗余solution刪除規(guī)則能夠最大限度的刪除冗余solution,經(jīng)過(guò)冗余刪除之后的solution具有特殊的性質(zhì),該性質(zhì)是實(shí)現(xiàn)算法線性時(shí)間復(fù)雜度的關(guān)鍵因素。交叉節(jié)點(diǎn)預(yù)測(cè)技術(shù)是通過(guò)采用特殊的數(shù)據(jù)結(jié)構(gòu),使得算法能夠預(yù)判下一節(jié)點(diǎn)是否為交叉節(jié)點(diǎn),并提前采取不同的冗余solution刪除規(guī)則。實(shí)驗(yàn)結(jié)果表明,對(duì)于同一電