一種基于網(wǎng)格的芯片布局密度控制方法

摘要：物理設(shè)計中，布局密度過高導(dǎo)致的擁塞是一直不可避免的問題.本文提出了一種基于網(wǎng)格劃分的密度控制方法來改善EDA工具在自動優(yōu)化擁塞方面的局限性，以Synopsys公司的后端工具IC Compiler為主要實驗工具，通過將目標(biāo)模塊劃分成網(wǎng)格（grid）的形式，分析每個網(wǎng)格內(nèi)的布局密度信息，對可能出現(xiàn)擁塞的區(qū)域通過算法進(jìn)行控制，以達(dá)到減少并解決布局擁塞的目的.實際工程試驗表明，該方法可以有效地解決模塊中由于布局密度過高引起的擁塞問題，同時改善了設(shè)計時序，具有較高的工程價值和實用性.

關(guān)鍵詞：網(wǎng)格劃分；布局密度；擁塞控制

中圖分類號：TN47 文獻(xiàn)標(biāo)識碼：A

A Method of Controlling Chip Layout Density

Based on Grid Division

HE Xiao-wei1， HAN Yu1， WANG Dong2， ZHAO Zhen-yu1

（1. College of Computer， National Univ of Defense Technology， Changsha， Hunan 410073， China；

2. Scientific Research Dept， National Univ of Defense Technology， Changsha， Hunan 410073， China）

Abstract： In physical design， local high density issue always results in place and routing congestion problems. This paper presented a method of controlling chip density based on grid division in order to alleviate the drawbacks of congestion-driven optimizations by EDA tools. This paper used Synopsys IC Compiler as major experiment tool， divided the design block into several grids， and analyzed the layout-density information within each grid to control and optimize the possible congestion areas. Meanwhile， the design timing has also been improved. The effectiveness and feasibility of this strategy has been verified with actual project examples.

Key words： grid division； layout density； congestion control

隨著半導(dǎo)體技術(shù)的發(fā)展，每一代工藝大體上將有效溝道長度降到前一代的0.7倍，芯片集成度極大地提高^[1].在后端設(shè)計中通過EDA工具對標(biāo)準(zhǔn)單元進(jìn)行布局時，這些單元并不會均勻地分布在芯片上，而是會根據(jù)邏輯劃分、時序優(yōu)先等布局引導(dǎo)來被放置.這就會導(dǎo)致在邏輯模塊交匯或布線通道附近等時序關(guān)鍵區(qū)域被擺放大量單元，而芯片的四周邊角的區(qū)域卻只有少量單元^[2].這使得在后端設(shè)計過程中，隨著優(yōu)化的進(jìn)行，各種優(yōu)化單元的不斷插入，芯片在總體單元利用率不是很高的情況下也會出現(xiàn)局部布局密度過高的情況，從而產(chǎn)生擁塞.

擁塞通常出現(xiàn)在時序關(guān)鍵區(qū)域，這種區(qū)域在布局階段擺放的單元數(shù)目就很多，在后續(xù)優(yōu)化階段還會插入大量的單元，所以極易形成擁塞，導(dǎo)致繞線、電遷移、功耗密度不均勻甚至無法繼續(xù)優(yōu)化等問題，嚴(yán)重影響了芯片的性能和穩(wěn)定性；同時局部單元數(shù)目過多也會導(dǎo)致局部線網(wǎng)密度提高，這對芯片的可制造性也將產(chǎn)生極大的影響，所以如何解決擁塞問題一直是集成電路設(shè)計中的重要課題^[3].

本文以Synopsys公司的后端工具IC Compiler為主要實驗工具，主要通過將目標(biāo)模塊劃分成網(wǎng)格（grid）的形式，分析每個網(wǎng)格內(nèi)的布局密度信息，對可能出現(xiàn)擁塞的區(qū)域進(jìn)行控制與優(yōu)化，以達(dá)到減少或解決布局擁塞的目的.實際工程證明，該方法可有效解決芯片布局密度過高引起的擁塞問題，極大地減少了設(shè)計過程中的迭代次數(shù)，縮短了設(shè)計周期.

