隨著半導體產業製程技術的不斷演進，系統級單晶片(System-on-Chip)中通常都會包含數百萬的標準邏輯閘與數百個模塊(Macro)，除此之外，晶片中經常包含預先擺置模塊，使得晶片中可擺置的區域變成不規則的形狀，這使得混合式擺置(Mixed-Size Placement)的問題複雜度大幅提高。在先前的模塊擺置的研究中，考量模塊擺置的規律性將電路中具有相同型態其彼此間具有高度連線的模塊，進行叢集及規律性的擺置，但此方法會導致某些叢集模塊面積過大而導致降低可繞度，因此本論文提出了一個叢集拆解的方式，考慮模塊間與物件連線的關係進行拆解，使用此方法提升可繞度。
本研究中提出了一個以可繞度為導向並且藉由叢集拆解方法，此方法用於三階段的混合式擺置架構。我們的方法首先在初步擺置的電路中進行電路的切割，將電路切割成數個平均的子區域，接著在子區域中對模塊和標準邏輯閘叢集進行拆解，讓叢集可以被擺置得更緊實，進而去重新散佈所有子區域得到新的全域散布的結果。本論文會將結果與現今的商業軟體銜接，透過電子設計自動化軟體(IC Compiler)進行標準邏輯閘的擺置與繞線，以得到確切的總繞線長度與繞線擁擠度，實驗結果證明，進行模塊的拆解確實可以減少總體繞線長度及繞線溢位。

As advance of manufacturing technology, a modern chip contain more and more macros. How to effectively handle several hundred of macro is even difficult problem because of a large design complexity and several pre-placed macros. The three-stage mixed-size placement approach is the most suitable for a commercial design which includes placement prototyping, macro placement and standard cell placement. The placement prototyping is the most important step because its result will determine the distribution of macros, and the locations of macros directly influence standard cell placement. SOC circuits usually contain sets of macros which have identical shapes and are in similar hierarchies. If these macros can be placed regularity, poweplanning will become easier and better routability may be obtained. Though previous work[32] can find the similar hierarchical macro and cluster them together, the area of macro clusters is too larger to degrade the placement quality. This paper introduces a routability-driven macro prototyping and pays special attention to the area of macro clusters. Decompose over larger clusters not only can improve the quality of global distribution but also decrease difficulty in legalization. Experimental results demonstrate that our approach can improve the wirelength and routability 11.74 and 11% in industry benchmarks.

