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

《边缘剪线技术应用於单元布局压缩》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、邊緣剪線技術應用於單元佈局壓縮　　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-dimensionallayoutcompactorbasedonedgedshearlinetechniqueswithjogsinsertiononapersonalcompute

3、r.Thecompactorcanbeconnectedofflinefromcurrentcommerciallayouttools,suchasTannerPro’sL-EditandCadence’sVirtuaso,withtheCIFfileformat.Anewdatastructureofedge-linkadjacentmatrixisusedforeasilyimplementationtoourcompactionalgorithm.Thealgorithmisverysimplebutefficientanditstimecomplexit

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

5、簡介在超大型積体電路實體設計中，壓縮工具可用來改善積體電路的佈局面積，一般經由編輯器得到的佈局設計圖雖然符合佈局設計的規則，但由於擺置設計及繞線設計的未最佳化結果，使得佈局設計圖完成後都會有一些不必要的空間產生，為了增加生產積體電路的產量及減少浪費成本，因此，如何得到一個既不違反設計規則，而且又有效率的能把佈線面積壓縮到最小空間的壓縮器是非常需要的。單元壓縮(Cellcompaction)[1-5]是指在邏輯電路設計功能佈局完成後的空間壓縮，一般在佈局電路都是使用特定的顏色符號來表示電路連接方式，如多晶矽（Poly）、接觸點（Contact）、穿孔點（Via）和

6、金屬線（Metal）等，在單元佈局時，往往都存在一些多餘的空間，經由人工來行使此空間的壓縮是非常的繁雜且費時。因此，我們需要一個有效率的壓縮器來行使此壓縮的工作。此篇論文中，我們經由個人電腦設計並完成一維的壓縮器，此壓縮器能與現在的商業佈局工具在離線的情況下直接銜接，例如TannerPro之L-Edit或Cadence之Virtuaso。而壓縮器的輸入來自於佈局轉成的CIF檔案，然後行使一維壓縮的動作，最後再回存成新的CIF檔案，而達成與現有商業佈局工具的銜接。為了方便核對壓縮前後的結果，我們設計了多重的視窗介面在我們的壓縮工具系統內。圖一所示為整個系統的流程，

7、首先系統讀入Tanner佈局後轉換出來的CIF檔案，同時把此檔案轉成中間檔存在資料庫內，以顯示原未壓縮的初始佈局。接著將整個佈局圖轉換成一種邊緣鏈結相鄰矩陣表示的資料結構[6-8]，然後由左向右以具有折線式邊緣剪線功能的平面掃描壓縮演算法，配合可移動最小距離的計算與二維陣列電子設計規範準則，計算出真正可向左壓縮的位移，然後依掃描的位置到邊緣相鄰矩陣表示的資料結構內更改相關的座標資料，並顯示壓縮後的佈局圖樣，經確定無誤後，再把壓縮後的資料回寫成CIF檔案格式，以銜接原佈局編輯設計系統。此壓縮演算法簡易而有效的，其時間複雜度為O（NlogN），N為一個單元佈局內的幾

8、何方塊數。我們使用Tan