1 布局擁塞概述

雖然設(shè)計流程中在邏輯綜合階段會進(jìn)行擁塞的優(yōu)化，但是在后端設(shè)計過程中依然會不可避免地出現(xiàn)擁塞問題.如果要用更加準(zhǔn)確的算法來控制后端流程中可能出現(xiàn)的擁塞情況，就必須了解在后端流程的不同階段可能會影響到布局密度變化的情況.

在后端設(shè)計流程中，常常因為優(yōu)化而需要插入或者改動單元，從而導(dǎo)致布局密度升高.這也正是在邏輯綜合時無法預(yù)估到物理設(shè)計后期擁塞分布的原因.可能造成設(shè)計出現(xiàn)布局擁塞的情況包括：標(biāo)準(zhǔn)單元的尺寸變動；插入普通緩沖器或時鐘單元，時鐘單元具有相同的上升和下降時間，在時鐘樹綜合時可以使時鐘信號獲得較好的占空比（duty cycle）^[4]；插入延時單元；插入防閂鎖單元等.

為適應(yīng)芯片設(shè)計的需要，人們在分析標(biāo)準(zhǔn)單元通道布線結(jié)構(gòu)的基礎(chǔ)上發(fā)明了新的啟發(fā)式算法，并將其應(yīng)用在EDA工具中，逐漸發(fā)展成擁塞驅(qū)動的布局算法，包括基于網(wǎng)格^[5]和非基于網(wǎng)格^[6]兩類.這兩類算法都以互連線為中心，在初期布線有很高的成功率.但其對單元擺放的控制太寬泛，不能有效地約束關(guān)鍵區(qū)域的布局密度，導(dǎo)致在后期布線時，特別是對于長路徑和布局密度高的區(qū)域，布通率下降明顯.

隨著IC設(shè)計水平的提升，物理設(shè)計中已經(jīng)有很多趨于成熟的策略可以用來解決設(shè)計過程中出現(xiàn)的擁塞問題.根據(jù)執(zhí)行者的不同，將其分為工具優(yōu)化和人工優(yōu)化兩種.

人工優(yōu)化一般分為兩種，一種是在布圖規(guī)劃階段通過合理擺放宏單元，設(shè)置布局/布線屏蔽層等方法來預(yù)防擁塞的發(fā)生；另一種則是在布局之后的階段，通過刪除冗余緩沖單元、減小單元尺寸、利用公共路徑插入緩沖單元等方法來解決擁塞問題.第一種方法的準(zhǔn)確度不高，往往要經(jīng)過數(shù)次迭代才能找到合適的方案；第二種方法面向的對象可具體到每一條路徑、每一個單元，準(zhǔn)確度極高，但非常依賴于布局，優(yōu)化空間較小，并且當(dāng)出現(xiàn)大規(guī)模擁塞的情況時，過于精細(xì)的分析反而使得優(yōu)化周期極大地增加.

因此如何結(jié)合兩種方法的優(yōu)勢，進(jìn)一步加強(qiáng)對密度的控制是具有較高工程價值的研究.本文通過劃分網(wǎng)格的形式，在EDA工具算法的基礎(chǔ)上加強(qiáng)對局部密度的控制，其中的擁塞預(yù)估將優(yōu)化過程中插入的延時單元面積考慮在內(nèi)，大大地增加了預(yù)估結(jié)果的準(zhǔn)確性.

2 理論研究與算法實現(xiàn)

2.1 網(wǎng)格劃分

將物理設(shè)計的模塊劃分為網(wǎng)格形式（如圖1所示），每個網(wǎng)格都包含一定的標(biāo)準(zhǔn)單元，通過指導(dǎo)布局過程使得布局擁塞度與特定的網(wǎng)格相關(guān)，從而達(dá)到控制局部密度的目的.

在布局的初始階段就需要確定網(wǎng)格的劃分，劃分網(wǎng)格時應(yīng)遵循以下原則：

