因為系統單晶片(System-on-Chip, SOC)越來越普遍，使得平面規劃持續成為實體設計中最重要的階段。在目前實體設計流程中，固定框架之平面規劃(fixed-outline floorplanning)越來越受到重視。固定框架之平面規劃的目標是將所有的電路模組擺置在晶片之固定框架，並且去最佳化一些既定的目標例如面積、效能、熱散逸等。在這本碩士論文之中，我們結合數學分析和遞延合併演算法來發展一個固定框架之平面規劃器，我們稱它為CAD。我們的平面規劃演算法可分成兩個階段：第一階段為全域分佈階段，第二階段為區域合理化階段。在全域分佈階段，我們必須將模組均勻地分散在指定區域內，並且使繞線長度最短。我們使用數學分析方法，它需要使用兩種技巧，包含S-LSE線長模型去估量線長，和鐘型位能函數去量測每個子區域的模組佔有率。在第一階段之後，所有模組會平均地分佈在給定的區域，並且整體繞線長度能達到最短。然而，模組之間仍存在一些互相重疊區域。因此在區域合理化階段，我們必須決定各模組精確的位置和形狀，使得兩兩模組間沒有任何重疊，而且使得所有模組都可以擺放在固定的區域內。為了使用遞延合併調整技巧，我們提出一個根據全域分佈的結果去建立分割樹。我們之它為退化之廣義化之分割樹，簡稱DGST。在我們的方法裡，大部分模組之間的關係，都直接根據全域分佈的結果。實驗結果顯示我們的方法是有效的且有效率的。我們也得到比現有文獻更好的結果。

Due to the prevailing of System-on-Chip (SOC), floorplanning continues to be one of the most important stage in the physical design flow. In current physical design flow, fixed-outline floorplanning has attracted more attention for the real requirement. The objective of fixed-outline floorplanning is to place modules of a circuit into a fixed-outline such that some predefined cost metric can be satisfied such as wirelength, timing, thermal dissipation, etc. In this thesis, we develop a fixed-outline floorplanner by combining an analytical based approach with the deferred-merge sizing algorithms, named CAD. Our floorplanning algorithm can be divided into two stages, which are global distribution stage and legalization stage. In the global distribution stage, we uniformly spread modules among a specified region and simultaneously minimize wirelength. Our analytical based approach use two kinds of techniques, including stable-log-sum-exp (S-LSE) wirelength model to estimate wirelength and the bell-shaped potential function to measure the utilization of modules in each subregion. After the first stage, modules have to be distributed over a specified region uniformly and total wirelength is minimized. However, there still exist some overlaps between modules. Thus, the exact locations and shapes of modules have to be determined such that no two modules overlap and all modules are placed inside the outline in the legalization stage. In order to apply deferred-merge sizing technique, we propose to build a slicing tree according to the global distribution results. We call it degraded generalized slicing tree, short by DGST. Most of relations between modules in our method can be determined directly according to the global distribution results. The experimental results have demonstrated the efficiency and effective of our approach. Our results can get better results than the-state-of-art floorplanners.

