隨著半導體產業製程技術的不斷演進，系統級單晶片(System-on-Chip)中通常都會包含數百萬的標準邏輯閘與數百個模組(Macro)，除此之外，一顆晶片中經常包含預先擺置模組，使得晶片中可擺置的區域變成不規則的形狀，這使得混合式擺置(Mixed-Size Placement)的問題複雜度大幅提高。本篇論文主要針對電路中具有相同型態其彼此間具有高度連線的模組，進行規律性的擺置，來減輕實體設計中的電源規劃的困難度，並且提高繞線的可繞度。
本研究中提出了一個以可繞度為導向且能考量巨集電路規律性之擺置樣板器，此方法常被用於三階段的混合式擺置架構。我們的方法可以分為兩個階段，首先在預先粗化階段先分別針對模組與標準邏輯閘進行粗化並同時考量模組規律性，接著在全域散佈後進行後續處理，用以避免模組叢集內的繞線溢位與增加合法化模組的可能性。本論文會將結果與現今的商業軟體銜接，透過電子設計自動化軟體(IC Compiler)進行標準邏輯閘的擺置與繞線，以得到確切的總繞線長度與繞線擁擠度，實驗結果證明，考慮規律性模組擺放確實可以減少總體繞線長度及繞線溢位。

As advance of process technologies and widely reuse of intellectual property (IP), a system-on-chip (SoC) design usually contains a large amount of standard cells and several hundred of macros. Due to large difference in size between a standard cell and a macro and various design consideration, mixed-size placement still remains a quite difficult problem. The paper introduces a routability-driven placement prototyping algorithm for hierarchical mixed-size circuits and pays special attention to regular placement of macros. The three-stage approach is the most popular mix-cell placement algorithm and can best fit into existing commercial design flows, where placement prototyping is the most important stage and locations of macros and standard cells are affected by the result. In addition to normal cells and macros, there exist sets of macros which have identical shapes and similar hierarchy in modern designs. Placement of these macros regularity can facilitate powerplanning and induce better routability. Experimental results have demonstrated effectiveness of our approach in industry benchmarks and actual design flow.

[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.