基于Buffer插入的互連線性能優(yōu)化.pdf

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

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

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