臺灣博碩士論文加值系統

由於矽智財的普遍使用以及越來越多的不同元件整合成系統單晶片，混合尺寸的電路元件置放成為實體電路設計中關鍵的一環。然而在處理置放問題時，對於大電路單元和標準電路元，兩者演算法在本質上差異甚大，因此要在一套流程中一起完成混合尺寸的置放是十分具有挑戰性的問題。在這篇論文中，我們將原本的置放問題轉化為一套新的最佳化模型，並以數學解析的方法配合多階層式架構求解。由實驗結果可知此套模型確實可用於實作全域式置放器，以應用增廣拉格朗日方法做為非線性最佳化求解的核心，能夠對整體電路繞線長度得到良好的成果。

Due to the trends of IP re-use and the SOC integration, mixed-size designs are very common now, and the quality of mixed-size placement becomes a critical step in the VLSI physical design. However, because the algorithms of macro placement and standard-cell placement are fundamentally distinct, placing the mixed-size design in a single flow is actually a challenging problem. In this thesis, we formulate the general placement problem as a nonlinear constrained optimization problem and solve it by the analytical approach incorporating with a multi-level scheme. The experimental results clearly show that our model can be employed as a global placer. By applying the augmented Lagrangian method to perform nonlinear programming, the result of the total half-perimeter wire length is comparable to current state-of-the-art placers.

1 Overview 5
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Our Contribution . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2 Preliminaries 8
2.1 Placer Classication . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Previous Work of Mixed-size Placer . . . . . . . . . . . . . . . 10
2.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.1 Concept . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Quadratic Objective . . . . . . . . . . . . . . . . . . . 12
2.3.3 Nonlinear Constraints Based on Bin Utilization . . . . 13
3 Algorithm and Implementation 18
3.1 Main Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2 Augmented Lagrangian Method . . . . . . . . . . . . . . . . . 20
3.3 Nonlinear Conjugate Gradient Minimization . . . . . . . . . . 21
3.4 Negative Gradient Evaluation . . . . . . . . . . . . . . . . . . 23
3.5 Multi-Level Scheme . . . . . . . . . . . . . . . . . . . . . . . . 24
3.6 Legalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.6.1 Legalization Flow . . . . . . . . . . . . . . . . . . . . . 26
3.6.2 Implementation of Macro Legalization . . . . . . . . . 27
4 Experimental Results 29
4.1 Some IBM ICCAD'04 Results . . . . . . . . . . . . . . . . . . 30
4.2 Macro Legalization . . . . . . . . . . . . . . . . . . . . . . . . 31
5 Conclusion 36

[1] C.-C. Chang, J. Cong, and X. Yuan, Multi-level Placement for Large-Scale Mixed-Size IC Designs , In Proc. Asia South Pacific Design Automation Conference, pp. 325-330, 2003.
[2] A. E. Caldwell, A. B. Kahng, and I. L. Markov, Can Recursive Bisection Alone Produce Routable Placements? , In Proc. Design Automation Conference, pp. 477-482, 2000.
[3] A. Agnihotri, M. C. Yildiz, A. Khatkhate, A. Mathur, S. Ono, and P. H. Madden, Fractional cut: Improved recursive bisection placement , In Proc. International Conference on Computer-Aided Design, pp. 307-310, 2003.
[4] C.-C. Chang, J. Cong, D. Pan and X. Yuan, Physical hierarchy generation with routing congestion control, In Proc. International Symposium on Physical Design, pp. 36-41, 2002
[5] H. Eisenmann and F. M. Johannes, Generic Global Placement and Floorplanning, In Proc. Design Automation Conference, pp. 269-274, 1998
[6] N. Viswanathan and Chris C.-N. Chu, FastPlace: Efficient Analytical Placement using Cell Shifting, Iterative Local Refinement and a Hybrid Net Model, In Proc. International Symposium on Physical Design, pp. 26-33, 2004
[7] Andrew B. Kahng and Q.Wang, Implementation and Extensibility of an Analytic Placer, In Proc. International Symposium on Physical Design, pp. 18-25, 2004
[8] J. M. Kleinhans, Georg Sigl, F. M. Johannes and K. J. Antreich, GORDIAN: VLSI Placement by Quadratic Programming and Slicing Optimization, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.10, No.3, Mar 1991
[9] Georg Sigl, K. Doll and F. M. Johannes, Analytical Placement: A Linear or a Quadratic Objective Function? , In Proc. ACM/IEEE Design Automation Conference, pp. 427-431, 1991
[10] S. N. Adya and I. L. Markov, Consistent Placement of Macro-Blocks Using Floorplanning and Standard-Cell Placement , In Proc. International Symposium on Physical Design, pp. 12-17, 2002
[11] A. Khatkhate, Chen Li, A. R. Agnihotri, M. C. Yildiz, S. Ono, C.-K. Koh and P. H. Madden, Recursive Bisection Based Mixed Block Placement , In Proc. International Symposium on Physical Design, pp. 84-89, 2004
[12] K. Vorwerk, A. Kennings and A. Vannelli, Engineering Details of a Stable Force-Directed Placer, In Proc. IEEE/ACM International Conference on Computer-Aided Design, pp. 573-580, 2004
[13] B. Hu and M. Marek-Sadowska, Fine Granularity Clustering-Based Placement, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol.23, No.4, Apr 2004
[14] A. B. Kahng and Q. Wang, An Analytical Placer for Mixed-Size Placement and Timing-Driven Placement, In Proc. IEEE/ACM International Conference on Computer-Aided Design, pp. 565-572, 2004.
[15] Y.-C. Chou and Y.-L. Lin, A Performance-Driven Standard Cell Placer Based on a Modified Force-Directed Algorithm, In Proc. International Symposium on Physical Design, pp. 24-29, 2001.
[16] G. Karypis and V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, In SIMA Journal on Scientific Computing, Vol.20, No.1, pp. 359-392, 1999
[17] G. Karypis, V. Kumar and S. Shekhar, Multilevel Hypergraph Partitioning: Application in VLSI DomainIn Proc. ACM/IEEE Design Automation Conference, pp. 526-529, 1997
[18] K. M. Hall, A r-dimensional quadratic placement algorithm, In Management Science, pp. 219-229, 1970
[19] D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press, 1982
[20] M. S. Bazaraa, H. D. Sherali and C. M. Shetty, Nonlinear Programming - Theory and Algorithms, 2nd Edition, John Wiley & Sons, 1993
[21] S. N. Adya, S. Chaturvedi, A. Roy, D. Papa and I. L. Markov, Unification of Partitioning, Floorplanning and Placement, In Proc. IEEE/ACM International Conference on Computer-Aided Design, pp. 550-557, 2004
(URL: http://vlsicad.eecs.umich.edu/BK/ICCAD04bench/)
[22] A. B. Kahng, S. Reda and Qinke Wang, Architecture and Details of a High Quality, Large-Scale Analytical Placer, In Proc. IEEE/ACM International Conference on Computer-Aided Design, pp. 890-897, 2005
[23] Y.-C. Chang, Y.-W. Chang, G.-M. Wu and S.-W. Wu, B*-Trees: A New Representation for Non-Slicing Floorplans, In Proc. IEEE/ACM Design Automation Conference, pp.458-463, 2000