1）網(wǎng)格之間應(yīng)該相互緊貼，并且不能重疊.

2）網(wǎng)格應(yīng)當(dāng)覆蓋該設(shè)計模塊的所有單元布局區(qū)域.

3）從算法復(fù)雜性考慮，盡量保證劃分的所有網(wǎng)格大小一致.

對于網(wǎng)格的面積，主要從兩方面考慮：第一是網(wǎng)格面積對后續(xù)優(yōu)化準(zhǔn)確性和效果的影響，第二是對優(yōu)化過程中插入的延時單元輸出翻轉(zhuǎn)時間的影響.這兩點若不分析清楚，將會使得后續(xù)優(yōu)化算法的實用性大打折扣.

從計算復(fù)雜性和誤差考慮，網(wǎng)格面積劃分得越大越好，但過大的網(wǎng)格會由于優(yōu)化時其內(nèi)部插入的延時單元距離目標(biāo)寄存器太遠(yuǎn)而產(chǎn)生翻轉(zhuǎn)時間違例.所以必須根據(jù)延時單元的驅(qū)動能力來限制網(wǎng)格面積.在實際設(shè)計中應(yīng)權(quán)衡兩者關(guān)系做出最優(yōu)選擇.

2.2 布局密度預(yù)估與控制

對于一個已經(jīng)完成標(biāo)準(zhǔn)單元放置的布局，其局部密度的定義為：

db（ei） = Cb（ei） /Ab（ei）.（1）

式中：Cb（ei）為分配在某一個網(wǎng)格ei中的標(biāo)準(zhǔn)單元總面積；Ab（ei）為該網(wǎng)格的面積.

最大密度的定義為：

D（B） = max db（ei），i = 1，2，…

布局的目標(biāo)是在不影響時序的前提下，盡量令D（B）最小化，即讓標(biāo)準(zhǔn)單元均勻分布，以減少局部擁塞率.

僅僅對布局之后的密度進(jìn)行分析的效果并不理想，因為標(biāo)準(zhǔn)單元放置完畢之后，還未進(jìn)行時序優(yōu)化.由于無法預(yù)估到未來進(jìn)行時序優(yōu)化時網(wǎng)表的變動，所以不能判斷每個網(wǎng)格在之后優(yōu)化過程中的密度變動.若在此時通過分析局部密度來設(shè)置約束，只有兩種辦法：

1）僅對已經(jīng)確定密度較高的網(wǎng)格設(shè)置約束，其優(yōu)點是準(zhǔn)確性高，對時序基本沒有影響；缺點是約束的網(wǎng)格數(shù)量少，對密度的控制力度較小.

2）對全部網(wǎng)格都設(shè)置密度約束，優(yōu)點是對密度的控制效果明顯，可以看成是所有單元被均勻分布在模塊的每個網(wǎng)格內(nèi)，基本保證每個區(qū)域內(nèi)都有空間進(jìn)行后續(xù)優(yōu)化；缺點是約束的網(wǎng)格較多，單元容易被布局屏蔽層推得過于分散，對時序影響較大.

這兩種方法雖然都可以做到密度控制，但是也都存在明顯的不足.所以我們要進(jìn)行更加有效的干預(yù)，就必須對密度過高的原因進(jìn)行更細(xì)致的分析.

在物理設(shè)計流程中，EDA工具在優(yōu)化過程中為了修復(fù)建立時間和保持時間違例會插入不同類型的緩沖單元，雖然我們不能預(yù)估建立時間優(yōu)化時插入的緩沖單元的位置，但在修復(fù)保持時間違例時，特別是在修復(fù)掃描模式的保持時間階段，插入的緩沖單元卻是可以預(yù)先判定位置的.因此，可以在布局之后提取設(shè)計中所有寄存器的位置信息，然后根據(jù)每個網(wǎng)格內(nèi)含有的寄存器數(shù)目計算出該網(wǎng)格在修復(fù)保持時間時可能需要的空間，將這個信息和密度綜合成新的擁塞預(yù)估標(biāo)準(zhǔn).

