徐 敏，劉 陳

(南京郵電大學(xué) 電子科學(xué)與技術(shù)學(xué)院，江蘇 南京 210003)

SS序列(Single-Sequence)為一串互不重復(fù)的自然數(shù)序列，參考文獻(xiàn)[1]中SS解碼規(guī)則將SS序列解碼作為相對(duì)應(yīng)的單元分布圖，并利用模擬退火算法[2]以一定的概率隨機(jī)改變單元內(nèi)模塊擺放順序、旋轉(zhuǎn)度及SS序列，通過(guò)SS解碼規(guī)則得出各單元模塊的水平/垂直約束圖，利用關(guān)鍵路徑算法[3]求出最終芯片的面積。但目前為止SS所解決的只是局限于對(duì)矩形硬模塊的布圖問(wèn)題，而對(duì)于非矩形模塊或不規(guī)則形狀模塊的布圖尚未有很好的解決方法。隨著集成電路技術(shù)快速發(fā)展，模塊將不局限在以矩形形式出現(xiàn)，而是有可能以多種多樣的形狀更加靈活地出現(xiàn)在集成電路版圖上，但若仍以矩形的模式處理，必然會(huì)導(dǎo)致芯片面積的利用率不高，出現(xiàn)很多空間閑置的現(xiàn)象，因此尋找出一套簡(jiǎn)單易行的方法解決不規(guī)則模塊擺放的問(wèn)題意義重大。

1 模塊的劃分

對(duì)于不規(guī)則模塊的先期處理是將其劃分為許多小矩形，從而避免了傳統(tǒng)算法將整個(gè)不規(guī)則模塊算為1個(gè)大矩形而帶來(lái)的面積浪費(fèi)。如圖1所示，由2個(gè)矩形合并而成，傳統(tǒng)分割法將其視為1個(gè)矩形整體，再利用SS序列算法將其放入版圖，如圖1(a)所示，造成了底面積的浪費(fèi)。SS序列無(wú)法區(qū)分模塊空白區(qū)域，而是將其視為一整體放入版圖，導(dǎo)致下部空白區(qū)域永遠(yuǎn)無(wú)法被其他模塊空間占用，帶來(lái)了較大浪費(fèi)，隨著模塊面積增大和不規(guī)則模塊數(shù)量增多，面積浪費(fèi)現(xiàn)象將更為嚴(yán)重。因此在輸入模塊數(shù)據(jù)前就應(yīng)將模塊進(jìn)行劃分，為了程序計(jì)算方便，規(guī)定為對(duì)模塊自上而下、以左邊為基準(zhǔn)進(jìn)行劃分，如圖1(b)所示將該不規(guī)則模塊劃分為A、B兩個(gè)小矩形輸入數(shù)據(jù)，在SS算法處理過(guò)程中將其視為兩個(gè)連在一起不同的模塊，運(yùn)用區(qū)域模塊連接算法使其在變換的過(guò)程中始終保持緊密的連接在一起，如此則可充分利用下部空余的面積部分。對(duì)于有弧形的不規(guī)則模塊，應(yīng)以弧形最邊緣切線為起點(diǎn)畫(huà)一矩形將其包圍，如圖1(c)所示模塊。首先以整體模塊最左邊為基準(zhǔn)，即起始點(diǎn)，以上半部弧形右邊最頂點(diǎn)為終點(diǎn)，上弧形最頂點(diǎn)為上邊作一矩形，將該不規(guī)則模塊分為上下兩部分矩形。對(duì)于更為復(fù)雜的不規(guī)則模塊也是如此劃分。

圖1 不規(guī)則模塊劃分

2 模塊區(qū)域連接算法

在劃分模塊后，存在許多相互需要連接在一起的小模塊，這時(shí)必須要建立新的序列來(lái)反映這些模塊間的相互關(guān)系。如圖2所示，SS布圖算法[4]分別變換SS序列及模塊數(shù)據(jù)序列的排列順序，將模塊數(shù)據(jù)序列一一對(duì)應(yīng)放入SS序列所生成的單元圖中，使得版圖不斷發(fā)生變化。因此加入了模塊區(qū)域連接序列后，應(yīng)在變換模塊數(shù)據(jù)序列前先將連接在一起的模塊放入SS序列所生成的單元中。算法規(guī)則如下：

(1)將劃分過(guò)的小矩形根據(jù)輸入的順序編號(hào)，將同一不規(guī)則模塊的小矩形歸為一組，不同組間由0相隔，從而生成反映模塊間相互連接關(guān)系的模塊區(qū)域連接序列。

(2)變換SS序列后，由于模塊是自上而下的劃分，因此需要找出SS單元圖中呈上下連接關(guān)系的單元號(hào)先放入不規(guī)則模塊。首先隨機(jī)選取1個(gè)SS序列號(hào)A，找出其相鄰下方的單元且水平位置最接近A的單元號(hào)B，即滿足公式 Mbl(A)-1=Mas(B)并且 Min(|Mbs(A)-Mbs(B)|)的SS序列號(hào)。

(3)將模塊區(qū)域連接序列中對(duì)應(yīng)的模塊(劃分后的小矩形)放入規(guī)則(2)所找出的單元中。

