邊緣剪線技術(shù)應(yīng)用於單元布局壓縮

1、1邊緣剪線技術(shù)應(yīng)用於單元佈局壓縮Edged Shear Line Techniques Applied toCell Compaction吳占鰲蔡加春*李文達(dá)Jan-Ou WuChia-Chun Tsai*Wen-Ta Lee國立臺(tái)北科技大學(xué)電腦通訊與控制研究所摘要本篇論文中，我們在個(gè)人電腦利用邊緣剪線具折線插入技術(shù)完成一維佈局壓縮器，此壓縮器能在離線方式利用CIF的檔案銜接現(xiàn)有商業(yè)的佈局工具，例如Tanner Pro之L-Edit 與Cadence 之Virtuaso。同時(shí)，我們採用新的邊緣鏈結(jié)相鄰矩陣的資料結(jié)構(gòu)完成我們的壓縮演算法，此演算法既簡單又有效，其時(shí)間複雜度為O(N logN)，其

2、中N為佈局中的矩形方塊物件的數(shù)目。經(jīng)由實(shí)驗(yàn)結(jié)果其節(jié)省佈局面積平均達(dá)43.8%，同時(shí)把壓縮後的結(jié)果回存CIF 檔，經(jīng)由商業(yè)的佈局工具再作設(shè)計(jì)規(guī)範(fàn)檢核，證實(shí)完全正確。關(guān)鍵詞：一維佈局壓縮器、邊緣鏈結(jié)相鄰矩陣、剪線。投稿受理時(shí)間：90年10月26日審查通過時(shí)間：91年2月1日ABSTRACTIn this paper, we implemented a one-dimensional layout compactor based on edged shear line techniques with jogs insertion on a personal computer. The compact

3、or can be connected off line from current commercial layout tools, such as Tanner Pros L-Edit and Cadences Virtuaso, with the CIF file format. A new data structure of edge-link adjacent matrix is used for easily implementation to our compaction algorithm. The algorithm is very simple but efficient a

4、nd its time complexity is O(N logN), where N is the number of geometric blocks in a cell layout. Experimentally, some examples are shown that the area saving is up to 43.8% in average. All the layout results restored to commercial tools are also verified.Keywords: One-dimensional compactor, Edge-lin

5、k adjacent matrix, Shear line.2壹、簡介在超大型積體電路實(shí)體設(shè)計(jì)中，壓縮工具可用來改善積體電路的佈局面積，一般經(jīng)由編輯器得到的佈局設(shè)計(jì)圖雖然符合佈局設(shè)計(jì)的規(guī)則，但由於擺置設(shè)計(jì)及繞線設(shè)計(jì)的未最佳化結(jié)果，使得佈局設(shè)計(jì)圖完成後都會(huì)有一些不必要的空間產(chǎn)生，為了增加生產(chǎn)積體電路的產(chǎn)量及減少浪費(fèi)成本，因此，如何得到一個(gè)既不違反設(shè)計(jì)規(guī)則，而且又有效率的能把佈線面積壓縮到最小空間的壓縮器是非常需要的。單元壓縮(Cell compaction)1-5是指在邏輯電路設(shè)計(jì)功能佈局完成後的空間壓縮，一般在佈局電路都是使用特定的顏色符號(hào)來表示電路連接方式，如多晶矽（Poly）、接觸點(diǎn)（Co

6、ntact）、穿孔點(diǎn)（Via）和金屬線（Metal）等，在單元佈局時(shí)，往往都存在一些多餘的空間，經(jīng)由人工來行使此空間的壓縮是非常的繁雜且費(fèi)時(shí)。因此，我們需要一個(gè)有效率的壓縮器來行使此壓縮的工作。此篇論文中，我們經(jīng)由個(gè)人電腦設(shè)計(jì)並完成一維的壓縮器，此壓縮器能與現(xiàn)在的商業(yè)佈局工具在離線的情況下直接銜接，例如Tanner Pro之L-Edit 或Cadence之 Virtuaso。而壓縮器的輸入來自於佈局轉(zhuǎn)成的CIF檔案，然後行使一維壓縮的動(dòng)作，最後再回存成新的CIF檔案，而達(dá)成與現(xiàn)有商業(yè)佈局工具的銜接。為了方便核對壓縮前後的結(jié)果，我們設(shè)計(jì)了多重的視窗介面在我們的壓縮工具系統(tǒng)內(nèi)。圖一所示為整個(gè)系統(tǒng)的

