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

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

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

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

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

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