芯片級多層布線關(guān)鍵技術(shù)研究.pdf

1、布線系統(tǒng)分成兩步：總體布線和詳細(xì)布線。為了降低問題復(fù)雜度，傳統(tǒng)布線通常采用基于均勻網(wǎng)格圖的有網(wǎng)格布線。但本質(zhì)上來講，布線資源是一個(gè)連續(xù)區(qū)域，布線應(yīng)該是可采用變線寬、變線間距的無網(wǎng)格布線。因此，隨著計(jì)算機(jī)硬件計(jì)算能力的不斷提高，國內(nèi)外對無網(wǎng)格布線的研究越來越多。 本論文在對國內(nèi)外有關(guān)無網(wǎng)格布線最新技術(shù)以及大規(guī)模布線問題中的各關(guān)鍵布線技術(shù)進(jìn)行深入研究和深刻總結(jié)的基礎(chǔ)上，針對性能驅(qū)動(dòng)的芯片級多層布線流程，對總體布線、無網(wǎng)格詳細(xì)布線等關(guān)

2、鍵技術(shù)進(jìn)行了深入研究，提出了時(shí)延和可制造性等多方面性能優(yōu)化的一系列有效的布線算法。同時(shí)我們也對作為總體布線和詳細(xì)布線橋梁的過點(diǎn)分配方法進(jìn)行了初步研究。 針對現(xiàn)有無網(wǎng)格布線算法以布通率為主要目標(biāo)，而很少考慮時(shí)延等性能優(yōu)化的現(xiàn)狀，本論文提出了一個(gè)時(shí)延驅(qū)動(dòng)的多層總體布線算法。算法采用一種多層次的“V”字形工作流程，分粗化和細(xì)化兩步完成布線。粗化階段，采用Top-Down的方式逐級縮小問題規(guī)模，直到到達(dá)能夠處理的層次；細(xì)化階段，采用Do

3、wn-Top的方式逐漸細(xì)化布線解，當(dāng)重新到達(dá)最頂層，總體布線解確定。在粗化階段的最粗層，針對大線網(wǎng)布線，專門提出了一個(gè)滿足時(shí)延約束的多線網(wǎng)布線算法。該算法通過引入軟邊和移動(dòng)斯坦納點(diǎn)概念，來推遲精確走線的確定時(shí)機(jī)，以避免過早固定走線帶來的盲目性，為布線提供更加全局化的考慮和極大的布線靈活性。 針對多層無網(wǎng)格區(qū)域布線的特性，需要一個(gè)新的過點(diǎn)分配算法CPA，以滿足噪聲約束，最小化通孔數(shù)。本論文對過點(diǎn)分配算法進(jìn)行了初步研究：首先根據(jù)障礙

4、物信息將小方塊邊界分解成多個(gè)區(qū)段，再分兩步解CPA問題：粗略過點(diǎn)分配CCPA和精細(xì)過點(diǎn)分配RCPA。在CCPA階段，根據(jù)噪聲約束計(jì)算每個(gè)過點(diǎn)的安全線間距并將其分配到一個(gè)區(qū)段。CCPA算法采用有效的圖布線算法，以最小化通孔數(shù)并確保沒有區(qū)段溢出為目標(biāo)；在RCPA階段，為每個(gè)過點(diǎn)確定精確的位置，使其滿足噪聲約束，并使同一線網(wǎng)的過點(diǎn)對對齊數(shù)最大化。 詳細(xì)布線階段，本論文提出了一種基于非均勻網(wǎng)格圖的多層無網(wǎng)格區(qū)域布線算法。算法首先通過一個(gè)

5、考慮時(shí)延性能的最小化半徑和費(fèi)用的生成樹算法MCSTMR將待布多端線網(wǎng)進(jìn)行解耦，形成兩端線網(wǎng)集合。然后通過一種自適應(yīng)迭代策略，將多層布線轉(zhuǎn)化為H-V布線層對序列來處理。當(dāng)處理單個(gè)H-V布線層對時(shí)，根據(jù)當(dāng)前處理的布線層對的障礙物集合，形成非均勻網(wǎng)格圖，為迷宮布線建立基礎(chǔ)圖模型。在非均勻網(wǎng)格圖上，利用改進(jìn)的迷宮布線算法順序處理兩端線網(wǎng)集合，獲得詳細(xì)布線解。針對布線無網(wǎng)格特性，論文主要改進(jìn)了迷宮算法的搜索策略，并通過二維區(qū)間樹這一特殊的數(shù)據(jù)結(jié)構(gòu)