臺灣博碩士論文加值系統

積體電路的佈局(floorplan)是電子實體電路設計過程的第一步。它決定電路模組(module)在晶片上擺放的位置，進而影響了晶片面積以及線長。晶片面積反映在晶片的製造成本上，而線長影響效能。因此佈局在實體設計中有其重要性。
自動佈局的演算法多以退火演算法為基礎。這類方法是塞填驅動的(packing-driven)。塞填驅動雖對面積是有利的，但對線長可能是有害的。另一方面，解析方法裡，以二次規劃(quadratic programming)為基礎的演算法，是線長驅動(wirelength-driven)的。在佈局裡，模組空間不重疊是重要的法則。塞填驅動有效的避開了不合法的佈局。然而以二次規劃為基礎的演算法卻不行。且塞填驅動能夠產生擁有較小面積的佈局。但二次規劃能從全局的視野最佳化線長是傳統以退火為基礎的演算法所不及。因此我們定義了拓撲相似性(topology similarity)並提出以相似性驅動(similarity-driven)之兩階段佈局演算法。其第一階段是以二次規劃為基礎的，並以尋找對線長友善的模組間拓撲關係為目標。而第二階段是以退火演算法為基礎，並以第一階段的結果做為其在進行相似性感知(similarity-aware)搜尋時的參考對像。我們藉此控制退火演算法在解析解附近的解空間尋找最佳解。實驗結果顯示，我們的演算法在線長上的收斂更快，同時能得到更短的線長且在面積上沒有顯著的增加。

Floorplanning is in the early stages of VLSI physical design. It determines the locations of modules and significantly governs the chip dimensions and the total wirelength on the chip. Thus it is important in terms of both fabrication cost and chip performance.
Floorplanning based on simulated annealing (SA) is popular. But this approach is packing-driven and may be profitless for the wirelength. On the other hand, the analytical approach by quadratic programming is wirelength-driven. Packing-driven approach has much success in the handling of the non-overlapping constraint and results floorplans with smaller area. But unlike the quadratic programming approach, traditional SA-based methods lack a global view of the interconnections. To eliminate this drawback, we define topology similarity and propose similarity-driven approach. In our approach, SA is guided by an analytical result. Similarity-aware perturbations are proposed to make searches more efficient. Compared to traditional packing-driven approach, experiments show the proposed algorithm produces solutions of shorter wirelength without apparent degradation in area.

摘 要 i
Abstract ii
誌　　謝 iii
Content iv
List of Tables vi
List of Figures vii
Chapter 1 Introduction 1
1.1 Floorplanning 1
1.2 Motivation 4
1.3 Thesis Organization 4
Chapter 2 Preliminaries 5
2.1 Notations 5
2.2 Problem Formulation 5
2.3 Analytical Approach: Quadratic Programming 5
2.4 Stochastic Approach: Sequence Pair 6
2.4.1 Simulated Annealing (SA) 6
2.4.2 Sequence-Pair 9
Chapter 3 Topology Similarity 10
3.1 Definition 10
3.2 Observation 12
3.3 Similarity-Driven Floorplanning 13
Chapter 4 Proposed Algorithm 14
4.1 Overview 14
4.2 Reordering 15
4.3 Similarity-Aware Search 16
4.3.1 Similarity-Constrained Search 16
4.3.2 Similarity Constraint Mapping 17
4.3.3 Precedence Constraint Graph (PCG) 18
4.3.4 Similarity Constraint Relaxation 19
4.3.5 Similarity-Aware Perturbations 21
4.4 Proposed Similarity-Driven Flow 24
Chapter 5 Experimental Results 26
5.1 Experimental Setup 26
5.2 Dynamic Behavior 26
5.3 Effect of Reordering 29
5.4 Effect of presrv Parameter 31
Chapter 6 Conclusion 33
Reference 34