7、流程，首先系統(tǒng)讀入Tanner佈局後轉(zhuǎn)換出來的CIF檔案，同時(shí)把此檔案轉(zhuǎn)成中間檔存在資料庫內(nèi)，以顯示原未壓縮的初始佈局。接著將整個(gè)佈局圖轉(zhuǎn)換成一種邊緣鏈結(jié)相鄰矩陣表示的資料結(jié)構(gòu)6-8，然後由左向右以具有折線式邊緣剪線功能的平面掃描壓縮演算法，配合可移動(dòng)最小距離的計(jì)算與二維陣列電子設(shè)計(jì)規(guī)範(fàn)準(zhǔn)則，計(jì)算出真正可向左壓縮的位移，然後依掃描的位置到邊緣相鄰矩陣表示的資料結(jié)構(gòu)內(nèi)更改相關(guān)的座標(biāo)資料，並顯示壓縮後的佈局圖樣，經(jīng)確定無誤後，再把壓縮後的資料回寫成CIF檔案格式，以銜接原佈局編輯設(shè)計(jì)系統(tǒng)。此壓縮演算法簡易而有效的，其時(shí)間複雜度為O（N logN），N為一個(gè)單元佈局內(nèi)的幾何方塊數(shù)。我們使用Tanne

8、r Pro之L-Edit實(shí)際製作了一些全客戶實(shí)體佈局單元資料作為測試?yán)?，?jīng)本系統(tǒng)作一維壓縮後，其執(zhí)行效率平均縮減佈局面積達(dá)43.8%。同時(shí)，我們也把壓縮後的佈局結(jié)果回存為CIF 檔案格式供Tanner Pro之L-Edit 讀取，此壓縮後佈局圖樣完全符合DRC，甚至再經(jīng)由LVS及Dracula等雙重驗(yàn)證，亦正確無誤。此實(shí)驗(yàn)結(jié)果，可知我們的一維壓縮器是直接而有效率的工具，同時(shí)也證實(shí)此一維壓縮工具可完全銜接現(xiàn)有的商業(yè)佈局工具。圖一一維壓縮器系統(tǒng)流程圖本論文其它章節(jié)安排如下，第二節(jié)介紹新的邊緣鏈結(jié)相鄰矩陣之資料結(jié)構(gòu)，第三節(jié)敘述一維邊緣剪線壓縮演算法，第四節(jié)顯示單元壓縮製作系統(tǒng)及壓縮實(shí)驗(yàn)結(jié)果，最後作

9、出結(jié)論。貳、資料結(jié)構(gòu)我們的壓縮系統(tǒng)與現(xiàn)有商業(yè)工具之銜接是以CIF檔案為媒介，輸入來自於佈局圖轉(zhuǎn)換為CIF資料格式，我們需要此佈局的資料以便壓縮時(shí)使用。在此我們定義邊緣鏈結(jié)相鄰矩陣之資料結(jié)構(gòu)以便存單元佈局每個(gè)幾何物件的邊，圖二所示為每一個(gè)節(jié)點(diǎn)定義的結(jié)構(gòu)，圖中l(wèi)ayer是代表物件佈局層為多晶矽、接觸點(diǎn)、穿孔點(diǎn)或金屬線等，edge是指左或右邊的標(biāo)幟，代表此節(jié)點(diǎn)被掃到的是左邊或右邊，(lx,ly)和(rx,ry)分別代表物件的左上角和右下角的座標(biāo)，而up、down和next分別表示指到相鄰矩陣的上、下和下一個(gè)的節(jié)點(diǎn)。Struct Nodechar layer4; / the layer of an o

