陳秀華

(福建船政交通職業(yè)學(xué)院 公共教學(xué)部，福建 福州 350007)

基于密度控制的多倍高單元詳細(xì)布局算法

陳秀華

(福建船政交通職業(yè)學(xué)院 公共教學(xué)部，福建 福州 350007)

針對(duì)多倍高單元詳細(xì)布局問(wèn)題，提出了一種基于密度控制的高效多倍高單元詳細(xì)布局方法。首先給出一種新的多倍高標(biāo)準(zhǔn)單元密度計(jì)算方法，接著提出一種嵌套式動(dòng)態(tài)規(guī)劃的高效算法用于優(yōu)化詳細(xì)布局中的線長(zhǎng)和密度2個(gè)目標(biāo)，采用標(biāo)準(zhǔn)的測(cè)試?yán)蛹M(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明，文中所提出的算法可以在合理的運(yùn)行時(shí)間里得到很好的詳細(xì)布局結(jié)果。

多倍高單元;詳細(xì)布局;密度控制;動(dòng)態(tài)規(guī)劃

0 引言

超大規(guī)模集成電路(Very Large Scale Integration，VLSI)設(shè)計(jì)中的布局一般分為3個(gè)階段：全局布局、合法化布局和詳細(xì)布局。全局布局一般是基于線長(zhǎng)最小化目標(biāo)來(lái)確定每個(gè)單元的大概位置，也可以根據(jù)布線或時(shí)延等目標(biāo)來(lái)確定單元的位置。但全局布局的結(jié)果經(jīng)常是重疊的，需要通過(guò)合法化來(lái)消除重疊的單元并重新確定單元的位置。詳細(xì)布局通過(guò)局部移動(dòng)單元位置來(lái)優(yōu)化布局的質(zhì)量。詳細(xì)布局是VLSI設(shè)計(jì)中非常關(guān)鍵的一個(gè)環(huán)節(jié)，對(duì)芯片的質(zhì)量有重大影響。

在當(dāng)前超大規(guī)模集成電路設(shè)計(jì)中，一直只考慮單倍高的標(biāo)準(zhǔn)單元。隨著技術(shù)的發(fā)展，依據(jù)不同的特征，如：時(shí)延、封裝、引腳可訪問(wèn)性等，各種不同寬度和高度的單元被使用[1]。隨著標(biāo)準(zhǔn)單元的高度變得越來(lái)越小，為滿足布線特征等各種要求，電路元件設(shè)計(jì)的復(fù)雜度也不斷增加。此外，為了滿足面積、功率和低成本等要求，布局密度經(jīng)常高達(dá)90%，幾乎接近極限，詳細(xì)布局就成了解決局部線路擁堵問(wèn)題的關(guān)鍵[2]。在一個(gè)極其密集的設(shè)計(jì)中，如果不破壞局部布局，只靠合法化和詳細(xì)布局插入或移動(dòng)大的單元幾乎是不可能的。此外，在給定的單元庫(kù)中每個(gè)單元的引腳數(shù)和面積是不一樣的，并且引腳數(shù)和面積大小無(wú)關(guān)，當(dāng)引腳數(shù)大的單元個(gè)數(shù)過(guò)多時(shí)就會(huì)造成局部擁堵。因此在給定芯片面積的情況下，采用合適的方法同時(shí)優(yōu)化線長(zhǎng)和消除擁堵是至關(guān)重要的。

吳剛等在文獻(xiàn)[3]中首次提出一種技術(shù)來(lái)處理雙倍高單元的詳細(xì)布局，使用單元分組和單元膨脹將單倍高單元轉(zhuǎn)化成雙倍高單元，使得在布局中只有雙倍高單元。然而，這種方法無(wú)法處理多倍高單元的電源線對(duì)齊約束，也不能處理3倍高以上的單元。文獻(xiàn)[4]則首次提出了關(guān)于位移最小化目標(biāo)的多倍高合法化算法，考慮了布局中的插入點(diǎn)，并在位移最小化目標(biāo)下試圖消除重疊單元。

1 問(wèn)題描述及其數(shù)學(xué)模型

(1)

式(1)中，N表示網(wǎng)表(線網(wǎng)的集合)。

平均格子利用率(ABU)是用來(lái)評(píng)估布局密度的一種方法。ABUγ表示密度在前γ%的格子的平均值?；诿芏鹊腁BU罰定義成overflow的權(quán)重和，其方程如下：

(2)

(3)

式(2)～(3)中，dt為目標(biāo)利用率;ω2,ω5,ω10,ω20設(shè)為10，4，2，1。在2013年ICCAD布局競(jìng)賽中定義廣義的線長(zhǎng)包括線長(zhǎng)密度花費(fèi)，如公式(4)：

sHPWL=HPWL(1+ABU)

(4)

其中，計(jì)算ABU時(shí)只包括單元面積利用率。隨著技術(shù)的發(fā)展，面積利用率已經(jīng)不是計(jì)算擁堵的最佳辦法。因?yàn)橐恍┐蟮膯卧赡馨苌俚囊_，而一些小的單元卻可能有很多引腳連接、很多線網(wǎng)，所以我們提出平均引腳利用率(APU)來(lái)計(jì)算布局中的引腳分布。每個(gè)單元的引腳密度為引腳數(shù)與格子(將布局區(qū)域劃分成大小相同的格子)位置的比例。一旦獲得引腳密度分布，則APU罰的計(jì)算跟ABU相同。