[1] J. Grason, “An approach to computerized space planning using graph theory,” Proc. Design Automation Workshop, pp. 170–178, 1971.
[2] Y.-T. Lai and S. M. Leinwand, “Algorithms for floorplan design via rectangular dualization,” Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 7, no. 12, Dec. 1988.
[3] D. F. Wong and C. L. Liu, “A new algorithm for floorplan design,” Proc. Design Automation Conf., pp. 101–107, 1986.
[4] S. Kirpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, May 13, 1983.
[5] R. H. J. M. Otten, “Automatic floorplan design,” Proc. Design Automation Conf., pp. 261–267, 1982
[6] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Rectangle-packing-based module placement,” Proc. International Conference on Computer-Aided Design, pp. 472–479, 1995.
[7] S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajitani, “Module placement on BSG-structure and IC layout applications,” Proc. International Conference on Computer-Aided Design, pp. 484–491, 1996.
[8] P.-N. Guo, C.-K. Cheng, and T. Yoshimura, “An O-tree representation of non-slicing floorplan and its applications,” Proc. Design Automation Conf., pp.268–273, 1999.
[9] Y. Pang, C.-K. Cheng, and T. Yoshimura, “An enhanced perturbing algorithm for floorplan design using the O-tree representation,” Proc. Int’l Symp. Physical Design, pp. 168–173, 2000.
[10] Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B*-trees: a new representation for non-slicing floorplans,” Proc. Design Automation Conf., pp. 458–463, 2000.
[11] X. Hong, G. Huang, Y. Cai, J. Gu, S. Dong, C. K. Cheng, and J. Gu, “Corner block list: an effective and efficient topological representation of non-slicing floorplan,” Proc. International Conference on Computer-Aided Design, pp. 8–12, 2000.
[12] J.-M. Lin and Y.-M. Chang, “TCG: a transitive closure graph-based representation for non-slicing floorplans,” Proc. Design Automation Conf., pp. 764–769, 2001.
[13] J.-M. Lin and Y.-M. Chang, “TCG-S: orthogonal coupling of P*-admissible representations for general floorplans,” Proc. Design Automation Conf., pp. 842–847, 2002.
[14] K. Sakanushi, Y. Kajitani, and D.P. Mehta, “The quarter-state-sequence floorplan representation,” IEEE Trans. Circuits and Syst.I: Fundamental Theory and Applications, vol. 50, no. 3, pp. 376–386, Mar. 2003.
[15] E. F. Y. Young, C. C. N. Chu, and Z. C. Shen, “Twin binary sequences: a nonredundant representation for general nonslicing floorplan,” IEEE Trans. Comput.-Aided Design Integr. Circuits Syst., vol. 22, no. 4, pp. 457–469.
[16] H. Zhou and J. Wang, “ACG-adjacent constraint graph for general floorplans,” Proc. IEEE International Conference on Computer Design, pp. 572–575, 2004.
[17] J. Wang and H. Zhou, “Exploring adjacency in floorplanning,” Proc. Asia and South Pacific Design Automation Conference, pp. 367–372, 2009.
[18] H. Murata and E. S. Kuh, “Sequence-pair based placement method for hard/soft/pre-placed modules,” Proc. Int’l Symp. Physical Design, pp. 167–172, 1998.
[19] E. F. Y. Young, C. C. N. Chu, and M. L. Ho, “A unified method to handle different kinds of placement constraints in floorplan design,” Proc. Asia and South Pacific Design Automation Conference, pp. 661–670, 2002.
[20] S. N. Adya and I. L. Markov, “Fixed-outline floorplanning: Enabling hierarchical design,” IEEE Trans. Very Large Scale Integr. (VLSI) Syst., vol. 11, no. 6, pp. 1120–1135, Dec. 2003.
[21] X. Tang, R. Tian, and M. D. F. Wong, “Minimizing wire length in floorplanning,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, vol. 25, no. 9, pp. 1744–1753, Sept. 2006.
[22] J.-T. Yan, Z.-W. Chen, Y.-H. Chou, S.-H. Lin, and H. Chiueh, “Thermal-driven white space redistribution for block-level floorplans,” Proc. Int. Conf. on Electronics, Circuits and Systems, pp. 662–665, 2008.
[23] S. Sutanthavibul, E. Shragowitz, and J. B. Rosen, “An analytical approach to floorplan design and optimization,” Proc. Design Automation Conf., pp. 187–192, 1990.
[24] L. Sha and R. W. Dutton, “An analytical algorithm for placement of arbitrarily sized rectangular blocks,” Proc. Design Automation Conf., pp. 602–608, 1985.
[25] Y. Zhan, Y. Feng, and S. S. Sapatnekar, “A fixed-die floorplanning algorithm using an analytical approach,” Proc. Asia and South Pacific Design Automation Conf., pp. 771–776, 2006.
[26] P. Zhou, Y. Ma, Z. Li, R. P. Dick, L. Shang, H. Zhou, X. Hong, and Q. Zhou, “3D-STAF: scalable temperature and leakage aware floorplanning for three-dimensional integrated circuits,” Proc. International Conference on Computer-Aided Design, pp. 590–597, 2007.
[27] A. B. Kahng, “Classical floorplanning harmful?” Proc. Int’l. Symp. on Physical Design, pp. 207–213, 2000.
[28] S. M. Sait and H. Youssef, “Iterative computer algorithms with applications in engineering: solving combinatorial optimization problems,” IEEE Computer Society Press, 1999.
[29] X. Tang, R. Tian, and D. F. Wong, “Fast evaluation of sequence pair in block placement by longest common subsequence computation,” Proc. Design, Automation and Test in Europe Conference and Exhibition, pp. 106–111, 2000.
[30] X. Tang and D. F. Wong, “FAST-SP: a fast algorithm for block placement based on sequence pair,” Proc. Asia and South Pacific Design Automation Conf., pp. 521–526, 2001.