(4)根據(jù)模塊區(qū)域連接序列，交換與規(guī)則(2)所得的單元號(hào)相對(duì)應(yīng)的模塊數(shù)據(jù)序列。

(5)生成版圖。

圖2 SS解碼算法對(duì)應(yīng)關(guān)系

3 不規(guī)則模塊的翻轉(zhuǎn)算法

在SS解碼算法中還需將模塊翻轉(zhuǎn)以獲得更好地?cái)[放位置。由于不規(guī)則模塊被劃分成許多小矩形，翻轉(zhuǎn)時(shí)不能簡(jiǎn)單改變矩形的長(zhǎng)寬順序，而應(yīng)結(jié)合模塊區(qū)域連接序列進(jìn)行整體翻轉(zhuǎn)。不同于簡(jiǎn)單矩形模塊只有0°和90°2種狀態(tài)，而不規(guī)則模塊要復(fù)雜得多，其中包括 0°、90°、180°和 270°4種翻轉(zhuǎn)狀態(tài)，如圖 3所示。

圖3 不規(guī)則模塊的翻轉(zhuǎn)

3.1 180°翻轉(zhuǎn)算法

180°翻轉(zhuǎn)情況相對(duì)較為簡(jiǎn)單，從圖 3中可看出180°翻轉(zhuǎn)僅僅是在原始狀態(tài)的基礎(chǔ)上改變了劃分的小矩形的上下位置關(guān)系，并沒(méi)有改變這些小矩形的長(zhǎng)寬數(shù)據(jù)，因此只需改變模塊區(qū)域連接序列中對(duì)應(yīng)組的順序。設(shè)有模塊區(qū)域連接序列：XXXX0ABCD0XXX0XXX0XXX，要使矩形組ABCD組成的模塊進(jìn)行180°翻轉(zhuǎn)，只需將序列改變?yōu)閄XXX0DCBA0XXX0XXX0XXX即可，如圖4所示。

圖4 模塊 180°翻轉(zhuǎn)

3.2 90°翻轉(zhuǎn)算法

90°翻轉(zhuǎn)的情況較為復(fù)雜，不僅涉及到模塊區(qū)域連接序列，而且由于其改變了小矩形的長(zhǎng)寬數(shù)據(jù)，同時(shí)要改變模塊數(shù)據(jù)序列。首先要對(duì)模塊重新進(jìn)行劃分：

(1)在原有模塊數(shù)據(jù)序列中找出長(zhǎng)度最小的模塊，將其寬加上改組中所有模塊寬度，作為一個(gè)新的小矩形。

(2)找出原有模塊數(shù)據(jù)序列中長(zhǎng)度第2小的模塊，將其長(zhǎng)減去(1)中矩形的長(zhǎng)作為其新的長(zhǎng)度，其寬改為原來(lái)寬度加上改組中所有模塊寬度再減去(1)中長(zhǎng)度最小的模塊的寬度。

(3)重復(fù)以上步驟直至所有矩形被處理。

(4)將修改過(guò)的模塊數(shù)據(jù)序列中長(zhǎng)寬數(shù)據(jù)對(duì)換。

(5)修改模塊區(qū)域連接序列使其與現(xiàn)在的模塊數(shù)據(jù)序列相對(duì)應(yīng)。

模塊90°翻轉(zhuǎn)如圖5所示。

圖5 模塊 90°翻轉(zhuǎn)

3.3 270°翻轉(zhuǎn)算法

270°相當(dāng)于在 90°翻轉(zhuǎn)的基礎(chǔ)上再次 180°翻轉(zhuǎn)，因此只需在3.2節(jié)的基礎(chǔ)運(yùn)用3.1節(jié)的算法進(jìn)行翻轉(zhuǎn)即可。

本文在SS序列算法的基礎(chǔ)上進(jìn)行了改進(jìn)，使原有算法在只能進(jìn)行簡(jiǎn)單矩形模塊布圖的基礎(chǔ)上，可以對(duì)一些復(fù)雜的不規(guī)則模塊進(jìn)行布圖，大大增加了SS算法的實(shí)用能力和處理復(fù)雜模塊的能力，為將來(lái)集成電路布圖的靈活多變打下了基礎(chǔ)。本文提出了新的模塊劃分概念，并提出了模塊區(qū)域連接算法、不規(guī)則模塊翻轉(zhuǎn)算法、模塊區(qū)域連接序列等新的算法和概念。充實(shí)了SS序列算法，增加了SS序列算法的功能，大大改進(jìn)了SS算法的實(shí)用性和處理復(fù)雜情況的應(yīng)變能力。

[1]KAJITANI Y.The Single-Sequence that unifies placement and floorplanning[M].Presented at the Presession Meeting of ASP-DAC.Asian Semi-conductor University Cooperations，2003.

[2]KIRKPATRICK S.Optimization by simulated annealing[J].Science， 1984，34(5):975-986.

[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1992.

[4]ZHANG X，KAJITANI Y.Theory of T-junction floorplan in terms of single-sequence[J].IEEE Int.Symp.on Circuits and Systems， 2004：341-344.