10、bject/ char edge1; / the left or right edge of an object /int lx, ly, rx, ry; / left-up and right-bottom coordinates of an object / Node *up, *down, *next; / link to up, down, and next objects /;圖二相鄰矩陣之節(jié)點(diǎn)結(jié)構(gòu)3圖三所示為邊緣鏈結(jié)相鄰矩陣佈局物件圖和資料結(jié)構(gòu)的關(guān)係，圖三(a)中之物件1、2、3、4分別表示四個(gè)物件，而X1到X8分別表示佈局物件的X座標(biāo)，圖三(b)所示其相對應(yīng)的邊緣鏈結(jié)相鄰矩陣資料

11、結(jié)構(gòu)，圖中的第0列是以各物件的左和右邊當(dāng)節(jié)點(diǎn)，同時(shí)配合一維由左往右的X平面掃描，再依X軸座標(biāo)的大小所建立出來的，例如1L(X1)、2L(X2)、.4L(X7)和4R(X8)，1L表物件1的左邊緣，其餘同樣表示法。平面掃描方法首先從第0列的第0行1L開始向右掃，初始掃到2L，接著掃到1R，一直掃到本身佈局物件的右邊或比最初第0行的邊界還大或相等時(shí)，此列掃描即停止，如1R的邊是物件1的右邊，此時(shí)便停止掃描。所以第0列向右掃描鏈結(jié)串列是物件1L物件2L物件1R。另外一個(gè)例子，圖四(b)是圖四(a)佈局圖所建立出來的資料結(jié)構(gòu)圖。(a)(b)圖三邊緣鏈結(jié)相鄰矩陣之資料結(jié)構(gòu)例子(一)4資料結(jié)構(gòu)表示法確定後

12、，接著如何來建立此資料結(jié)構(gòu)，以便能把佈局圖轉(zhuǎn)成相對應(yīng)的資料表示方式，以 x軸平面掃瞄為例，其建立過程之演算步驟敘述如下：(a)(b) 圖四邊緣鏈結(jié)相鄰矩陣之資料結(jié)構(gòu)例子(二)一、 首先讀入佈局圖的檔案，轉(zhuǎn)成暫時(shí)的中間檔。把CIF的檔轉(zhuǎn)換成佈局圖所有物件為左上角與右下角的記錄資料，如圖五(b)就是把圖五(a)轉(zhuǎn)換完成的資料檔，其中CTH、CCP 、CM和CCC分別代表氧化層、多晶矽層、金屬層和穿孔點(diǎn)等，而lx、ly表示物件的左上角座標(biāo)，rx、ry表示物件的右下角座標(biāo)。(a) lx ly rx ryCTH 96 40 146 49CTH 96 166 146 176CCP 117 34 126 1

13、81CM 137 108 217 117CM 96 166 108 200CM 136 40 146 176CM 10 107 126 116CM 96 18 106 49CM 10 17 213 27CM 10 191 213 201CCC 13 194 17 198CCC 13 20 17 25CCC 119 110 123 114(b) 圖五佈局圖轉(zhuǎn)換為CIF資料檔二、依佈局圖所有物件的左上角X座標(biāo)和右下角X座標(biāo)分別排序，並建立出第0列的節(jié)點(diǎn)出來。例如圖五(b)佈局圖所有物件的第0列邊節(jié)點(diǎn)結(jié)果為10 10 10 13 13 17 17 96 96 96 96 96 106 108 117

14、 119 123 126 136 137 146 146 213 213 217。三、以第0列的節(jié)點(diǎn)邊當(dāng)起點(diǎn)，由左往右掃描建出每一列的資料結(jié)構(gòu)。四、假如此時(shí)的邊是物件的左邊，則經(jīng)由邊緣鏈結(jié)相鄰矩陣會(huì)找到另一重疊物件的左邊，其重疊的情形如圖六(a)和(b)所示。五、假如此時(shí)的邊是物件的右邊，則經(jīng)由邊緣鏈結(jié)相鄰矩陣會(huì)找到物件的左邊或此時(shí)是物件最右邊的邊，則可能找不到邊，其不重疊的情形如圖七(a)和(b)所示。六、依此方法，最後便可建出如圖三(b)和圖四(b)的邊緣鏈結(jié)相鄰矩陣的資料結(jié)構(gòu)。 (a) (b)圖六兩物件重疊的狀況5(a)(b)圖七兩物件不重疊的狀況上述之邊緣鏈結(jié)相鄰矩陣資料結(jié)構(gòu)之建置是基

