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

1、边沿剪线技术应用於单元布局压缩.边沿剪线技术应用於单元布局压缩.17/17边沿剪线技术应用於单元布局压缩.邊緣剪線技術應用於單元佈局壓縮1邊緣剪線技術應用於單元佈局壓縮EdgedShearLineTechniquesAppliedtoCellCompaction吳占鰲蔡加春*李文達Jan-OuWuChia-ChunTsai*Wen-TaLee國立臺北科技大學電腦通訊與控制研究所纲领本篇論文中，我們在個人電腦利用邊緣剪線具折線插入技術达成一維佈局壓縮器，此壓縮器能在離線方式利用CIF的檔案銜接現有商業的佈局工具，比方TannerPro之L-Edit與Cadence之Virtuaso。同時，我們採

2、用新的邊緣鏈結相鄰矩陣的資料結構达成我們的壓縮演算法，此演算法既簡單又有效，其時間複雜度為O(NlogN)，此中N為佈局中的矩形方塊物品的數目。經由實驗結果其節省佈场面積均匀達43.8%，同時把壓縮後的結果回存CIF檔，經由商業的佈局工具再作設計規範檢核，證實完满正確。關鍵詞：一維佈局壓縮器、邊緣鏈結相鄰矩陣、剪線。投稿受理時間：90年10月26日審查通過時間：91年2月1日ABSTRACTInthispaper,weimplementedaone-dimensionallayoutcompactorbasedonedgedshearlinetechniqueswithjogsinsertio

3、nonapersonalcomputer.Thecompactorcanbeconnectedofflinefrom103臺北科技大學學報第三十五之一期currentcommerciallayouttools,suchasTannerPro-EditandCadencesLsVirtuaso,withtheCIFfileformat.Anewdatastructureofedge-linkadjacentmatrixisusedforeasilyimplementationtoourcompactionalgorithm.Thealgorithmisverysimplebutefficient

4、anditstimecomplexityisO(NlogN),whereNisthenumberofgeometricblocksinacelllayout.Experimentally,someexamplesareshownthattheareasavingisupto43.8%inaverage.Allthelayoutresultsrestoredtocommercialtoolsarealsoverified.Keywords:One-dimensionalcompactor,Edge-linkadjacentmatrix,Shearline.1042邊緣剪線技術應用於單元佈局壓縮壹

5、、簡介間，經由人工來履行此空間的壓縮是特其余繁雜且費時。所以，我們需要一個有效率的壓縮在超大型積体電路實體設計中，壓縮工具器來履行此壓縮的工作。可用來改良積體電路的佈场面積，一般經由編輯器获得的佈局設計圖雖然符合佈局設計的此篇論文中，我們經由個人電腦設計並完規則，但由於擺置設計及繞線設計的未最正确化結果，使得佈局設計圖达成後都會有一些不用成一維的壓縮器，此壓縮器能與現在的商業佈局工具在離線的情況下直接銜接，比方Tanner要的空間產生，為了增添生產積體電路的產量Pro之L-Edit或Cadence之Virtuaso。而壓縮及減少浪費成本，所以，怎样获得一個既不違器的輸入來自於佈局轉成的CIF檔

6、案，然後行反設計規則，并且又有效率的能把佈線面積壓使一維壓縮的動作，最後再回存成新的CIF檔縮到最小空間的壓縮器是特别需要的。案，而達成與現有商業佈局工具的銜接。為了單元壓縮(Cellcompaction)1-5是指在邏方便核對壓縮前後的結果，我們設計了多重的輯電路設計功能佈局达成後的空間壓縮，一般視窗介面在我們的壓縮工具系統內。圖一所示在佈局電路都是使用特定的顏色符號來表示為整個系統的流程，第一系統讀入Tanner佈局電路連接方式，如多晶矽（Poly）、接觸點後轉換出來的CIF檔案，同時把此檔案轉成中（Contact）、穿孔點（Via）和金屬線（Metal）間檔存在資料庫內，以顯示原未壓縮的