多倍高詳細(xì)布局(MrDP)問(wèn)題的定義如下：

給定一個(gè)初始多倍高標(biāo)準(zhǔn)單元布局和一些固定宏塊，不管該布局合不合法，為優(yōu)化線長(zhǎng)和密度而得到的一個(gè)合理的、高質(zhì)量的解決方案，即sHPWL和APU最小。

2 多倍高單元詳細(xì)布局算法

2.1 算法的整體框架

詳細(xì)布局算法見(jiàn)表1。對(duì)總體布局給定布局的解決方案，首先檢查該布局是否合法。如果不合法，則去除重疊執(zhí)行并使多倍高單元的電源線對(duì)齊。在這一步中，首先執(zhí)行鏈移動(dòng)算法(表2)以減少單元重疊，因?yàn)槌跏嫉慕鉀Q方案可能包含許多重疊導(dǎo)致合法化難以進(jìn)行；接下來(lái)再利用文獻(xiàn)[2]中德?tīng)柡戏ɑ瘉?lái)確保位移最??；然后同時(shí)優(yōu)化線長(zhǎng)和密度直至算法達(dá)到最大步或者不超過(guò)1%的單元可以移動(dòng)時(shí)終止。在實(shí)驗(yàn)中最多允許迭代6次，在最終布局前提出嵌套式動(dòng)態(tài)規(guī)劃算法(表3)來(lái)優(yōu)化線長(zhǎng)。

表1 詳細(xì)布局算法

表2 鏈移動(dòng)算法

表3 嵌套式動(dòng)態(tài)規(guī)劃算法

2.2 鏈移動(dòng)算法

詳細(xì)布局通常是通過(guò)cell-by-cell manner 方法來(lái)優(yōu)化線長(zhǎng)，即一個(gè)單元試圖與另一個(gè)單元交換或移到更好的位置，從而得到更好的線長(zhǎng)[6-8]，該方法對(duì)單倍高詳細(xì)布局十分有效。多倍高單元因占據(jù)多個(gè)行，會(huì)使更多的單元產(chǎn)生重疊，如果仍用此方法將導(dǎo)致布局失敗。如果沒(méi)有擾動(dòng)，則至少2個(gè)單元很難再插入另一個(gè)多行高度單元，類似的情況也會(huì)發(fā)生在其他大的單元上。根據(jù)文獻(xiàn)[9]密度的重新定義和文獻(xiàn)[10-11]中獲得的映射形式，采用允許其他單元同時(shí)移動(dòng)以優(yōu)化單個(gè)目標(biāo)單元的策略,具體算法框架見(jiàn)表2。