15、於排序與掃描方法，總共所花費(fèi)的時(shí)間為O(N logN)，N為佈局單元物件的數(shù)目。參、邊緣剪線的壓縮演算法我們以邊緣鏈結(jié)相鄰矩陣的資料結(jié)構(gòu)為基礎(chǔ)，配合以X軸方向邊緣剪線方法來壓縮單元佈局圖，圖八所示為我們的一維壓縮演算法的流程圖。此演算法首先建立多重文件視窗處理界面系統(tǒng)，接著讀入Tanner Pro佈局後轉(zhuǎn)換出來的CIF檔案，再把整個(gè)佈局圖轉(zhuǎn)換成一種邊緣鏈結(jié)相鄰矩陣表示的資料結(jié)構(gòu)，然後使用具折線式邊緣剪線功能的平面掃描方法，由左向右掃描，並配合可移動(dòng)最小距離的計(jì)算，計(jì)算出可向左移動(dòng)多少空間，再配合二維陣列DRC的法則，算出真正向左可壓縮的位移，然後依掃描的位置到邊緣相鄰矩陣表示的資料結(jié)構(gòu)內(nèi)更改相

16、關(guān)的資料，即完成壓縮工作。為了可使Tanner回讀以便核對DRC的功能，我們把完成壓縮佈局圖之資料結(jié)構(gòu)內(nèi)的資料回存成CIF的檔案格式。圖八一維壓縮演算法之流程圖6圖九所示為NOR閘佈局圖的平面掃瞄例子，圖中的S1、S2、S3、S4、S5和S6即為依序由左往右掃描的軌跡，其中S4是具有插入折線線段的掃瞄軌跡。在平面的折線段掃描中，其佈局圖的Y軸方向是否能插入轉(zhuǎn)彎線段，依佈局圖的分佈狀況，我們列出如圖十有關(guān)折線段上段一端轉(zhuǎn)彎的規(guī)則，圖中之轉(zhuǎn)彎線段向左方移位其新的Y軸yb1座標(biāo)為：yb1= yb+ S(D,P) + WP (1)其中S(D,P)表示diffusion和poly兩物件之佈局規(guī)則的最小間

17、距，Wp表示poly線的最小寬度。圖九NOR閘佈局圖的平面掃瞄軌跡圖十往左方上折線段距離的判斷圖十中X軸方向新的Xb1坐標(biāo)為當(dāng)時(shí)平面掃描的X軸座標(biāo)減上物件的寬度值；所以是否可插入折線，其判斷的條件即Hy要符合式下列式：Hy > S(D,P) + Wp (2)同理，如圖十一所示另一端轉(zhuǎn)彎情況，此折線段向右方移位，其新的yb1為yb1 = yb - S( D,P) + WP (3)而圖十一中新的Xb1坐標(biāo)為當(dāng)時(shí)平面掃描的X軸座標(biāo)值減上物件的寬度值，所以是否可插入折線，其判斷的條件即Hy要符合下列式：Hy > S(D,P)+ WP (4)圖十一往右方下折線段距離的判斷圖十二所示的情況，即

18、線段一端先向左邊轉(zhuǎn)彎，接著又向右轉(zhuǎn)彎，此時(shí)中間的距離Hy需符合下式：7Hy > 2*S(D,P)+ Wp (5)如果中間是兩條線段要產(chǎn)生轉(zhuǎn)彎時(shí)，如圖十三所示，其Hy的限制大小為Hy > 2*S(A,B)+ WB+S(B,C)+ Wc (6)(6)式中，如假設(shè)這些物件的相隔佈局規(guī)則都一樣，則可簡化為Hy > 2*2S(A,B)+ WB (7)圖十二線段上下兩端產(chǎn)生折線圖十三中，如果有N條的條線段要產(chǎn)生轉(zhuǎn)彎時(shí)，則(7)式之Hy的限制大小為Hy > 2 N *S(A,B)+ Wp (8)圖十三兩條線段產(chǎn)生轉(zhuǎn)彎8依據(jù)前面所詳細(xì)敘述的折線加入之邊緣剪線掃瞄壓縮方法，我們綜合整理出

