跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.81) 您好!臺灣時間:2024/12/08 04:09
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:蔡士成
研究生(外文):Shih-Cheng Tsai
論文名稱:使用幾何方法於平坦佈局資料來辨識矩陣結構
論文名稱(外文):Geometric Approach to Array Structure Recognition in Flatten Layout
指導教授:林榮彬林榮彬引用關係
學位類別:碩士
校院名稱:元智大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2006
畢業學年度:94
語文別:英文
論文頁數:32
中文關鍵詞:矩陣結構演算法辨識幾何
外文關鍵詞:array structureflatten layoutrecognitiongeometric
相關次數:
  • 被引用被引用:0
  • 點閱點閱:188
  • 評分評分:
  • 下載下載:1
  • 收藏至我的研究室書目清單書目收藏:0
本論文提出了一種從佈局設計中找出矩陣結構(array structure)的演算法,所找出的矩陣結構可以用來降低製程規則驗證的處理時間。此演算法含有四個階段,第一個階段先為不同的元件模版(cell template)的元計來個別建立所屬的紅黑樹(R-B tree),然後再利用所有的紅黑樹來找出草稿矩陣(scratched array),每個草稿矩陣可視為一個矩形。第二階段藉由幾何合併操作來連結相同組成元件的矩形的草稿矩陣,合併兩個草稿矩陣後的物件稱為草稿嵌接矩陣(scratched rabbeted array),第三階段利用嵌接及矩形的草稿矩陣交錯的方式找出馬賽克矩陣(mosaic array),一個馬賽克矩陣包含了許多馬賽克元件(mosaic cell),每一個馬賽克元件都包含超過一個元件範例(cell instance),最後一個階段將雜訊元件(noise cell)從矩陣中移除並決定所找出的矩陣的實際形狀。此演算法的時間複雜度為 , 為草稿嵌接矩陣個數, 為 的元件個數。空間複雜度為 , 為模板 的元件個數。
This thesis proposes an algorithm to find out array structures from a layout design. The so-obtained array structures can be employed to reduce DRC processing time. Our algorithm consists of four phases. In the first phase, we build a R-B tree for all the cells with the same cell template. We then employ R-B trees to find out all scratched arrays. Each of the scratched arrays is treated as a rectangle. The second phase joins the rectangular scratched arrays with the same cell template by performing a geometric union operation. An object after uniting two scratched arrays is called a scratched rabbeted array. The third phase identifies mosaic arrays by intersecting the scratched rabbeted arrays including rectangular scratched array. A mosaic array consists of many mosaic cells, each of which contains more than one cell instance. The last phase removes the noise cell from the (mosaic) arrays and decides the actual shapes of the recognized arrays by removing those cells not useful for reducing DRC processing time. The algorithm has the time complexity , where is the number of scratched rabbeted arrays and is the number of cells for . The space complexity is , where is the number of cells with template .
List of Figures ii
Symbol Definitions iii
Chapter 1. Introduction 1
1.1. Background and Motivation 1
1.2. Contributions 5
1.3. Thesis Organization 5
Chapter 2. Problem Formulation 6
Chapter 3. Algorithm and Implementation 12
3.1. Rectangular Scratched Array Recognition 12
3.1.1. Tentative Anchor Cell 15
3.1.2. Leap 17
3.1.3. Dimension of Rectangular Scratched Array 18
3.2. Scratched Mosaic Arrays Recognition 21
3.2.1. Forming Scratched Rabbeted Arrays 22
3.2.2. Forming Scratched Mosaic Arrays 22
3.3. Qualifying and Resizing Scratched Arrays 27
Chapter 4. Experimental Results 28
Chapter 5. Conclusion and Future work 31
Reference 32
[1] G. S. Taylor, J. K. Ousterhout, “Magic''s incremental design-rule checker” Proceedings of the 21st conference on Design automation, 1984,Pages: 160 – 165
[2] M. H. Arnold,J. K. 0usterhout, “Lyra: A new approach to geometric layout rule checking” Proceedings of the 19th conference on Design automation,1982,Pages: 530 – 536
[3] T. Whitney, “A hierarchical design analysis front end”. In proceeding the first conference on VLSI, 1981, Pages 530-536
[4] T. Whitney, “A hierarchical design checker”. Caltech CSTR: 1981. 4320-tr-81
[5] Yu-Cheng Chiang, "Array Structure Recognition in Flatten Layout" Yuan Ze University, Degree of Master, 2005.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top