7、初始佈等，在單元佈局時，常常都存在一些多餘的空局。接著將整個佈局圖轉換成一種邊緣鏈結相105臺北科技大學學報第三十五之一期鄰矩陣表示的資料結構6-8，然後由左向右以拥有折線式邊緣剪線功能的平面掃描壓縮演算法，配合可移動最小距離的計算與二維陣列電子設計規範準則，計算出真实可向左壓縮的位移，然後依掃描的地点到邊緣相鄰矩陣表示的資料結構內改正相關的座標資料，並顯示壓縮後的佈局圖樣，經確定無誤後，再把壓縮後的資料回寫成CIF檔案格式，以銜接原佈局編輯設計系統。此壓縮演算法簡易而有效的，其時間複雜度為O（NlogN），N為一個單元佈局內的幾何方塊數。我們使用TannerPro之L-Edit實際製作了一些

8、全客戶實體佈局單元資料作為測試例子，經本系統作一維壓縮後，其執行效率均匀縮減佈场面積達43.8%。同時，我們也把壓縮後的佈局結果回存為CIF檔案格式供TannerPro之L-Edit讀取，此壓縮後佈局圖樣完满符合DRC，甚至再經由LVS及Dracula等雙重驗證，亦正確無誤。此實驗結果，可知我們的一維壓縮器是直接而有效率的工具，同時也證實此一維壓縮工具可完满銜接現有的商業佈局工具。CIFInputFullyCustomlayoutCIFoutput(TannerorCadence)ReadaCIFfileDisplaytheinitiallayoutConstructthedatastruct

9、ureofedge-linkadjacentmatrix.ProcessExecute1-DTechnologycompactionwithjogsUMCinsertion.0.5m2P2MRestoretheCIFfileLVS/Dracula圖一一維壓縮器系統流程圖本論文其余章節安排以下，第二節介紹新的邊緣鏈結相鄰矩陣之資料結構，第三節敘述一維邊緣剪線壓縮演算法，第四節顯示單元壓縮製作系統及壓縮實驗結果，最後作出結論。106貳、資料結構我們的壓縮系統與現有商業工具之銜接是以CIF檔案為媒介，輸入來自於佈局圖轉換為CIF資料格式，我們需要此佈局的資料以便壓縮時使用。在此我們定義邊緣鏈結相鄰矩

10、陣之資料結構以便存單元佈局每個幾何物品的邊，圖二所示為每一個節點定義的結構，圖中layer是代表物品佈局層為多晶矽、接觸點、穿孔點或金屬線等，edge是指左或右邊的標幟，代表此節點被掃到的是左邊或右邊，(lx,ly)和(rx,ry)分別代表物品的左上角和右下角的座標，而up、down和next分別表示指到相鄰矩陣的上、下和下一個的節點。StructNodecharlayer4;/thelayerofanobject/charedge1;/theleftorrightedgeofanobject/intlx,ly,rx,ry;/left-upandright-bottomcoordinateso

11、fanobject/Node*up,*down,*next;/linktoup,down,andnextobjects/;邊緣剪線技術應用於單元佈局壓縮3圖二相鄰矩陣之節點結構圖三所示為邊緣鏈結相鄰矩陣佈局物品圖和資料結構的關係，圖三(a)中之物品1、2、3、4分別表示四個物品，而X1到X8分別表示佈局物品的X座標，圖三(b)所示其相對應的邊緣鏈結相鄰矩陣資料結構，圖中的第0列是以各物品的左和右邊當節點，同時配合一維由左往右的X平面掃描，再依X軸座標的大小所成立出來的，比方1L(X1)、2L(X2)、.4L(X7)和4R(X8)，1L表物品1的左邊緣，其餘同樣表示法。平面掃描方法第一從第0列的

12、第0行1L開始向右掃，初始掃到2L，接著掃到1R，一直掃到自己佈局物品的右邊或比最先第0行的邊界還大或相等時，此列掃描即停止，如1R的邊是物品1的右邊，此時便停止掃描。所以第0列向右掃描鏈結串列是物品1L物品107臺北科技大學學報第三十五之一期2L物品1R。其余一個例子，圖四(b)是圖四程之演算步驟敘述以下：(a)佈局圖所成立出來的資料結構圖。1243X1X2X3X4X5X6X7X8(a)Head1L2L1R2L1R3L2R1R2R4L3L2R3R2R3R4L3R4L4R4L4R4R(b)圖三邊緣鏈結相鄰矩陣之資料結構例子(一)資料結構表示法確定後，接著怎样來成立此資料結構，以便能把佈局圖轉成