[1]. S. R. Arikati and R. Varadarajan. “A signature based approach to regularity extraction.” In Proc. ICCAD, pages 542 - 545, 1997.
[2]. C. J. Alpert, D. Huang, and A. B. Kahng. “Multilevel circuit partitioning”. IEEE Trans. Computer-Aided Design, Vol. 17, No. 8, pages 655 - 667, Aug 1998.
[3]. C. Alpert, A. Kahng, G.-J. Nam, S. Reda, and P. Villarrubia. “A semi-persistent clustering technique for VLSI circuit placement.” In Proc. ISPD, pages 200–207, 2005.
[4]. K. Athikulwongse, A. Chakraborty, J.-S. Yang, W. Hou, D. Z. Pan, and S. K. Lim. “Stress-driven 3D-IC placement with TSV keep-out zone and regularity study.” In Proc. ICCAD, pages 669–674, 2010.
[5]. C. Chu. “FLUTE: fast lookup table based wirelength estimation technique.” In Proc. ICCAD, pages 696 - 701, 2004.
[6]. J. Cong and S. Lim. “Edge separability-based circuit clustering with application to multilevel circuit partitioning.” IEEE Trans. Computer-Aided Design, Vol. 23, No. 3, pages 346–357, 2004.
[7]. 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 Trans on TCAD, Vol. 27, No.9. 7, pages 1228-1240, July 2008.
[8]. 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 Trans. on TCAD, Vol. 27, No. 9. 7, pages 1621 - 1634, September 2008.
[9]. Y.-L. Chuang, G.-J. Nam, C. J. Alpert, Y.-W. Chang, J. A. Roy, N. Viswanathan. “Design-hierarchy Aware Mixed-size Placement for Routability Optimization.” In Proc. ICCAD, pages 663-668, 2010.
[10]. P.-Y. Chou, H.-C. Ou and Y.-W. Chang. Micheli. “Heterogeneous B*-trees for analog placement with symmetry and regularity considerations.” In Proc. ICCAD, pages 512–516, 2011.
[11]. Y.-F. Chen, C.-C. Huang, C.-H. Chiou, Y.-W. Chang, C.-J. Wang. “Routability-Driven Blockage-Aware Macro Placement.” In Proc. DAC, pages 1 - 6, 2014.
[12]. S. Chatterjee, V. S. Saun, and A. Arunachalam. “A Methodology for Placement of Regular and Structured Circuits.” In Proc. VLSID, pages 499–504, 2015.
[13]. G. G. Faust, R. Zhang, K. Skadron, M. R. Stan, and B. H. Meyer. “ArchFP: rapid prototyping of pre-RTL floorplans.” In Proc. VLSI-SoC, pages 183-188, 2012.
[14]. G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. “Multilevel hypergraph partitioning: Application in VLSI domain.” In Proc. DAC, pages 526–529, 1997.
[15]. G. Karypis and V. Kumar. “Multilevel k-way hypergraph partitioning.” In Proc. DAC, pages 343–348, 1999.
[16]. B. Hu and M. Marek-Sadowska. “Fine granularity clustering for large scale placement problems.” In Proc. ISPD, pages 67–74, 2003.
[17]. M.-K. Hsu and Y.-W. Chang. “Unified analytical global placement for large-scale mixed-size circuit designs.” IEEE Trans. Computer-Aided Design, Vol. 31, No. 9, pages 1366 - 1378, September 2012.
[18]. M.-K. Hsu, Y.-F. Chen, C.-C. Huang, S. Chou, T.-H. Lin, T.-C. Chen, and Y.-W. Chang. “NTUplace4h: A novel routability-driven placement algorithm for hierarchical mixed-size circuit designs.” IEEE Trans. Computer-Aided Design, Vol. 33, No. 12, pages. 1914 - 1927, December 2014.
[19]. W. K. Luk and A. A. Dean. “Multistack optimization for datapath chip layout.” In Proc. DAC, pages 110 - 115, 1989.
[20]. R. X. T. Nijssen and C. A. J. van Eijk. “Regular layout generation of logically optimized datapaths.” In Proc. ISPD, pages 42 - 47, April. 1997.
[21]. S. Nakatake. “Structured Placement with Topological Regularity Evaluation.” In Proc. ASPDAC, pages 215–220, 2007.
[22]. S. Nakatake, M. Kawakita, T. Ito, M. Kojima, M. Kojima, K. Izumi, and T. Habasaki. “Regularity-oriented analog placement with diffusion sharing and well island generation.” In Proc. APSDAC, pages 305–311, 2010.
[23]. J. d. S. Pedro, J. Cortadella, and A. Roca. “A hierarchical approach for generating regular floorplans.” In Proc. ICCAD, pages 655–662, 2014.
[24]. S.I. Ward, D.A. Papa, Z. Li, C.N. Sze, C.J Alpert and E. Swartzlander. “Quantifying academic placer performance on custom designs.” In Proc. ISPD, pages 91 - 98, 2011.
[25]. S.I. Ward, M. Kim, N. Viswanathan, Z. Li, C.J Alpertm, D.Z. Pan and E. Swartzlander, “Keep it straight: teaching placement how to better handle designs with datapaths.” In Proc. ISPD, pages 79 - 86, 2012.
[26]. S.I. Ward, M. Kim, N. Viswanathan, Z. Li, C.J Alpert and E. Swartzlander. “Structure-aware placement for datapath-intensive circuit designs.” IEEE Trans. Computer-Aided Design, Vol. 32, No. 2, pages 228 - 241, Feb. 2013.
[27]. C. Yang, X. Hong, Y. Cai, W. Hou, T. Juig, and W. Wu. “Standard-cell based data-path -placement utilizing regularity.” In Proc. ICASIC, pages 97–100, 2003.
[28]. T. T. Ye and G. D. Micheli. “Data path placement with regularity.” In Proc. ICCAD, pages 264–271, 2000.
[29]. T. T. Ye and G. D. Micheli. “Physical synthesis for ASIC datapath circuits.” In Proc. ISCAS, pages 365 - 368, 2002.
[30]. T. T. Ye and G. D. Micheli. “Physical planning for on-chip multiprocessor networks and switch fabrics.” In Proc. ASAP, pages 97-107, 2003.
[31]. J. Z. Yan, N. Viswanathan, and C. Chu, “Handling complexities in modern large-scale mixed-size placement.” In Proc. DAC, pages. 436-441, 2009.
[32]. J.-M. Lin, B.-H, Yu, L.-Y. Chang. “Regularity-aware routability-driven placement prototyping algorithm for hierarchical mixed-size circuits” In Proc. ASPDAC, page: 438-443, 2017
[33]. B. Hu, M. Marek-Sadowska, “Fine Granularity Clustering-Based Placement” IEEE Trans. Computer-Aided Design, Vol 23, pages 527 – 536, 2004
[34]. J. Li, L. Behjat, J. Huang, “An Effective Clustering Algorithm for Mixed-size Placement” In Proc. ISPD page: 111-118, 2007