隨著製程技術的不斷進步，單一晶片中所包含的電晶體數越來越多，為了降低其設計的複雜度，經常使用矽智財(Intellectual Property)電路，現今的系統級單晶片(System-on-Chip)經常有些矽智財電路，其中包含類比模組、嵌入式記憶體等，甚至現今的晶片中常有些預擺置的模組(Macro)，這些模組的位置已經固定在晶片中，使得原本晶片的可擺置的範圍變成了不規則的形狀，此外擺置(Placement)的問題存在著預擺置模組和大型模組，大幅提高混合尺寸擺置的複雜度。
過去的文獻中針對混合型晶片針對模組擺置並沒有一個快速且有效的方法，因此本篇論文中使用三階段的擺置方式，其中包括：全域擺置雛形、模組電路擺置、標準邏輯閘擺置，最後再由電子設計自動化軟體(IC Compiler)進行繞線，得到確切的總繞線長度。執行全域擺置前，為了降低設計的複雜度，簡化下階段全域擺置的計算，採用粗化(Coarsening)的技巧，使全域減少擺置元件的數量；全域擺置時使用數學最佳化的分析方式將所有的模塊均勻地散佈出去，並且散佈的同時考慮總線長、預擺置的模組、可繞度；接著模組擺置使用遞迴切割的技巧將模組更均勻的分散到晶片四周；最後合法化模組時採用列舉包裝法(Enumerative Packing)和模擬退火法(Simulate Anneal)找到模組確切的位置，將擺置結果由電子設計自動化軟體進行標準邏輯閘擺置和繞線。實驗結果證實，我們的演算法不但能夠快速且有效的決定模組位置，且能接近實際業界的擺置結果。

Due to advance in manufacture technology, a modern system-on-a-chip (SoC) usually contains more than billions of transistors. Some macros need to be placed at specified positions and orientations because of special requirement of a modern chip. Thus, a modern chip becomes more complicated. From the past, the literatures show that the macros can occupy more than 70% of a chip area. It is more important for placing macros to better positions in a modern chip. Therefore, this thesis adopts three-stage placement method including placement prototyping, macro placement and standard-cell placement. In order to reduce the complexity of design, we cluster standard cells to reduce the number of movable blocks. In placement prototyping stage, we use an analytical approach to spread gradually and consider wirelength, preplaced blocks, routability, and density. Based on result of global distribution, we use partition based approach to advanced spread macros to boundary of chip and expand soft blocks which are located at high congestion regions. Finally, we will legalize each macro in a sub-region. We compare our method with CP-tree and manual macro placement results provided by industry based on test cases provided by Himax. Experimental results demonstrate that our approach is close to the actual result placement and lower congestion.

[1]. Y.-C. Chang, Y.-W. Chang, G.-M. Wu, and S.-W. Wu, “B*-Trees: A new representation for non-slicing floorplans,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 458-463, 2000.
[2]. C. Chu, “FLUTE: Fast Lookup Table Based Wirelength Estimation Technique,” In Proceedings of International Conference on Computer Aided Design, pp. 696-701, 2004.
[3]. C. Chu and Y.-C. Wong, “Fast and Accurate Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” In Proceedings of International Symposium on Physical Design, pp. 28-35, 2005.
[4]. T. Chan, J. Cong, J. Shinnerl, K. Sze, and M. Xie, “mPL6: Enhanced multilevel mixed-size placement,” in Proceedings ACM International Symposium on Physical Design, pp. 212–214, 2006.
[5]. 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 pre-placed blocks and density constraints,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 7, pp. 1228-1240, July 2008.
[6]. T.-C. Chen, P.-H. Yuh, Y.-W. Chang, F.-J. Huang, and T.-Y. Liu, “MP-trees: A packing-based macro placement algorithm for modern mixed-size designs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27,no. 9, pp. 1621-1634, September 2008.
[7]. C. Chu and Y.-C. Wong, “FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 27, no. 1, pp.70-83, January 2008.
[8]. K.-C. Chan, J.-M. Lin, C.-J Hsu, “A flexible fixed-outline floorplanning methodology for mixed-size modules,” in Proceedings of ASP-DAC, pp. 435-440, January 2013.
[9]. Y.-F. Chen, C.-C. Huang, C.-H. Chiou, Y.-W. Chang, and C.-J. Wang, “Routability-driven blockage-aware macro placement,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 1-6, 2014.
[10]. C.M. Fiduccia and R.M. Mattheyses, “A Linear-Time Heuristic for Improving Network Partitions,” In Proceedings of ACM/IEEE Design Automation Conference, pp. 175-181, 1982.
[11]. B.S. Goh, Feng Ye, Shuisheng Zhou, “Steepest descent algorithms in optimization with good convergence properties,” Control and Decision Conference, pp. 1526-1530, July 2008.
[12]. M. R. Hestenes, E. Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems,” Journal of Research of the National Bureau of Standards, vol. 49, no. 6, pp. 409-436, December 1952.
[13]. J. Hao and J. Orlin, “A faster algorithm for finding the minimum cut in a directed graph,” Journal of Algorithms, vol. 17, no. 3, pp. 424–446, 1994.
[14]. S. Kirkpatrick, C. D. Gelatt, and M. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671-680, May 1983.
[15]. A. B. Kahng and Q. Wang, “Implementation and extensibility of an analytic placer,” IEEE Transactions Computer-Aided Design Integrated Circuits and Systems, vol. 24, no. 5, pp. 734–747, May 2005.
[16]. M.-C. Kim, J. Hu, D.-J. Lee, and I. L. Markov, “A SimPLR method for routability-driven placement,” in Proceedings of ICCAD, pp. 67–73, 2011.
[17]. M.-C. Kim, D.-J. Lee, and I. L. Markov, “SimPL: An effective placement algorithm,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 31, no. 1, pp. 50-60, January 2012.
[18]. C. Li, M. Xie, C. -K. Koh, J. Cong, and P. H. Madden, “Routability-driven Placement And White Space Allocation,” in Proceedings of ICCAD, pp. 394-401, 2004.
[19]. W. C. Naylor, R. Donelly, and L. Sha, “Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer,” U.S. Patent 6 301 693, October 2001.
[20]. A. Pazderin, S. Yuferev, “Power flow calculation by combination of Newton-Raphson method and Newton's method in optimization,” Industrial Electronics, pp. 1693-1696, November 2009.
[21]. J. A. Roy, N. Viswanathan, G.-J. Nam, C. J. Alpert, and I. L. Markov, “CRISP: Congestion Reduction By Iterated Spreading During Placement,” in Proceedings of ICCAD, pp. 357–362, November 2009.
[22]. E. Wein and J. Benkoski, “Hard macros will revolutionize SoC design,” EE Times Online, August 2004.
[23]. X. Yang, B.-K. Choi, and M. Sarrafradeh, “Routability-Driven White Space Allocation For Fixed-Die Standard-Cell Placement,” IEEE Transactions Computer-Aided Design Integrated Circuits and Systems, vol. 22, no. 4, pp. 410-419, April 2003.
[24]. J. Z. Yan, N. Viswanathan, and C. Chu, “Handling complexities in modern large-scale mixed-size placement,” in Proceedings of ACM/IEEE Design Automation Conference, pp. 436-441, 2009.
[25]. J. Z. Yan and C. Chu, “DeFer: DeFered Decision Making Enable Fixed-outline Floorplanning Algorithm,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, no. 3, pp. 119-130, 2010.