13、相對應的資料表示方式，以x軸平面掃瞄為例，其成立過(a)1L1R1R2L3L2L3L3R2R3L3R3R2R4L5L2R5L4L5L5R4R5L5R5R4R4R(b)圖四邊緣鏈結相鄰矩陣之資料結構例子(二)一、第一讀入佈局圖的檔案，轉成暫時的中間檔。把CIF的檔轉換成佈局圖全部物品為108邊緣剪線技術應用於單元佈局壓縮CM10191213201左上角與右下角的記錄資料，如圖五(b)就1319417198CCCCCC13201725是把圖五(a)轉換达成的資料檔，此中CCC119110123114CTH、CCP、CM和CCC分別代表氧化層、(b)圖五佈局圖轉換為CIF資料檔多晶矽層、金屬層和穿孔

14、點等，而lx、ly二、依佈局圖全部物品的左上角X座標和右下表示物品的左上角座標，rx、ry表示物品角X座標分別排序，並成立出第0列的節的右下角座標。點出來。比方圖五(b)佈局圖全部物品的第0列邊節點結果為。三、以第0列的節點邊當起點，由左往右掃描(a)建出每一列的資料結構。lxlyrxry四、假如此時的邊是物品的左邊，則經由邊緣CTH964014649CTH96166146176鏈結相鄰矩陣會找到另一重疊物品的左CCP11734126181CM137108217117邊，其重疊的情况如圖六(a)和(b)所示。CM96166108200C、假如此時的邊是物品的右邊，則經

15、由邊緣CM10107126116CM961810649鏈結相鄰矩陣會找到物品的左邊或此時CM101721327109臺北科技大學學報第三十五之一期5是物品最右邊的邊，則可能找不到邊，其不重疊的情况如圖七(a)和(b)所示。(b)六、依此方法，最後即可建出如圖三(b)和圖四圖七兩物品不重疊的狀況(b)的邊緣鏈結相鄰矩陣的資料結構。上述之邊緣鏈結相鄰矩陣資料結構之建置是基於排序與掃描方法，總共所花費的時間為O(NlogN)，N為佈局單元物品的數目。(a)參、邊緣剪線的壓縮演算法我們以邊緣鏈結相鄰矩陣的資料結構為基礎，配合以X軸方向邊緣剪線方法來壓縮單(b)圖六兩物品重疊的狀況元佈局圖，圖八所示為我

16、們的一維壓縮演算法的流程圖。此演算法第一成立多重文件視窗處理界面系統，接著讀入TannerPro佈局後轉換(a)出來的CIF檔案，再把整個佈局圖轉換成一種邊緣鏈結相鄰矩陣表示的資料結構，然後使用具折線式邊緣剪線功能的平面掃描方法，由左1106邊緣剪線技術應用於單元佈局壓縮向右掃描，並配合可移動最小距離的計算，計算出可向左移動多少空間，再配合二維陣列DRC的法則，算出真实向左可壓縮的位移，然後依掃描的地点到邊緣相鄰矩陣表示的資料結構內改正相關的資料，即达成壓縮工作。為圖八一維壓縮演算法之流程圖了可使Tanner回讀以便核對DRC的功能，我們把达成壓縮佈局圖之資料結構內的資料回存成CIF的檔案格式

17、。111臺北科技大學學報第三十五之一期圖九所示為NOR閘佈局圖的平面掃瞄例子，圖九NOR閘佈局圖的平面掃瞄軌跡圖中的S1、S2、S3、S4、S5和S6即為依序由左往右掃描的軌跡，此中S4是拥有插入折線線段的掃瞄軌跡。在平面的折線段掃描中，其佈局圖的Y軸方向能否能插入轉彎線段，依佈局圖的分佈狀況，我們列出如圖十有關折線段上段一端轉彎的規則，圖中之轉彎線段向左方移位其新的Y軸b1座標為：yb1=yb+S(D,P)+WP(1)此中S(D,P)表示diffusion和poly兩物品之佈局規則的最小間距，Wp表示poly線的最小寬度。S1S2S3S4S5S6圖十往左方上折線段距離的判斷圖十中X軸方向新的

