臺灣博碩士論文加值系統

本論文提出了一種從佈局設計中找出矩陣結構(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.