19、一維壓縮演算法，如圖十四所示。Algorithm Comapction-Sweep(Xmin, Xmax) /Xmin and Xmax are the X coordinates of the left-mostand right-most edges in a layout, respectively / /Let adjacency be the edge-link adjacent matrix and scanxsi be the pointer of current sweep /scanxsi = adjacency0；/Starting sweep from the 0th c

20、olumn in adjacent matrix / while (scanxsi.rxXmax) *si = get_si(scanxsi.rx)；/Find all the objects that have the same X coordinates from scanxsi /scanxsj = get_next( *si)；/Find all the edges viewed from *si / sv = get_min(scanxsi,scanxsj)；/Get minimum space between objects si and sj / if(scanxsj.layer

21、“CTH”) /Is Thinoxide layer? / get_drc()；/Get correspond width or space from selected technology process /displacement_compute()；/Compute the movable displacement, movx /coordinate_refresh()；/ Update the coordinates with the local displacement from adjacent matrix/ elsejog_compaction()；/With jogs ins

22、ertion /scanxsi adjacency0down； /end of while/writeback_CIFfile()；/Restored into the CIF file /end of Comapction-Sweep/Procedure jog_compaction(adjacency) pointcthcthi=search_CTH()；/Find all the CTH transistors / intvtojogsi=search_crosscth()；/ Find the CTH from vertical directions / inthtojogsh=sea