18、Xb1坐標為當時平面掃描的X軸座標減上物品的寬度值；所以能否可插入折線，其判斷的條件即Hy要符合式下列式：HyS(D,P)+Wp(2)同理，如圖十一所示另一端轉彎情況，此折線段向右方移位，其新的yb1為yb1=yb-S(D,P)+WP(3)而圖十一中新的Xb1坐標為當時平面掃描的X軸座標值減上物品的寬度值，所以能否1128邊緣剪線技術應用於單元佈局壓縮7可插入折線，其判斷的條件即Hy要符合以下(6)式中，如假設這些物品的相隔佈局規則式：都一樣，則可簡化為HyS(D,P)+WPHy2*2S(A,B)+WB(7)(4)圖十二線段上下兩端產生折線圖十一往右方下折線段距離的判斷圖十三中，假如有N條的條

19、線段要產生轉圖十二所示的情況，即線段一端先向左邊彎時，則(7)式之Hy的限制大小為轉彎，接著又向右轉彎，此時中間的距離HyHy2N*S(A,B)+Wp(8)需符合下式：Hy2*S(D,P)+Wp(5)假如中間是兩條線段要產生轉彎時，如圖十三所示，其Hy的限制大小為圖十三兩條線段產生轉彎Hy2*S(A,B)+WB+S(B,C)+Wc(6)依據前面所詳細敘述的折線加入之邊緣剪113臺北科技大學學報第三十五之一期線掃瞄壓縮方法，我們綜合整理出一維壓縮演算法，如圖十四所示。AlgorithmComapction-Sweep(Xmin,Xmax)/endofComapction-Sweep/Proced

20、urejog_compaction(adjacency)pointcthcthi=search_CTH()；/FindalltheCTHtransistors/intvtojogsi=search_crosscth()；/FindtheCTHfromverticaldirections/XminandXmaxaretheXcoordinatesoftheleft-mostinthtojogsh=search_crosscth()；/Findandright-mostedgesinalayout,respectively/theCTHfromhorizontaldirections/Letadj