[1] S. N. Adya, S. Chaturvedi, J. A. Roy, D. A. Papa, I. L. Markov, “Unification of partitioning, placement and floorplanning,” in Proc. of IEEE/ACM Int. Conf. Computer-Aided Design, pp. 550-557, 2004.
[2] S. N. Adya, and I. L. Markov, “Fixed-outline Floorplanning Through Better Local Search,” in Proc. IEEE Int. Conf. Computer Design, Austin, TX, pp. 328-334, 2001.
[3] S. N. Adya, and I. L. Markov, “Fixed-Outline Floorplanning: Enabling Hierarchical Design,” IEEE Trans. on Very Large Scale Integr. Syst., Vol. 11, No. 6, pp. 1120-1135, Dec. 2003.
[4] T. Chan, J. Cong, T. Kong, J. Shinnerl, “Multilevel optimization for large-scale circuit placement,” in Proc. of IEEE/ACM Int. Conf. Computer-Aided Design, pp. 171-176, 2000.
[5] T. Chan, J. Cong, and K. Sze, “Multilevel generalized force-directed method for circuit placement,” in Proc. ACM Int. Symp. Phys. Design, pp. 185-192, 2005. Best paper award at ISPD 2005.
[6] T. Chan, J. Cong, J. Shinnerl, K. Sze, and M. Xie, “mPL6: Enabled multilevel mixed-size placement,” in Proc. ACM Int. Symp. Phys. Design, pp. 212-214, 2006.
[7] Y. C. Chang, Y. W. Chang, G. Wu, and S. Wu, “B*-trees: A new representation for non-slicing floorplans,” in Proc. Design Automation Conference (DAC), pp. 458-463, 2000.
[8] T.-C. Chen, Y.-W. Chang, S.-C. Lin, “IMF: Interconnect-Driven Multilevel Floorplanning for Large-Scale Building-Module Designs,” in Proc. of IEEE/ACM Int. Conf. Computer-Aided Design, 2005.
[9] T.-C. Chen, Y.-W. Chang, “Modern Floorplanning Based on B*-Tree and Fast Simulated Annealing,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 25, No. 4, April 2006.
[10] T.-C. Chen, Y.-W. Chang, S.-C. Lin, “A New Multilevel Framework for Large-Scale Interconnect-Driven Floorplanning,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, No. 2, pp. 286-294, February 2008.
[11] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang, “NTUplace3: An Analytical Placer for Large-Scale Mixed-Size Designs with Preplaced Blocks and Density Constraints,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 27, No. 7, pp. 1228-1240, July 2008.
[12] J. Cong, M. Romesis, and J. Shinnerl, “Fast floorplanning by look ahead enabled recursive bipartitioning,” IEEE Trans. Computer-Aided Design Integrated Circuits and Systems, Vol. 25, No. 9, pp. 1719-1732, Sep. 2006.
[13] J. Edmonds, “Paths, trees, and flowers”, Canadian Journal of Mathematics, 1965.
[14] H. Eisenmann and F. M. Johannes, “Generic global placement and floorplanning,” in Proc. IEEE/ACM Design Automation Conference (DAC), pp. 269-274, 1998.
[15] D. Hill, “Method and System for High Speed Detailed Placement of Cells withnin an Integrated Circuit Design,” U.S. Patent 6 370 673, Apr. 9, 2002.
[16] Meng-Kai Hsu, Yao-Wen Chang, and Valeriy Balabanov, “TSV-Aware Analytical Placement for 3D IC Designs”, in Proc.of IEEE/ACM Design Automation Conference (DAC), June 2011.
[17] B. Hu, and M. Marek-Sadowska, “Fine granularity clustering for large scale placement problems,” in Proc. ACM Int. Symp. Phys. Design, pp. 67-74, 2003.
[18] B. Hu, and M. Marek-Sadowska, “Multilevel fixed-point-addition-based VLSI placement,” IEEE Trans. Computer-Aided Design Integrated Circuits and Systems, Vol. 24, No. 8, pp. 1188-1203, Aug. 2005.
[19] L. Jin, D. Kim, L. Mu, D.-S. Kim and S.-M. Hu, “A sweepline algorithm for Euclidean Voronoi diagram of circuits,” Elsevier Computer-Aided Design, Vol. 38, pp. 260-272, 2006.
[20] A. B. Kahng, “Classical Floorplanning Harmful?,” in Proc. ACM Int. Symp. Phys. Design, 2000.
[21] A. B. Kahng, S. Reda, and Q. Wang, “APlace: A general analytical placement framework,” in Proc. ACM Int. Symp. Phys. Design, pp. 233-235, 2005.
[22] A. B. Kahng, S. Reda, and Q. Wang, “Architecture and details of a high quality, largescale analytical placer,” in Proc. of IEEE/ACM Int. Conf. Computer-Aided Design, pp. 890-897, 2005.
[23] A. B. Kahng and Q.Wang, “Implementation and extensibility of an analytic placer,” IEEE Trans. Computer-Aided Design Integrated Circuits and Systems, Vol. 24, No. 5, pp. 734-747, May 2005.
[24] A. B. Kahng and Q.Wang, “A faster implementation of APlace,” in Proc. ACM Int. Symp. Phys. Design, 2006, pp. 218-220.
[25] G. Karypis, R. Aggarwal, V. Kumar, and Shashi Shekhar, “Multilevel Hypergraph Partitioning: Applications in VLSI Domain”, IEEE Trans. on Very Large Scale Integr. Syst., Vol. 7, No. 1, Mar. 1999.
[26] M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich, “GORDIAN: VLSI placement by quadratic programming and slicing optimization,” IEEE Trans. Computer-Aided Design Integrated Circuits and Systems, Vol. 10, No. 3, pp. 356-365, Mar. 1991.
[27] M. Kuwano, and Y. Takashima, “Stable-LSE based Analytical Placement with Overlap Removable Length,” in Proc. Synthesis and System Integration of Mixed Information Technologies (SASIMI), 2010. Best Paper Award.
[28] J.-M. Lin and Y.-W. Chang, “TCG: A transitive closure graph-based representation for non-slicing floorplans,” in Proc. IEEE/ACM Design Automation Conference (DAC), pp. 764-769, 2001.
[29] J.-M. Lin and H. Hung, “UFO: Unified Convex Optimization Algorithms for Fixed-Outline Floorplanning,” in Proc. of IEEE/ACM Asia South Pacific Design Automation Conference, 2010.
[30] Chaomin Luo, Miguel F. Anjos, Anthony Vannelli, “Large-Scale Fixed-Outline Floorplanning Design Using Convex Optimization Techniques,” in Proc. of IEEE/ACM Asia South Pacific Design Automation Conference, 2008.
[31] K. Mehlhorn, and S. Naher, “LEDA, a platform for combinatorial and geometric computing,” Cambridge Press, 1999.
[32] Minghorng Lai and D. F. Wong, “Slicing Tree Is a Complete Floorplan Representation,” in Proc. of Design, Automation and Test in Europe Conference, 2001.
[33] H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani, “Rectangle-packing-based module placement,” in Proc. Int. Conf. Computer-Aided Design, pp. 472-479, 1995.
[34] G.-J. Nam, S. Reda, C. J. Alpert, P. G. Villarrubia, and A. B. Kahng, “A fast hierarchical quadratic placement algorithm,” IEEE Trans. Computer-Aided Design Integrated Circuits and Systems, Vol. 25, No. 4, pp. 678-691, Apr. 2006.
[35] W. C. Naylor, R. Donelly, and L. Sha, “Non-linear optimization system and method for wire length and delay optimization for an automatic electric placer,” U.S. Patent 6 301 693, Oct. 9, 2001.
[36] R. H. J. M. Otten, “Automatic Floorplan Design,” Proc. of IEEE/ACM Design Automation Conference (DAC),” pp. 261-267, 1982.
[37] P. G. Sassone and S. K. Lim, “A Novel Geometric Algorithm for Fast Wire-Optimized Floorplanning,” in Proc. Int. Conf. Computer-Aided Design, pp. 74-80, 2003.
[38] L. Stockmeyer, “Optimal orientations of cells in slicing floorplan designs,” Informat. Control, Vol. 57, pp. 91-101, May-Jun. 1983.
[39] G.-J. Nam, S. Reda, C. J. Alpert, P. G. Villarrubia, and A. B. Kahng, “A fast hierarchical quadratic placement algorithm,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 25, No. 4, pp. 678-691, April 2006.
[40] Natarajan Viswanathan, Min Pan, and Chris Chu, “FastPlace 3.0: A Fast Multilevel Quadratic Placement Algorithm with Place Congestion Control,” in Proc.of IEEE/ACM Asia South Pacific Design Automation Conference, pp. 135-140, 2007.
[41] Jackey Z. Yan and Chris Chu, “DeFer: Deferred Decision Making Enabled Fixed-Outline Floorplanning Algorithm,” IEEE Trans. Computer-Aided Design of Integrated Circuits and Systems, Vol. 29, No. 3, pp. 119-130, March 2010.
[42] Jackey Z. Yan, Chris Chu, and Wai-Kei Mak, “SafeChoice: A Novel Clustering Algorithm for Wirelength-Dirven Placement,” in Proc. ACM Int. Symp. Phys. Design, 2010.
[43] Jackey Z. Yan, Chris Chu, and Wai-Kei Mak, “SafeChoice: A Novel Approach to Hypergraph Clustering for Wirelength-Driven Placement,” IEEE Trans. Computer-Aided Design of Integrated Circuits and System, Vol. 30, No. 7, pp. 1020-1033, July, 2011.
[44] J. A. Roy, S. N. Adya, D. A. Papa, and I. L. Markov, “Min-cut floorplacement,” IEEE Trans. Computer-Aided Design of Integraed Circuits and System, Vol. 25, No. 7, pp. 1313-1326, July, 2006.
[45] Linfu Xiao, Subarna Sinha, Jingyu Xu, Evangeline F.Y. Young, “Fixed-outline Thermalaware 3D Floorplanning,” in Proc. of IEEE/ACM Asia South Pacific Design Automation Conference, 2010.
[46] G. Zimmerman, “A new area and shape function estimation technique for very large scale integration layouts,” in Proc. of IEEE/ACM Int. Conf. Computer-Aided Design, pp. 60-65, 1988.