基于Single—Sequence表示法的BUS總線約束布局優(yōu)化

摘要：基于Single-Sequence表示法和模擬退火算法框架，通過檢驗(yàn)single-sequence編碼的直接升序和直接降序判斷BUS總線布局中水平和垂直約束的可行性。在MCNC benchmark上的實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性.。

關(guān)鍵詞：Single-Sequence表示法；BUS布局約束；直接升序；直接降序

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）33-0225-02

隨著微電子技術(shù)不斷發(fā)展，越來越多的元器件被集成到一塊芯片上，同時(shí)需要多層金屬實(shí)現(xiàn)器件間的連接（通常包括幾條BUS總線）以完成既定功能。隨著電路復(fù)雜度和集成度急劇增加，BUS布線成為一項(xiàng)艱巨任務(wù)，尤其是在網(wǎng)絡(luò)和數(shù)據(jù)處理芯片上。為使BUS總線連接更加方便高效，應(yīng)在布圖規(guī)劃的早期階段就考慮BUS總線的布局及其優(yōu)化。文中應(yīng)用Single Sequence（以下簡(jiǎn)稱SS）表示法來討論BUS總線布局問題。

1 Single-Sequence表示法

Single-Sequence表示法用1～n的自然數(shù)排列表示平面上n個(gè)模塊的布圖規(guī)劃（布局）的拓?fù)浣Y(jié)構(gòu)。每個(gè)SS編碼所包含的ABLR關(guān)系（上、下、左、右）由每個(gè)表示模塊或區(qū)域的自然數(shù)在SS中的相對(duì)大小和位置確定[1-6]：

SS中的ABLR關(guān)系：假設(shè)在SS編碼中兩個(gè)自然數(shù)x和y保持這種位置關(guān)系。當(dāng)且僅當(dāng)xy時(shí)，x所代表的模塊或區(qū)域在y所代表的模塊（或區(qū)域）的下邊。

SS編碼是平面上n個(gè)物體之間ABLR位置關(guān)系的產(chǎn)生器。考慮平面上n個(gè)物體，一個(gè)SS編碼定義了平面上n個(gè)物體之間n（n-1）/2個(gè)ABLR關(guān)系[1-3]。SS編碼的標(biāo)識(shí)和獲得過程如圖1所示，圖中SS編碼為41352。

2 BUS總線約束布圖規(guī)劃（布局）

2.1 BUS約束布圖規(guī)劃問題定義

假設(shè)布線區(qū)域?yàn)槎鄬咏饘賹?，BUS總線以水平或垂直方向分布在兩層。單條BUS總線可表示為ui={b1，…，bk}，k=︱ui︱，。每個(gè)模塊bi的左下角坐標(biāo)為（xi，yi），其寬度和高度分別為wi和hi。BUS線驅(qū)動(dòng)布圖規(guī)劃（布局）可如下定義[7-10]：

給定n個(gè)長(zhǎng)方形模塊集B={bi︱i=1…，n}和m條BUS總線集U={ui︱i=1…，m}，每條BUS線寬度為ti并穿過模塊集Bi（Bi[?]B，︱Bi︱=ki）。確定每個(gè)模塊和BUS線在布局平面上的位置，使得任意兩個(gè)模塊及BUS總線（水平或垂直）不重疊，每條BUS線ui穿越所包含的所有模塊ki。同時(shí)，包圍所有模塊的外框矩形（芯片面積）和BUS線占用面積最小化（如圖2所示）。

命題1 水平BUS線布局約束條件

水平BUS總線uk={b1，…，bk}滿足布局條件當(dāng)且僅當(dāng)ymax-ymin[≥]tk， ymax=min{yi+hi︱i=1…，k}， ymin=max{yi︱i=1…，k}。

命題2 垂直BUS線布局約束條件

垂直BUS總線uk={b1，…，bk}滿足布局條件當(dāng)且僅當(dāng)xmax-xmin[≥]tk， xmax=min{xi+wi︱i=1…，k}， ymin=max{xi︱i=1…，k}。

圖3（a）中，兩條BUS線u（A，G）和v（D，E，F(xiàn)）分別穿過各自給定的連線模塊。但在圖3（b）中，BUS線u（A，G）未完全連接模塊A（不滿足命題1中條件）；v（D，E，F(xiàn)）不能實(shí)現(xiàn)相應(yīng)模塊連接。

2.2 BUS約束布圖規(guī)劃（布局）文獻(xiàn)概述

文獻(xiàn)中，一些學(xué)者討論過布圖規(guī)劃（布局）中的模塊間位置約束問題，但這些方法多基于單個(gè)模塊的位置調(diào)整。Xiang等在文獻(xiàn)[7]中討論過模塊間上、下、左、右的相鄰放置，但使用sequence-pair表示法，編碼變形復(fù)雜，計(jì)算復(fù)雜度較高。Tang等在文獻(xiàn)[8]中給出了一種模塊位置對(duì)齊且相鄰的方法，但在BUS總線約束中并不強(qiáng)制要求模塊間相鄰。Rafiq等在文獻(xiàn)[10]中給出了一種基于BUS總線的布圖規(guī)劃方法，但給出的BUS總線只包括兩個(gè)模塊極其繁雜連線。