2.3 嵌套式最短路徑問(wèn)題

有序多倍高布局問(wèn)題通常將轉(zhuǎn)化成有上下限的嵌入式最短路徑問(wèn)題，然后采用嵌入式動(dòng)態(tài)規(guī)劃算法來(lái)解決。定義最大位移量為M，則每個(gè)單元的位移值為K=2M+1。令Zij表示分裂單元Zi在第j位置；r表示在Rdr上分裂單元的個(gè)數(shù)；b表示在Rdr上行單元的個(gè)數(shù)；t表示在Rdr下行單元的個(gè)數(shù)。

有序多倍高單元布局問(wèn)題中一個(gè)關(guān)鍵點(diǎn)在于：對(duì)于每個(gè)劃分即子問(wèn)題都是獨(dú)立的，所以分裂單元的位置可以被固定下來(lái)。例如，在單元e 的位置固定下來(lái)后，劃分的單元就變得獨(dú)立了。如果可以固定分裂單元的位置，那么原問(wèn)題就可以分解成一個(gè)個(gè)子問(wèn)題。因此，將原問(wèn)題轉(zhuǎn)化成了嵌入式最短路徑問(wèn)題，其中outer-level 問(wèn)題(求最短路徑問(wèn)題)是為了求出分裂單元的位置，inner-level是關(guān)于邊的權(quán)重問(wèn)題。

outer-level 最短路徑算法中每個(gè)節(jié)點(diǎn)表示分裂單元的候選位置，本算法需要求從s到t的最短路徑。在預(yù)先知道獨(dú)立的性質(zhì)下，可以通過(guò)求解inner-level問(wèn)題計(jì)算出各邊的權(quán)重。由于沒(méi)有橫跨矩形區(qū)域的單元，所以這2個(gè)問(wèn)題相互獨(dú)立。

2.4 嵌套式動(dòng)態(tài)規(guī)劃算法

關(guān)于優(yōu)化線長(zhǎng)和合法化的有序單倍高布局已得到較為廣泛的研究[12-16]，本文采用嵌套式動(dòng)態(tài)規(guī)劃的算法來(lái)有效解決多倍高單元詳細(xì)布局問(wèn)題。表3給出了嵌套式動(dòng)態(tài)規(guī)劃算法的框架。通過(guò)SolveOuterLevel 函數(shù)求outer-level問(wèn)題，SolveOuterLevel的核心程序是7～15行中的3個(gè)循環(huán)。每個(gè)候選位置的花費(fèi)通過(guò)ComputeDPCost函數(shù)來(lái)計(jì)算。通過(guò)SolveInnerLevel函數(shù)來(lái)求解每個(gè)劃分的inner-level 花費(fèi)問(wèn)題。在每個(gè)劃分里，利用SolveInnerLevel里面的ComputeDPCost函數(shù)分別計(jì)算上下行的花費(fèi)。由于inner-level 問(wèn)題在理想情況下與單倍高問(wèn)題相同，本文省略其中的細(xì)節(jié)。

ComputeDPCost的線長(zhǎng)花費(fèi)采用文獻(xiàn)[5]中定義單倍高布局的花費(fèi)函數(shù)計(jì)算。如果單元Ci與單元Cj在同一行，并且Cj在Ci的左邊，那么假設(shè)Cj在這一行最左邊的位置，并計(jì)算此時(shí)的線長(zhǎng)花費(fèi)。如果單元Ci與單元Cj在同一行，并且Cj在Ci的右邊，那么假設(shè)Cj在這一行最右邊的位置，并計(jì)算此時(shí)的線長(zhǎng)花費(fèi)。如果單元Ci與單元Cj不在同一行，就按它們所在的真實(shí)位置計(jì)算。這樣的計(jì)算結(jié)果與單倍高布局里的HPWL等價(jià)，也與理想情況下的雙倍高布局相同。