由式（1）知道，對于網(wǎng)格ei，其局部密度為db（ei） = Cb（ei）/Ab（ei） ，設(shè)網(wǎng)格ei內(nèi)有N個寄存器，為每個寄存器在修復(fù)保持時間時預(yù)留的空間為K，所以，對于該設(shè)計中的網(wǎng)格，其局部單元擁塞度的定義為：

Con（ei） = db（ei） + N（ei）K/Ab（ei）.

綜合可得：

Con（ei） = [Cb（ei） + N（ei）K]/Ab（ei）.（2）

對于網(wǎng)格ei而言，其局部單元擁塞度為布局完成之后，該網(wǎng)格內(nèi)所有單元的面積及為網(wǎng)格內(nèi)部所有寄存器預(yù)留面積之和與網(wǎng)格總面積之比.

使用式（2）定義的局部單元擁塞度作為布局階段的網(wǎng)格密度評估標(biāo)準(zhǔn)，比之前使用的式（1）更加精確，不但從局部密度來分析單元擁塞，而且考慮到了修復(fù)保持時間違例時的擁塞來源，增強(qiáng)了布局對流程后期的擁塞影響.新的最大單元擁塞度的定義為：

Con（B） = max [db（ei） + N（ei）K/Ab（ei）]，i = 1，2， …

可以看出，如果要讓Con（B）最小，不但要將標(biāo)準(zhǔn)單元分布均勻，還要避免某一區(qū)域寄存器分布過多.這樣等于將時序關(guān)鍵區(qū)域的單元均勻擴(kuò)散，保證了優(yōu)化的空間.

2.3 算法實現(xiàn)

基于網(wǎng)格的密度預(yù)估布局所采用的算法只需要通過預(yù)估，得到每個網(wǎng)格的局部密度即可.具體的算法實現(xiàn)步驟如下：

1）設(shè)計文件輸入以及布局.首先要有一個已經(jīng)確定的布局來避免迭代.將輸入信息讀入EDA工具，并進(jìn)行標(biāo)準(zhǔn)單元擺放.對已經(jīng)擺放的標(biāo)準(zhǔn)單元進(jìn)行時序優(yōu)化和物理位置優(yōu)化，使得初始寄存器的位置基本固定.

2）網(wǎng)格劃分.在標(biāo)準(zhǔn)單元布局完成之后，就可以開始網(wǎng)格的劃分.根據(jù)網(wǎng)格劃分的原則來劃分網(wǎng)格，保證網(wǎng)格覆蓋整個模塊.值得注意的一點是，將網(wǎng)格的垂直長度設(shè)置成單元區(qū)（row）的整數(shù)倍，可以減少復(fù)雜度并提高準(zhǔn)確性.

3）網(wǎng)格擁塞計算.在網(wǎng)格劃分完成后，開始計算網(wǎng)格的擁塞度.從第一個網(wǎng)格開始計算，通過面積坐標(biāo)信息將該網(wǎng)格內(nèi)的單元提取出來，然后將處于網(wǎng)格內(nèi)的單元面積進(jìn)行累加，最后除以網(wǎng)格總面積，即可得到網(wǎng)格的當(dāng)前密度db（ei）.對于預(yù)估的面積N（ei）K也采用同樣的方法.通過坐標(biāo)判斷寄存器是否在當(dāng)前網(wǎng)格內(nèi)，如果不在就跳過該寄存器，如果在，則當(dāng)前網(wǎng)格內(nèi)寄存器數(shù)目加1，直到所有寄存器遍歷完畢.在得到當(dāng)前網(wǎng)格的布局密度和寄存器數(shù)目之后，即可進(jìn)行下一網(wǎng)格的擁塞計算.

4）設(shè)置約束.對于處在中心區(qū)域布局密度較高的網(wǎng)格，可以設(shè)置較嚴(yán)格的布局約束；對于處在邊角非關(guān)鍵區(qū)域、布局密度很低的網(wǎng)格，可以設(shè)置較寬松的約束或者不用設(shè)置約束.