3 基于SS編碼的BUS約束布圖規(guī)劃

定義1 直接升序 給定包含n個(gè)模塊的任一SS編碼{ s1s2…si..sj…sn︱si∈N}，從任意位置上的數(shù)字si出發(fā)（記為p1），向右（向后）掃描，大于p1且離其最近的數(shù)字記為p2，重復(fù)此過程直到編碼右端，得到的序列稱為該數(shù)字（位置）的直接升序，記為{p1p2…pk︱pk∈SS，pi

定義2 直接降序 給定包含n個(gè)模塊的任一SS編碼{ s1s2…si..sj…sn︱si∈N}，從任意位置上的數(shù)字si出發(fā)（記為q1），向右（向后）掃描，小于q1且離其最近的數(shù)字記為q2，重復(fù)此過程直到編碼右端，得到的序列稱為該數(shù)字（位置）的直接降序，記為{q1q2…qk︱qk∈SS，qi>qi+1}。SS編碼中模數(shù)最大直接降序稱為該編碼的最大降序。

例：圖1（b）的編碼為41352，其最大升序?yàn)?35，最大降序?yàn)?32。

命題3 當(dāng)SS編碼的任一直接升序的模大于某一水平BUS總線約束的模，將水平BUS總線約束包含的模塊放置到該直接升序代表的模塊位置處，可得到一個(gè)可行解。

證明：因?yàn)镾S編碼表示數(shù)字代表的矩形區(qū)域上下左右的位置關(guān)系，任一直接升序中數(shù)字代表的位置左右直接相鄰；如果不直接相鄰，可通過滑動(dòng)模塊（區(qū)域）右上角的T型連接的邊使其直接相連[1，3]。

命題4 當(dāng)SS編碼的任一直接降序的模大于某一垂直BUS總線約束的模，將垂直BUS總線約束包含的模塊放置到該直接降序代表的模塊位置處，可得到一個(gè)可行解。

證明：同命題3。

4 算法描述

算法總體框架為退火。需要注意的是，一個(gè)SS編碼僅給出了數(shù)字代表的區(qū)域（模塊）的位置關(guān)系，還需將模塊分配到區(qū)域里，壓縮后得到最終的布局。

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

參考文獻(xiàn)：

[1] Kajitani Y. The single-sequence that unifies placement and floorplanning [C]. Presession meeting of ASP-DAC，Asian Semi-conductor University Cooperations， Jan.2003， PP： 368-371.

[2] 李康， 虞厥邦，于永斌. Single-Sequence的邊界約束條件[J]. 電子科技大學(xué)學(xué)報(bào)， 2008，37（1）： 70-73.

[3] K Li， J Yu， J Li. VLSI Floorplanning with Boundary Constraints Based on Single-Sequence Representation[J]. Ieice Trans on Fundamentals， 2009， 92（9）： 2369-2375.

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

[5] 李坤龍.布圖規(guī)劃約束對(duì)VLSI設(shè)計(jì)性能的影響[D].青島：青島理工大學(xué)，2016.

[6] 徐敏.基于Single-Sequence的布圖規(guī)劃改進(jìn)算法及實(shí)現(xiàn)[D].南京：南京郵電大學(xué)，2010.

[7] H. Xiang， X. Tang， D. Wong， Bus-driven floorplanning. Proceedings of IEEE International Conference on Computer-Aided Design， 2003：66-73.

[8] E.F. Young， C.C. Chu， M.L. Ho， A unified method to handle different kinds of placement constraints in floorplan design. Proceedings of the Seventh Asia and South Pacific Design Automation Conference and 15th International Conference on VLSI Design， 2002： 661–667.

[9] X. Tang， D. F. Wong. Floorplanning with alignment and performance constraints[J]. ACM DAC， 2002， pp：848-853.

[10] Rafiq. F， C. Jeske， M Yang. BUS based integrated floorplanning. IEEE International Symposium on Circuits & Systems， 2002，l2（2）： 875-878.

[11] 李煜，張徐亮，虞厥邦. 基于O-TREE樹表示的總線約束在VLSI/PCB布局中的應(yīng)用[J].成都信息工程學(xué)院學(xué)報(bào)，2005，（20）：291-296.

[12] Xiaoping Tang， D. F. Wong. Floorplanning with alignment and performance constraints[J]. ACM DAC， 2002：848-853.

[13] H. Murata， K. Fujiyoshi， S. Nakatake， Y. Kajitani. VLSI module placement based on rectangle packing by the sequence pair[J]. IEEE Trans on CAD， 1996， 15（12）：1518-1524.

【通聯(lián)編輯：張薇】