算法3的運(yùn)行時(shí)間復(fù)雜度為O(M2n)，其中n表示在矩形區(qū)域里的單元的個(gè)數(shù)?？紤]被r個(gè)單元?jiǎng)澐殖蓃+1個(gè)塊，在每個(gè)塊(劃分)中，下行有bi個(gè)單元，上行有ti個(gè)單元。假設(shè)ComputeDPCost只需時(shí)間為常數(shù)且n遠(yuǎn)大于r。文獻(xiàn)[17]中用來(lái)解決單倍高布局的動(dòng)態(tài)規(guī)劃算法只需要O(Mn)的時(shí)間復(fù)雜度。所以在SolveInnerLevel中對(duì)每個(gè)劃分的計(jì)算需要O(Mbi)+O(Mti)的時(shí)間復(fù)雜度。算法3的時(shí)間復(fù)雜度為：

(5)

本文提出線長(zhǎng)、單元密度、引腳密度的多倍高詳細(xì)布局算法，主要貢獻(xiàn)為：

1)為優(yōu)化線長(zhǎng)、單元密度、引腳密度，提出關(guān)于多倍高的鏈移動(dòng)方法。

2)采用嵌套式動(dòng)態(tài)規(guī)劃高效解決有序的多倍高線長(zhǎng)優(yōu)化布局。

3)本文方法與最新的詳細(xì)布局相比能提高3%的線長(zhǎng)規(guī)模，在單元密度上提高了13.2%，在引腳密度上提高了13.3%。

3 實(shí)驗(yàn)結(jié)果

本文算法在主頻3.4 GHz、內(nèi)存32 G的Linux操作系統(tǒng)下用C++實(shí)現(xiàn)，采用文獻(xiàn)[1]提供的ISPD05 placement benchmark測(cè)試數(shù)據(jù)(表4)進(jìn)行仿真實(shí)驗(yàn)和驗(yàn)證，在HPWL、sHPWL、CPU等方面與文獻(xiàn)[1]算法進(jìn)行對(duì)比，算法實(shí)驗(yàn)結(jié)果比較見(jiàn)表5。

表4 ISPD05測(cè)試數(shù)據(jù)集[1]

表5 算法實(shí)驗(yàn)結(jié)果比較

在合理的運(yùn)行時(shí)間內(nèi)，本文所提出的算法在HPWL、sHPWL、ABU的罰和APU的罰等方面比文獻(xiàn)[1]算法的結(jié)果均有明顯提高。對(duì)于表4中的所有實(shí)例，在HPWL方面，本文算法都比文獻(xiàn)[1]算法明顯縮短，平均縮短了1.2%；在sHPWL方面，平均縮短了3.0%; ABU的罰比文獻(xiàn)[1]平均減少了13.3%；APU的罰比文獻(xiàn)[1]平均減少了13.2%。由此說(shuō)明本文算法可獲得更好的單元格密度，得到較好的詳細(xì)布局結(jié)果。

4 結(jié)束語(yǔ)

本文提出了基于密度控制的高效多倍高單元詳細(xì)布局方法,將基于嵌套式動(dòng)態(tài)規(guī)劃的高效算法用于優(yōu)化詳細(xì)布局中的線長(zhǎng)和密度2個(gè)目標(biāo),采用標(biāo)準(zhǔn)的測(cè)試?yán)蛹M(jìn)行測(cè)試。實(shí)驗(yàn)結(jié)果表明本文所提出的算法可以在合理的運(yùn)行時(shí)間里，得到很好的詳細(xì)布局結(jié)果。

[1] 徐寧，洪先龍.超大規(guī)模集成電路物理設(shè)計(jì)理論與算法[M].北京：清華大學(xué)出版社，2009:4-6.

[2] 南國(guó)芳.VLSI物理設(shè)計(jì)中關(guān)鍵問(wèn)題求解的算法研究[D].天津：天津大學(xué)，2004.

[3] Wu G,Chu C.Detailed placement algorithm for VLSI design with double-row height standard cells[J].IEEE Trans.on CAD of Integrated Circuits and Systems,2016,35 (9):1569-1573.