具體的約束標(biāo)準(zhǔn)是以網(wǎng)格內(nèi)的寄存器數(shù)目為標(biāo)準(zhǔn)的.擁有較多寄存器的網(wǎng)格意味著在未來優(yōu)化中可能被插入更多的單元.對于一個擁塞度為Con（ei） = db（ei） + N（ei）K/ Ab（ei）的網(wǎng)格，需要預(yù)留的面積通常為N（ei）K的1.3～2.1倍，可根據(jù)不同的需求來進(jìn)行設(shè)置.

最后將約束信息輸出成tcl腳本形式，以便在下一步中應(yīng)用.

5）重新布局.在約束設(shè)置完畢后，需要重新布局及擺放標(biāo)準(zhǔn)單元.在布局階段讀入上一步中生成的設(shè)置腳本，使得新的單元擺放遵循約束規(guī)范.

6）擁塞檢查.在新的布局生成之后，還要對該布局進(jìn)行一次擁塞檢查.目的是防止一些在第一次布局中沒有注意到的網(wǎng)格在第二次布局后產(chǎn)生擁塞.

以上6步完成之后，基于網(wǎng)格的密度控制布局就完成了，詳細(xì)的算法流程圖如圖2所示.

3 實驗結(jié)果

實驗實例為一個百萬門級的設(shè)計模塊，該模塊面積為1 380 μm×1 300 μm，含有58 776個寄存器，161 236個標(biāo)準(zhǔn)單元，時鐘周期為700 ps.雖然該模塊布局階段的單元利用率并不高，但是由于單元擺放不均勻，在中間區(qū)域集中了80%以上的單元，而周圍區(qū)域只擺放了一些與I/O引腳有關(guān)的單元，所以在優(yōu)化過程中仍然可能出現(xiàn)擁塞.我們采用兩套流程對該模塊進(jìn)行后端設(shè)計，不同點在于第一套流程在布局階段的腳本中嵌入了本章研究的布局密度控制腳本；另一套流程采用的是正常后端設(shè)計的腳本，在每個階段都會進(jìn)行一次EDA工具自帶的擁塞優(yōu)化.

為方便對比，兩套流程中均不采用任何ECO手段.首先對模塊進(jìn)行網(wǎng)格劃分，分割成21×20共420個網(wǎng)格，每個網(wǎng)格面積為65.52 μm×65 μm = 4 258.8 μm2，網(wǎng)格劃分之后的模塊如圖3所示.

下面分別給出了兩套流程在不同階段每個網(wǎng)格的擁塞度對比以及靜態(tài)時序分析的報告.為了更清楚更直觀地分析不同階段的局部擁塞，將網(wǎng)格擁塞度以散點圖的形式表現(xiàn)出來，圖4和圖5分別為兩套流程在布局階段局部擁塞度對比.圖中橫坐標(biāo)為網(wǎng)格內(nèi)的局部密度，縱坐標(biāo)為網(wǎng)格內(nèi)的寄存器數(shù)目，每一個散點代表一個網(wǎng)格，從圖中可以清楚地看到每一個網(wǎng)格區(qū)域的布局密度與寄存器數(shù)目.

圖4為該模塊使用正常流程時，在布局之后的各網(wǎng)格擁塞度情況.可以看到，在布局階段，大部分網(wǎng)格的布局密度已經(jīng)接近0.8，一些網(wǎng)格的布局密度甚至已經(jīng)超過0.9.圖5為采用密度控制之后的布局擁塞示意圖，可知在通過對布局密度較高和寄存器密集區(qū)域進(jìn)行了控制之后，大部分網(wǎng)格的布局密度降低到了0.6左右，只有少數(shù)網(wǎng)格超過0.8，效果非常明顯.同時網(wǎng)格內(nèi)寄存器數(shù)目的最大值也從350左右減少到了不到300，max Con（B）降低了11%.

