臺灣博碩士論文加值系統

為了改善類比積體電路設計過程中的重複設計 (redesign iterations) 的問題，研究人員提出了採用含參數佈局圖的概念。並且，為了使用 corner stitching資料結構儲存45度角含參數佈局圖，含參數佈局圖裏的含參數多邊形必須被切割。在本篇論文中，我們提出一個以雙掃描線 (dual-scanline) 技術為基礎的平行化多邊形切割演算法，該演算法可以將45度角含參數多邊形切割為梯形。該演算法所使用的雙掃描線技術採用了 Top-Down 以及Bottom-Up兩條掃描線，並且以平行處理的方式切割多邊形。此演算法不僅可以處理45度角含參數多邊形，而且可以處理 45度角固定座標之多邊形。另外，在此研究中，我們也改進了演算法中的一個可以進行線性數學式的比較的程序。由實驗結果顯示，和以前的程式相比較，同時採用雙掃描線技術以及採用新的比較程序的的程式，在使用4個執行緒時最高可以達到 2.34 倍的執行速度。

In the analog integrated circuit design process, researchers have proposed the concept of parameterized layouts in order to mitigate the problem of redesign iterations. Additionally, in order to use corner stitching data structure in storing parameterized layouts, polygons in parameterized layouts have to be partitioned. In the thesis, a parallel polygon partitioning algorithm, which is capable of partitioning parameterized 45-degree polygons into trapezoids and is based on the dual-scanline technology, is proposed. This technology uses two scanlines, which include top-down and bottom-up scanlines, so that vertices of a polygon can be concurrently processed. The algorithm can be used to deal with not only parameterized polygons, but also fixed-coordinate polygons. In addition, the performance of a procedure in the algorithm has been improved. Compared with a partitioning program implemented previously, the new parallel partitioning program can achieve as high as 2.34X speedup while using four threads.

Chapter 1. Introduction 1
1.1. Traditional Analog Circuit Design Flow 1
1.1.1. Redesign Problem 1
1.1.2. Parameterized Layout 2
1.1.3. An Analog Design Example 3
1.1.4. Corner Stitching 6
1.2. The importance of Parallelism 8
1.3. Organization of the Thesis 9
Chapter 2. Problem Formulation 10
2.1. Parameterized Polygon with Constraints 10
Chapter 3. Preliminaries 13
3.1. First-Order Multiple-Variable Polynomials (FOMV) 13
3.1.1. Data Structure for FOMV Polynomials 14
3.1.2. Operations on FOMV Polynomials 15
3.2. The Sequential Scanline-Based Partitioning Algorithm 16
3.3. The Comparison Procedure Using MILP 22
Chapter 4. The Algorithm and Approaches 25
4.1. The Parallel Dual-Scanline Algorithm 25
4.1.1. The Stop Condition for Two Scanlines 34
4.1.2. The Effect of Case Reordering 37
4.2. Parallel Comparison Procedure 38
4.3. Improving the Comparison Procedure 39
Chapter 5. Experimental Results 42
Chapter 6. Conclusion 52
References 53
Appendix A 53
Appendix B 53

[1]I-Lun Tseng, “Symbolic extraction for estimating ana-log layout parasitics in layout-aware synthesis,” The 12th International Con-ference on Mixed Design of Integrated Circuits and Systems (MIXDES), 2005.
[2]G. T. Hamachi J. K. Ousterhout, R. N. Mayo, W. S. Scott, and G. S. Taylor, “Magic: A VLSI layout system,” in 21st Proceedings of the Design Automation Conference on Design automation, 1984.
[3]John K. Ousterhout, “Corner Stitching: A Data-Structuring Technique for VLSI Layout Tools,” IEEE Transactions on Computer-Aided Design, vol. CAD-3, no. 1, pp. 87-100, 1984.
[4]Surendra Nahar, and Sartaj Sahni, “Fast Algorithm for Polygon Decomposition,” IEEE Transactions on Computer-Aided Design, vol. 7, no. 4, pp. 473-483, 1988.
[5]David Marple, Michiel Smulders, and Henk Hegen, “Tailor: A Layout System Based on Trapezoidal Corner Stitching,” IEEE Transactions on Computer-Aided Design, vol. 9, no. 1, pp. 66-90, 1990.
[6]“OpenMP Applicaiton Program Interface Version 3.1,” July 2011.
[7]I-Lun Tseng, “Partitioning parameterized 45-degree polygons with constraint programming,” ACM Transactions on Design Automation of Electronic Systems 2008.
[8]“http://www.gurobi.com/.”
[9]I-Lun Tseng, “Efficient Partitioning of Parameterized 45-Degree Polygons with Mixed ILP,” In Proceedings of In Proceedings of IEEE Region 10 Conference (TENCON), pp., 2010.
[10]M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer, 2000.