資料路徑是現代高性能電路設計中最重要的部分之一。但是，大多數現有的研究都是以高度規律性和緊密的方式來擺置以資料路徑為導向的元件（datapath-oriented objects）。然而，很少有研究在擺置樣板（placement prototyping）時考慮此議題。因此，本論文根據資料流圖（dataflow graph）提出了一個用於混合尺寸設計的擺置樣板方法，以便將以資料路徑為導向的元件散佈到正確的方向，使得後續階段能夠較輕易地將它們合法化。此外，由於擺置樣板有較高的複雜度和多個目標需同時考量，即使採用多階層架構（multilevel framework），仍然會相當耗時。因此，本論文也提出了一個快速的多階層架構來進一步提高擺置時的效率。實驗結果證明，本論文提出的方法可以在線長、可繞度和時序違反（timing violation）等方面取得更好的表現。

Datapath is one of the most important components in modern high-performance circuit de-signs. But most of the existing works target on placing datapath-oriented objects with high regularity and compactness. However, seldom research considers this problem during placement prototyping. Hence, this paper proposes a placement prototyping algorithm for a mixed-size cell design according to dataflow graphs in order to distribute the datapath-oriented objects to the correct directions such that they can be easily legalized in the later stage. Due to larger complexity and various objectives, placement prototyping be-comes more time-consuming even with the multilevel framework. Hence, we propose a fast multilevel framework to further improve its efficiency and effectiveness. The experimental results show that our methodology can achieve better performance in terms of wirelength, routability and timing violation.

[1] C. Alpert, A. Kahng, G.-J. Nam, S. Reda, and P. Villarrubia, “A semi-persistent clus-tering technique for VLSI circuit placement,” in Proc. of ACM International Sympo-sium on Physical Design (ISPD), pp. 200–207, 2005.
[2] Y. Cheon and D. F. Wong, “Design hierarchy-guided multilevel circuit partitioning,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 22, no. 4, pp. 420–427, 2003.
[3] T.-C. Chen, Y.-W. Chang, and S.-C. Lin, “IMF: interconnect-driven multilevel floor-planning for large-scale building-module designs,” in Proc. of IEEE/ACM Internation-al Conference on Computer Aided Design (ICCAD), pp. 159–164, 2005.
[4] 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 (TCAD), vol. 27, no. 7, pp. 1228–1240, July 2008.
[5] 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 (TCAD), vol. 27, no. 9, pp. 1621–1634, September 2008.
[6] Y.-L. Chuang, G.-J. Nam, C. J. Alpert, Y.-W. Chang, J. Roy, and N. Viswanathan, “Design-hierarchy aware mixed-size placement for routability optimization,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), San Jo-se, CA, USA, pp. 663–668, 2010.
[7] S. Chou, M.-K. Hsu, and Y.-W. Chang, “Structure-Aware Placement for Datapath-Intensive Circuit Designs,” in Proc. of ACM/IEEE Design Automation Con-ference (DAC), July 2012.
[8] Y.-F. Chen, C.-C. Huang, C.-H. Chiou, Y.-W. Chang, and C.-J. Wang, “Routabil-ity-driven blockage-aware macro placement,” in Proc. of ACM/IEEE Design Automa-tion Conference (DAC), pp. 1–6, 2014.
[9] M.-K. Hsu and Y.-W. Chang, “Unified analytical global placement for large-scale mixed-size circuit designs,” IEEE Transactions on Computer-Aided Design of Inte-grated Circuits and Systems (TCAD), vol. 31, no. 9, pp. 1366–1378, September 2012.
[10] 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 Transactions on Computer-Aided Design of Inte-grated Circuits and Systems (TCAD), vol. 33, no. 12, pp. 1914–1927, 2014.
[11] C. C. Huang, B.-Q. Lin, H.-Y. Lee, Y.-W. Chang, K. S. Wu, and J.-Z. Yang, “Graph-based logic bit slicing for datapath-aware placement,” in Proc. of ACM/IEEE Design Automation Conference (DAC), June 2017.
[12] G. Karypis and V. Kumar, “Multilevel k-way hypergraph partitioning,” in Proc. of ACM/IEEE Design Automation Conference (DAC), pp. 343–348, 1999.
[13] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, “Multilevel hypergraph parti-tioning: applications in VLSI domain,” IEEE Transactions on Very Large Scale Inte-gration Systems (TVLSI), vol. 7, no. 1, pp. 69–79, March 1999.
[14] A.B. Kahng and Q. Wang, “Implementation and extensibility of an analytic placer,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 24, no. 5, pp. 734–747, May 2005.
[15] J.-M. Lin, Y.-L. Deng, S.-T. Li, B.-H. Yu, L.-Y. Chang, and T.-W. Peng,“Regularity-aware routability-driven macro placement methodology for mixed-size circuits with obstacles,” IEEE Transactions on Very Large Scale Integration Systems (TVLSI), 2018.
[16] J.-M. Lin, S.-T. Li and Y.-T. Wang, “Routability-driven Mixed-size Placement Proto-typing Approach Considering Design Hierarchy and Indirect Connectivity Between Macros,” in Proc. of ACM/IEEE Design Automation Conference (DAC), 2019.
[17] J.-M. Lin, Y.-L. Deng, Y.-C. Yang, J.-J. Chen, and Y.-C. Chen, “A Novel Macro Placement Approach based on Simulated Evolution Algorithm,” in Proc. of IEEE/ACM International Conference on Computer Aided Design (ICCAD), 2019.
[18] 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 B1, December 16, 1998.
[19] A. Vidal-Obiols, J. Cortadella, J. Petit, M. Galceran-Oms, F. Martorell, “RTL-Aware Dataflow-Driven Macro Placement,” in Proc. of IEEE/ACM Design Automation and Test in Europe Conference (DATE), March 2019.
[20] S. I. Ward, M.-C. Kim, N. Viswanathan, Z. Li, C. Alpert, E. E. Swartzlander, Jr., and D. Z. Pan, “Keep it straight: teaching placement how to better handle designs with datapaths,” in Proc. of ACM International Symposium on Physical Design (ISPD), pp.79–86, March 2012.
[21] S. I. Ward, M.-C. Kim, N. Viswanathan, Z. Li, C. J. Alpert, E. E. Swartzlander, and D. Z. Pan, “ Structure-Aware Placement Techniques for Designs With Datapaths,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD), vol. 32, no. 2, pp. 228–241, February 2013.
[22] Himax Technologies, Inc. About Himax. Accessed: October 13, 2019. [Online]. Available: https://www.himax.com.tw/company/about-himax/
[23] Synopsys, Inc. IC Compiler. Accessed: September 30, 2019. [Online]. Available: https://www.synopsys.com/implementation-andsignoff/physical-implementation/ic-compiler.html