違例后，模塊布局密度有了較大的增加.圖6中大部分網(wǎng)格的布局密度都達(dá)到或接近1，這些網(wǎng)格所包含區(qū)域的布局空間趨于飽和，并且可能已經(jīng)產(chǎn)生擁塞.圖7為采用了密度控制的流程在簽核階段的擁塞示意圖，可看到雖然布局密度同樣有大幅提升，但大部分網(wǎng)格的布局密度維持在0.9左右，即在這些區(qū)域仍有10%左右的空間可供使用，說明這些區(qū)域尚未產(chǎn)生擁塞.

下面我們將兩套流程在簽核階段的時序結(jié)果進(jìn)行比較.表1為該模塊在簽核階段的PT時序報告，其中func和shift分別代表功能模式和掃描模式；后綴為max的端角為檢查建立時間的端角，后綴為min的端角為檢查保持時間的端角；WNS代表最關(guān)鍵路徑的違反時間；VPN代表關(guān)鍵路徑的條數(shù).

從表1的時序報告中可看出，該模塊在使用常規(guī)流程完成簽核階段優(yōu)化后還有將近30 000條保持時間的關(guān)鍵路徑?jīng)]有被修復(fù).這是由于在該階段出現(xiàn)了明顯的擁塞問題.沒有足夠空間進(jìn)行保持時間修復(fù). EDA工具本身的擁塞優(yōu)化不但未能解決問題，反而影響到了模塊的建立時間，優(yōu)化已經(jīng)無法繼續(xù)進(jìn)行，只能回到布局階段甚至將網(wǎng)表重新綜合后再進(jìn)行新的流程.

而采用了密度控制的流程在該階段很好地完成了優(yōu)化任務(wù)，所有模式下的保持時間已經(jīng)基本修復(fù)完畢，而且建立時間也沒有出現(xiàn)大幅度的惡化.后續(xù)只需要進(jìn)行一些ECO的時序優(yōu)化，就可以令時序收斂達(dá)到簽核的標(biāo)準(zhǔn).

通過以上的實驗結(jié)果以及圖表分析，可以很清楚地看到密度控制在實際后端流程中的作用.在布局階段進(jìn)行密度控制之后，完全避免了后續(xù)階段的擁塞問題，減少了迭代的工作，縮短了設(shè)計周期.

4 結(jié) 論

本文針對物理設(shè)計中EDA工具對芯片布局密度控制不力從而容易導(dǎo)致產(chǎn)生擁塞的問題，提出了一種通過將布局區(qū)域劃分為網(wǎng)格形式來加強(qiáng)對局部掌控的布局密度控制算法.實際工程試驗結(jié)果表明，該算法可以較好地解決芯片的布局擁塞問題，減少物理設(shè)計流程中的迭代次數(shù)，縮短了設(shè)計周期.

參考文獻(xiàn)

[1] 趙繼業(yè)， 楊旭.納米級工藝對物理設(shè)計的影響[J].信息技術(shù)快報，2008，6（2）：25-34.

ZHAO Ji-ye， YANG Xu. The affect of nano-process to physical design[J]. Information Technology Letter， 2008，6（2）：25-34. （In Chinese）

[2] MARKOV I L. Capo： congestion-driven placement for standard cell and RTL netlists with incremental capability[D]. Ann Arbor， Michigan： University of Michigan， 2010： 99-110.

[3] 唐有情.納米級工藝下系統(tǒng)級芯片的物理設(shè)計[J].中國科技信息，2010（5）：50-51.

TANG You-qing. The physical design of system-on-chip in nano-process[J]. China Science and Technology Information， 2010（5）：50-51.（In Chinese）

[4] TSMC.90/80/65/55/45/40nm standard cell library application note（Version 1.9）[R].Xinzhu： TSMC， 2009.

[5] YANG B， YU J， YAN T， et al. An obstacle detoured routing algorithm based on the enhanced ACS[C]// Proceedings of 2004 International Conference on Communications， Circuits and Systems.Washington， DC： IEEE Computer Society， 2004：1286-1289.

[6] CONG J， FANG J， KHOO K Y. DUNE—a multilayer gridless routing system[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems， 2001，20（5）：633-647.