21、acencybetheedge-linkadjacentmatrixandupblock=calluph(inth)；/Computescanxsibethepointerofcurrentsweep/offsetfromCTHstoup-middleobjects/thloblockcallloh(inth)；/Computescanxsi=adjacency0；/Startingsweepfromthe0columninadjacentmatrix/offsetfromCTHstobottom-middleobjects/while(scanxsi.rxXmax)for(jog=1;jog

22、=4*scanxsj=get_next(*si)；/Findalltheedges(si-1)+4*(si)&loblock=4*(si-1)+4*(si)viewedfrom*si/Withconsiderationof0.5umtechnologies/sv=get_min(scanxsi,scanxsj)；/Getminimummove_jog()；spacebetweenobjectssiandsj/estimatemovabledisplacement/if(scanxsj.layer“/IsCTHhinoxide”)layer?/find_hor_contact()；get_drc

23、()；/Getcorrespondwidthorspacefrom/Updatexcoordinates/selectedtechnologyprocess/refresh_vertical()；displacement_compute()；/Computethe/Updateycoordinates/movabledisplacement,movx/elsecoordinate_refresh()；/Updatethewithout_jog()；coordinateswiththelocaldisplacement/Withoutjogsinsertion/fromadjacentmatri

24、x/elsejog_compaction()；/Withjogsinsertion/圖十四一維壓縮演算法scanxsiadjacency0；down/endofwhile/此演算法包含兩個部份，writeback_CIFfile()；/RestoredintotheCIFfile/114邊緣剪線技術應用於單元佈局壓縮9Compaction-Sweep(Xmin,Xmax)是專門負責沒有折線的壓縮方法，物品的一邊向右邊找另一物品最凑近的邊，同時判斷能否為電晶體氧化層CTH，假如不是，則由displacement_compute()計算出可位移的大小，再配合get_drc()得佈局規則的位移大小，

25、此可算出真正可壓縮的大小，然後最後經由coordinate_refresh()更新邊緣鏈結相鄰矩陣資料結構內的資料。假如是，為了不改變電晶體的L和W，而跳至jog_compaction(adjacency)去做折線的壓縮動作，而產生折線情况是當一垂直方向的物品一端固定另一端產生向右壓縮，如圖十與十一所示；或物品的上下兩端固定，而中間產生壓縮，如圖十二所示；以及有更多的物品產生中間壓縮，如圖十三所示。此掃描的壓縮演算法可使用在任何區域的搜尋，直接找到所要移動的掃描軌跡，其最差情況之總掃描次數為2*N，橫向掃描最多為2個節點，所以最差情況還是2*2*N，亦即掃描壓縮方法的時間複雜度O(N)。綜合第

26、二節所述之邊緣鏈結相鄰矩陣資料結構之建置時間為O(NlogN)，故我們的邊緣剪線技術之壓縮演算法其時間複雜度為O(NlogN)。肆、壓縮實驗結果我們的壓縮系統之硬體設備採用華碩筆記型電腦L8400系列，中央處理單元是IntelPentium-IIII400MHz，內建192MB的記憶體，程式以BorlandC+Builder4.0編寫而成，並以UMC0.5um2P2M製程的設計規則為例。我們針對每一種單元佈局未壓縮的初始佈局和115臺北科技大學學報第三十五之一期未具折線式壓縮後的佈局做一個比較，同時顯示壓縮的減縮比，如表一所示，很明顯壓縮前和壓縮後減縮比均匀節省面積達40.8%，同時我們並做了

27、有折線和沒折線的比較，我們發現有折線的壓縮比均匀節省面積達43.8%，比沒折線的壓縮在面積上均匀又節省了3%。接著以佈局的矩形個數來探討其執行時間的關係，以圖十五所示，我們可發現當佈局矩形個數在100以下時，其執行時間幾乎凑近線性；當佈局矩形個數大於100時，執行時間凑近對數型。同時我們把此結果和Nandy6的壓縮器比較，Nandy壓縮器佈局矩形個數和執行時間如圖十六，我們發現因為Nandy的壓縮器其資料結構是用四元樹建出來的，所以同樣在100個矩形的線性關係，本系統執行時間快了十倍之多。表一各種單元具折線與非具折線之壓縮結果InitialWithoutjogsWithjogsExamplel

28、ayoutAreaArea_AreaArea_Run_(m2)(m2)saving(m2)savingtimeNOT31*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%184ms20

29、0nie150mt矩形個數和執n100o行時間關係ituc50exe01723478185124340numberoflayoutrectangles圖十五本系統時間對幾何物品的關係oc1esn0.8iem0.6tNandy曲線no0.4tuc0.2exe013293040456270numberoflayoutrectangles11610邊緣剪線技術應用於單元佈局壓縮我們製作一個一維單元佈局具折線式壓圖十六Nandy6時間對幾何物品的關係縮器，能配合讀取現有商業佈局軟體Tanner圖十七(a)與(b)分別顯示四位元計數器初ProL-Edit之CIF檔案之讀取與回存及UMC始和壓縮後的佈局，

30、而圖十七(c)是執行後的詳0.5m2P2M之製程規則，並實際达成多個單細統計表，此中壓縮面積節省了31%。元佈局壓縮，壓縮後佈局資料完满正確而符合DRC，同時亦經LVS及Dracula雙重驗證，亦完满無誤。我們的壓縮演算法引用剪線觀念的初始的佈局基礎，並採用改良式的邊緣鏈結相鄰矩陣資料結構，經由實驗證明此方法是既簡單又有效率的。壓縮後的佈局此壓縮器很简单擴充與適用於更進階的製程技術，如0.35m或0.18m等，只需更新其二維陣列電子設計規範準則即可。(c)壓縮後的統計資料參考文獻圖十七四位元計數器的壓縮結果1J.F.Lee,“ANewFrameworkofDesign伍、結論RulesforcompactionofVLSILayout,”IEEETrans.OnComputer-AidedDesign,117臺北科技大學學報第三十五之一期11Vol7,No.11,pp.1159-1204,198