[4] Chow WK,Pui CW,Young EFY.Legalization algorithm for multiple-row height standard cell design[C]//Design Automation Conference,Las Vegas,Nevada:IEEE Design Automation,2016:1-6.

[5] Kim MC，Viswanathan N,Li Z,et al.ICCAD-2013 CAD contest in placement finishing and benchmark suite[C]//International Conference on Computer-aided Design,San Jose,CA:IEEE Computer Society,2013:268-270.

[6] Chow WK,Kuang J,He X,et al.Cell density-driven detailed placement with displacement constraint[C]//International Symposium on Physical Design,Petaluma,CA:ISPD,2014:3-10.

[7] Pan M,Viswanathan N,Chu C.An efficient and effective detailed placement algorithm[C]// International Conference on Computer-aided Design,San Jose,CA:IEEE Press,2005:48-55.

[8] Popovych S,Lai HH,Wang CM,et al.Density-aware detailed placement with instant legalization[C]//Design Automation Conference,Las Vegas,Nevada:IEEE Design Automation,2014,42(2):1-6.

[9] Lin T,Chu C,Shinnerl JR,et al.POLAR:placement based on novel rough legalization and refinement[C]//International Conference on Computer-aided Design,San Jose,CA:IEEE Computer Society,2013,21(1):357-362.

[10] Kernighan BW,Lin S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,1970,49(2):291-307.

[11] Fiduccia CM,Mattheyeyes RM.A linear-time heuristic for improving network partitions[C]//Design Automation Conference,Las Vegas,Nevada:IEEE Design Automation,1982,13(5):175-181.

[12] Brenner U,Vygen J.Faster optimal single-row placement with fixed ordering[C]//Design Automation & Test in Europe Conference,2000:117-121.

[13] Taghavi T,Alpert C,Huber A,et al.New placement prediction and mitigation techniques for local routing congestion[C]//International Conference on Computer-aided Design,San Jose,CA:IEEE Press Piscataway,2010:621-624.

[14] Kahng AB,Tucker P,Zelikovsky A.Optimization of linear placements for wirelength minimization with free sites[C]//Asia and South Pacific Design Automation Conference,San Jose,CA:IEEE Press,1999:241-244.

[15] 李康.VLSI物理設(shè)計(jì)中布局及有約束的布局優(yōu)化[D].成都：電子科技大學(xué),2010.

[16] 高文超，周強(qiáng)，錢旭,等.應(yīng)用于大規(guī)模集成電路非線性布局的二元結(jié)群算法[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2013，25(7)：1083-1088．

[17] Lin Y,Yu B,Zou Y,et al.Stitch aware detailed placement for multiple e-beam lithography[C]//Asia and South Pacific Design Automation Conference,San Jose,CA:IEEE Press,2016:186-191.

(責(zé)任編輯 吳鴻霞)

An Efficient Algorithm for Multiple-row Detailed Placement Based on Density Control

ChenXiuhua

(Department of Basic Courses，F(xiàn)ujian Chuanzheng Communications College，F(xiàn)uzhou Fujian 350007 )

This paper proposed an efficient algorithm for multiple-row detailed placement based on density control.Firstly,a new algorithm for multiple-row height standard cell density was given,then an efficient algorithm with a nesting dynamic programming was used to optimize the line length and density of the detailed placement,the test was done by the ISPD05 placement benchmark suite.Experimental results showed that the proposed algorithm can achieve the best result of detailed placement in the reasonable running time.

multiple-row height cell;detailed placement;density control;dynamic programming

2017-01-16

福建省教育廳科技項(xiàng)目(項(xiàng)目編號(hào)：JA10284;JB07283)；福建省交通科技發(fā)展項(xiàng)目(項(xiàng)目編號(hào)：201011)。

陳秀華，副教授，碩士，研究方向：圖論及其應(yīng)用、優(yōu)化理論與算法。

10.3969/j.issn.2095-4565.2017.02.010

O157.6

A

2095-4565(2017)02-0045-05