边缘剪线技术应用於单元布局压缩.doc

邊緣剪線技術應用於單元佈局壓縮1邊緣剪線技術應用於單元佈局壓縮Edged Shear Line Techniques Applied toCell Compaction吳占鰲蔡加春*李文達Jan-Ou WuChia-Chun Tsai*Wen-Ta Lee國立臺北科技大學電腦通訊與控制研究所摘要本篇論文中，我們在個人電腦利用邊緣剪線具折線插入技術完成一維佈局壓縮器，此壓縮器能在離線方式利用CIF的檔案銜接現有商業的佈局工具，例如Tanner Pro之L-Edit 與Cadence 之Virtuaso。同時，我們採用新的邊緣鏈結相鄰矩陣的資料結構完成我們的壓縮演算法，此演算法既簡單又有效，其時間複雜度為O(N logN)，其中N為佈局中的矩形方塊物件的數目。經由實驗結果其節省佈局面積平均達43.8%，同時把壓縮後的結果回存CIF 檔，經由商業的佈局工具再作設計規範檢核，證實完全正確。關鍵詞：一維佈局壓縮器、邊緣鏈結相鄰矩陣、剪線。投稿受理時間：90年10月26日審查通過時間：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 compactor 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 and 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-link adjacent matrix, Shear line.1132壹、簡介在超大型積体電路實體設計中，壓縮工具可用來改善積體電路的佈局面積，一般經由編輯器得到的佈局設計圖雖然符合佈局設計的規則，但由於擺置設計及繞線設計的未最佳化結果，使得佈局設計圖完成後都會有一些不必要的空間產生，為了增加生產積體電路的產量及減少浪費成本，因此，如何得到一個既不違反設計規則，而且又有效率的能把佈線面積壓縮到最小空間的壓縮器是非常需要的。單元壓縮(Cell compaction)1-5是指在邏輯電路設計功能佈局完成後的空間壓縮，一般在佈局電路都是使用特定的顏色符號來表示電路連接方式，如多晶矽（Poly）、接觸點（Contact）、穿孔點（Via）和金屬線（Metal）等，在單元佈局時，往往都存在一些多餘的空間，經由人工來行使此空間的壓縮是非常的繁雜且費時。因此，我們需要一個有效率的壓縮器來行使此壓縮的工作。此篇論文中，我們經由個人電腦設計並完成一維的壓縮器，此壓縮器能與現在的商業佈局工具在離線的情況下直接銜接，例如Tanner Pro之L-Edit 或Cadence之 Virtuaso。而壓縮器的輸入來自於佈局轉成的CIF檔案，然後行使一維壓縮的動作，最後再回存成新的CIF檔案，而達成與現有商業佈局工具的銜接。為了方便核對壓縮前後的結果，我們設計了多重的視窗介面在我們的壓縮工具系統內。圖一所示為整個系統的流程，首先系統讀入Tanner佈局後轉換出來的CIF檔案，同時把此檔案轉成中間檔存在資料庫內，以顯示原未壓縮的初始佈局。接著將整個佈局圖轉換成一種邊緣鏈結相鄰矩陣表示的資料結構6-8，然後由左向右以具有折線式邊緣剪線功能的平面掃描壓縮演算法，配合可移動最小距離的計算與二維陣列電子設計規範準則，計算出真正可向左壓縮的位移，然後依掃描的位置到邊緣相鄰矩陣表示的資料結構內更改相關的座標資料，並顯示壓縮後的佈局圖樣，經確定無誤後，再把壓縮後的資料回寫成CIF檔案格式，以銜接原佈局編輯設計系統。此壓縮演算法簡易而有效的，其時間複雜度為O（N logN），N為一個單元佈局內的幾何方塊數。我們使用Tanner Pro之L-Edit實際製作了一些全客戶實體佈局單元資料作為測試例子，經本系統作一維壓縮後，其執行效率平均縮減佈局面積達43.8%。同時，我們也把壓縮後的佈局結果回存為CIF 檔案格式供Tanner Pro之L-Edit 讀取，此壓縮後佈局圖樣完全符合DRC，甚至再經由LVS及Dracula等雙重驗證，亦正確無誤。此實驗結果，可知我們的一維壓縮器是直接而有效率的工具，同時也證實此一維壓縮工具可完全銜接現有的商業佈局工具。圖一一維壓縮器系統流程圖本論文其它章節安排如下，第二節介紹新的邊緣鏈結相鄰矩陣之資料結構，第三節敘述一維邊緣剪線壓縮演算法，第四節顯示單元壓縮製作系統及壓縮實驗結果，最後作出結論。貳、資料結構我們的壓縮系統與現有商業工具之銜接是以CIF檔案為媒介，輸入來自於佈局圖轉換為CIF資料格式，我們需要此佈局的資料以便壓縮時使用。在此我們定義邊緣鏈結相鄰矩陣之資料結構以便存單元佈局每個幾何物件的邊，圖二所示為每一個節點定義的結構，圖中layer是代表物件佈局層為多晶矽、接觸點、穿孔點或金屬線等，edge是指左或右邊的標幟，代表此節點被掃到的是左邊或右邊，(lx,ly)和(rx,ry)分別代表物件的左上角和右下角的座標，而up、down和next分別表示指到相鄰矩陣的上、下和下一個的節點。Struct Nodechar layer4; / the layer of an object/ 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 /;圖二相鄰矩陣之節點結構3圖三所示為邊緣鏈結相鄰矩陣佈局物件圖和資料結構的關係，圖三(a)中之物件1、2、3、4分別表示四個物件，而X1到X8分別表示佈局物件的X座標，圖三(b)所示其相對應的邊緣鏈結相鄰矩陣資料結構，圖中的第0列是以各物件的左和右邊當節點，同時配合一維由左往右的X平面掃描，再依X軸座標的大小所建立出來的，例如1L(X1)、2L(X2)、.4L(X7)和4R(X8)，1L表物件1的左邊緣，其餘同樣表示法。平面掃描方法首先從第0列的第0行1L開始向右掃，初始掃到2L，接著掃到1R，一直掃到本身佈局物件的右邊或比最初第0行的邊界還大或相等時，此列掃描即停止，如1R的邊是物件1的右邊，此時便停止掃描。所以第0列向右掃描鏈結串列是物件1L物件2L物件1R。另外一個例子，圖四(b)是圖四(a)佈局圖所建立出來的資料結構圖。(a)(b)圖三邊緣鏈結相鄰矩陣之資料結構例子(一)4資料結構表示法確定後，接著如何來建立此資料結構，以便能把佈局圖轉成相對應的資料表示方式，以 x軸平面掃瞄為例，其建立過程之演算步驟敘述如下：(a)(b) 圖四邊緣鏈結相鄰矩陣之資料結構例子(二)一、 首先讀入佈局圖的檔案，轉成暫時的中間檔。把CIF的檔轉換成佈局圖所有物件為左上角與右下角的記錄資料，如圖五(b)就是把圖五(a)轉換完成的資料檔，其中CTH、CCP 、CM和CCC分別代表氧化層、多晶矽層、金屬層和穿孔點等，而lx、ly表示物件的左上角座標，rx、ry表示物件的右下角座標。(a) lx ly rx ryCTH 96 40 146 49CTH 96 166 146 176CCP 117 34 126 181CM 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) 圖五佈局圖轉換為CIF資料檔二、依佈局圖所有物件的左上角X座標和右下角X座標分別排序，並建立出第0列的節點出來。例如圖五(b)佈局圖所有物件的第0列邊節點結果為10 10 10 13 13 17 17 96 96 96 96 96 106 108 117 119 123 126 136 137 146 146 213 213 217。三、以第0列的節點邊當起點，由左往右掃描建出每一列的資料結構。四、假如此時的邊是物件的左邊，則經由邊緣鏈結相鄰矩陣會找到另一重疊物件的左邊，其重疊的情形如圖六(a)和(b)所示。五、假如此時的邊是物件的右邊，則經由邊緣鏈結相鄰矩陣會找到物件的左邊或此時是物件最右邊的邊，則可能找不到邊，其不重疊的情形如圖七(a)和(b)所示。六、依此方法，最後便可建出如圖三(b)和圖四(b)的邊緣鏈結相鄰矩陣的資料結構。 (a) (b)圖六兩物件重疊的狀況5(a)(b)圖七兩物件不重疊的狀況上述之邊緣鏈結相鄰矩陣資料結構之建置是基於排序與掃描方法，總共所花費的時間為O(N logN)，N為佈局單元物件的數目。參、邊緣剪線的壓縮演算法我們以邊緣鏈結相鄰矩陣的資料結構為基礎，配合以X軸方向邊緣剪線方法來壓縮單元佈局圖，圖八所示為我們的一維壓縮演算法的流程圖。此演算法首先建立多重文件視窗處理界面系統，接著讀入Tanner Pro佈局後轉換出來的CIF檔案，再把整個佈局圖轉換成一種邊緣鏈結相鄰矩陣表示的資料結構，然後使用具折線式邊緣剪線功能的平面掃描方法，由左向右掃描，並配合可移動最小距離的計算，計算出可向左移動多少空間，再配合二維陣列DRC的法則，算出真正向左可壓縮的位移，然後依掃描的位置到邊緣相鄰矩陣表示的資料結構內更改相關的資料，即完成壓縮工作。為了可使Tanner回讀以便核對DRC的功能，我們把完成壓縮佈局圖之資料結構內的資料回存成CIF的檔案格式。圖八一維壓縮演算法之流程圖6圖九所示為NOR閘佈局圖的平面掃瞄例子，圖中的S1、S2、S3、S4、S5和S6即為依序由左往右掃描的軌跡，其中S4是具有插入折線線段的掃瞄軌跡。在平面的折線段掃描中，其佈局圖的Y軸方向是否能插入轉彎線段，依佈局圖的分佈狀況，我們列出如圖十有關折線段上段一端轉彎的規則，圖中之轉彎線段向左方移位其新的Y軸yb1座標為：yb1= yb+ S(D,P) + WP (1)其中S(D,P)表示diffusion和poly兩物件之佈局規則的最小間距，Wp表示poly線的最小寬度。圖九NOR閘佈局圖的平面掃瞄軌跡圖十往左方上折線段距離的判斷圖十中X軸方向新的Xb1坐標為當時平面掃描的X軸座標減上物件的寬度值；所以是否可插入折線，其判斷的條件即Hy要符合式下列式：Hy S(D,P) + Wp (2)同理，如圖十一所示另一端轉彎情況，此折線段向右方移位，其新的yb1為yb1 = yb - S( D,P) + WP (3)而圖十一中新的Xb1坐標為當時平面掃描的X軸座標值減上物件的寬度值，所以是否可插入折線，其判斷的條件即Hy要符合下列式：Hy S(D,P)+ WP (4)圖十一往右方下折線段距離的判斷圖十二所示的情況，即線段一端先向左邊轉彎，接著又向右轉彎，此時中間的距離Hy需符合下式：7Hy 2*S(D,P)+ Wp (5)如果中間是兩條線段要產生轉彎時，如圖十三所示，其Hy的限制大小為Hy 2*S(A,B)+ WB+S(B,C)+ Wc (6)(6)式中，如假設這些物件的相隔佈局規則都一樣，則可簡化為Hy 2*2S(A,B)+ WB (7)圖十二線段上下兩端產生折線圖十三中，如果有N條的條線段要產生轉彎時，則(7)式之Hy的限制大小為Hy 2 N *S(A,B)+ Wp (8)圖十三兩條線段產生轉彎8依據前面所詳細敘述的折線加入之邊緣剪線掃瞄壓縮方法，我們綜合整理出一維壓縮演算法，如圖十四所示。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 column 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“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 insertion /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=search_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=4*(si-1)+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 / 圖十四一維壓縮演算法此演算法包括兩個部份，Compaction-Sweep (Xmin,Xmax)是專門負責沒有折線的壓縮方法，物件的一邊向右邊找另一物件最靠近的邊，同時判斷是否為電晶體氧化層CTH，如果不是，則由displacement_ compute()計算出可位移的大小，再配合get_drc()得佈局規則的位移大小，此可算出真正可壓縮的大小，然後最後經由coordinate_refresh()更新邊緣鏈結相鄰矩陣資料結構內的資料。如果是，為了不改變電晶體的L和W，而跳至jog_compaction (adjacency)去做折線的壓縮動作，而產生折線情形是當一垂直方向的物件一端固定另一端產生向右壓縮，如圖十與十一所示；或物件的上下兩端固定，而中間產生壓縮，如圖十二所示；以及有更多的物件產生中間壓縮，如圖十三所示。此掃描的壓縮演算法可使用在任何區域的搜尋，直接找到所要移動的掃描軌跡，其最差情況之總掃描次數為2*N，橫向掃描最多為2個節點，所以最差情況還是2*2*N，亦即掃描壓縮方法的時間複雜度O(N)。綜合第二節所述之邊緣鏈結相鄰矩陣資料結構之建置時間為O(N logN)，故我們的邊緣剪線技術之壓縮演算法其時間複雜度為O(N logN)。肆、壓縮實驗結果9我們的壓縮系統之硬體設備採用華碩筆記型電腦L8400系列，中央處理單元是IntelPentium-IIII 400 MHz，內建192MB的記憶體，程式以Borland C+ Builder 4.0編寫而成，並以UMC 0.5um 2P2M製程的設計規則為例。我們針對每一種單元佈局未壓縮的初始佈局和未具折線式壓縮後的佈局做一個比較，同時顯示壓縮的減縮比， 如表一所示，很明顯壓縮前和壓縮後減縮比平均節省面積達40.8%，同時我們並做了有折線和沒折線的比較，我們發現有折線的壓縮比平均節省面積達43.8%，比沒折線的壓縮在面積上平均又節省了3%。接著以佈局的矩形個數來探討其執行時間的關係，以圖十五所示，我們可發現當佈局矩形個數在100以下時，其執行時間幾乎接近線性；當佈局矩形個數大於100時，執行時間接近對數型。同時我們把此結果和Nandy6的壓縮器比較，Nandy壓縮器佈局矩形個數和執行時間如圖十六，我們發現因為Nandy的壓縮器其資料結構是用四元樹建出來的，所以同樣在100個矩形的線性關係，本系統執行時間快了十倍之多。表一 各種單元具折線與非具折線之壓縮結果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-FF119*4176*3840%75*3841%39msJK-FF113*4485*4031%82*4034%40msD-FF126*4092*3732%91*3733%42msCounter445*48345*4330%338*4331%184ms圖十五本系統時間對幾何物件的關係圖十六 Nandy6時間對幾何物件的關係10圖十七(a)與(b)分別顯示四位元計數器初始和壓縮後的佈局，而圖十七(c)是執行後的詳細統計表，其中壓縮面積節省了31%。(a)初始的佈局(b)壓縮後的佈局(c)壓縮後的統計資料圖十七四位元計數器的壓縮結果伍、結論我們製作一個一維單元佈局具折線式壓縮器，能配合讀取現有商業佈局軟體Tanner Pro L-Edit之CIF 檔案之讀取與回存及UMC 0.5m 2P2M之製程規則，並實際完成多個單元佈局壓縮，壓縮後佈局資料完全正確而符合DRC，同時亦經LVS及Dracula雙重驗證，亦完全無誤。我們的壓縮演算法引用剪線觀念的基礎，並採用改良式的邊緣鏈結相鄰矩陣資料結構，經由實驗證明此方法是既簡單又有效率的。此壓縮器很容易擴充與適用於更進階的製程技術，如0.35m或0.18m等，只要更新其二維陣列電子設計規範準則即可。參考文獻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 layou