23、rch_crosscth()；/Find the CTH from horizontal directions / upblock=calluph(inth)；/Compute offset from CTHs to up-middle objects/loblockcallloh(inth)；/Compute offset from CTHs to bottom-middle objects/for(jog=1;jog<cthi-1;jog=jog+2) do /Do (cthi-1)/2 pairs/ if(si-1!=0&&(upblock>=4*(si-1)

24、+4*(si)&&loblock>=4*(si-1)+4*(si)/With consideration of 0.5um technologies/ move_jog()；/ estimate movable displacement / find_hor_contact()；/Update x coordinates / refresh_vertical()；/Update y coordinates / else without_jog()；/Without jogs insertion / 圖十四一維壓縮演算法此演算法包括兩個(gè)部份，Compaction-Sweep

25、 (Xmin,Xmax)是專門負(fù)責(zé)沒有折線的壓縮方法，物件的一邊向右邊找另一物件最靠近的邊，同時(shí)判斷是否為電晶體氧化層CTH，如果不是，則由displacement_ compute()計(jì)算出可位移的大小，再配合get_drc()得佈局規(guī)則的位移大小，此可算出真正可壓縮的大小，然後最後經(jīng)由coordinate_refresh()更新邊緣鏈結(jié)相鄰矩陣資料結(jié)構(gòu)內(nèi)的資料。如果是，為了不改變電晶體的L和W，而跳至jog_compaction (adjacency)去做折線的壓縮動(dòng)作，而產(chǎn)生折線情形是當(dāng)一垂直方向的物件一端固定另一端產(chǎn)生向右壓縮，如圖十與十一所示；或物件的上下兩端固定，而中間產(chǎn)生壓縮，如

26、圖十二所示；以及有更多的物件產(chǎn)生中間壓縮，如圖十三所示。此掃描的壓縮演算法可使用在任何區(qū)域的搜尋，直接找到所要移動(dòng)的掃描軌跡，其最差情況之總掃描次數(shù)為2*N，橫向掃描最多為2個(gè)節(jié)點(diǎn)，所以最差情況還是2*2*N，亦即掃描壓縮方法的時(shí)間複雜度O(N)。綜合第二節(jié)所述之邊緣鏈結(jié)相鄰矩陣資料結(jié)構(gòu)之建置時(shí)間為O(N logN)，故我們的邊緣剪線技術(shù)之壓縮演算法其時(shí)間複雜度為O(N logN)。肆、壓縮實(shí)驗(yàn)結(jié)果9我們的壓縮系統(tǒng)之硬體設(shè)備採用華碩筆記型電腦L8400系列，中央處理單元是IntelPentium-IIII 400 MHz，內(nèi)建192MB的記憶體，程式以Borland C+ Builder 4.

27、0編寫而成，並以UMC 0.5um 2P2M製程的設(shè)計(jì)規(guī)則為例。我們針對每一種單元佈局未壓縮的初始佈局和未具折線式壓縮後的佈局做一個(gè)比較，同時(shí)顯示壓縮的減縮比， 如表一所示，很明顯壓縮前和壓縮後減縮比平均節(jié)省面積達(dá)40.8%，同時(shí)我們並做了有折線和沒折線的比較，我們發(fā)現(xiàn)有折線的壓縮比平均節(jié)省面積達(dá)43.8%，比沒折線的壓縮在面積上平均又節(jié)省了3%。接著以佈局的矩形個(gè)數(shù)來探討其執(zhí)行時(shí)間的關(guān)係，以圖十五所示，我們可發(fā)現(xiàn)當(dāng)佈局矩形個(gè)數(shù)在100以下時(shí)，其執(zhí)行時(shí)間幾乎接近線性；當(dāng)佈局矩形個(gè)數(shù)大於100時(shí)，執(zhí)行時(shí)間接近對數(shù)型。同時(shí)我們把此結(jié)果和Nandy6的壓縮器比較，Nandy壓縮器佈局矩形個(gè)數(shù)和執(zhí)行時(shí)

28、間如圖十六，我們發(fā)現(xiàn)因?yàn)镹andy的壓縮器其資料結(jié)構(gòu)是用四元樹建出來的，所以同樣在100個(gè)矩形的線性關(guān)係，本系統(tǒng)執(zhí)行時(shí)間快了十倍之多。表一 各種單元具折線與非具折線之壓縮結(jié)果ExampleInitial layout(mm2)Without jogsWith jogsArea(mm2)Area_savingArea(mm2)Area_savingRun_timeNOT31*3013*2762%12*2765%8msNOR31*3017*2750%16*2753%10msNAND32*3217*2951%14*2960%13msParity49*3337*3031%36*3033%16msRS-

29、FF119*4176*3840%75*3841%39msJK-FF113*4485*4031%82*4034%40msD-FF126*4092*3732%91*3733%42msCounter445*48345*4330%338*4331%184ms圖十五本系統(tǒng)時(shí)間對幾何物件的關(guān)係圖十六 Nandy6時(shí)間對幾何物件的關(guān)係10圖十七(a)與(b)分別顯示四位元計(jì)數(shù)器初始和壓縮後的佈局，而圖十七(c)是執(zhí)行後的詳細(xì)統(tǒng)計(jì)表，其中壓縮面積節(jié)省了31%。(a)初始的佈局(b)壓縮後的佈局(c)壓縮後的統(tǒng)計(jì)資料圖十七四位元計(jì)數(shù)器的壓縮結(jié)果伍、結(jié)論我們製作一個(gè)一維單元佈局具折線式壓縮器，能配合讀取現(xiàn)有商業(yè)佈

30、局軟體Tanner Pro L-Edit之CIF 檔案之讀取與回存及UMC 0.5m 2P2M之製程規(guī)則，並實(shí)際完成多個(gè)單元佈局壓縮，壓縮後佈局資料完全正確而符合DRC，同時(shí)亦經(jīng)LVS及Dracula雙重驗(yàn)證，亦完全無誤。我們的壓縮演算法引用剪線觀念的基礎(chǔ)，並採用改良式的邊緣鏈結(jié)相鄰矩陣資料結(jié)構(gòu)，經(jīng)由實(shí)驗(yàn)證明此方法是既簡單又有效率的。參考文獻(xiàn)1 J.F. Lee, “A New Framework of Design Rules for compaction of VLSI Layout,” IEEE Trans. On Computer-Aided Design, Vol 7, No. 11, pp. 1159-1204, 1988.2 S.L. Lin and Allen, “Minplex- a compactor that minimizes the bounding rectangle and individual rectangles in a layout,” Proc. 23th IEEE Design Automation Conference, pp. 123-130, 1986.3 J.F. Lee and D. T. Tang, “VLSI l