本論文提出了一個適用於混合尺寸電路且能考量資料流導向限制的數學解析擺置演算法。為了在電路設計初期即能夠獲得更好的擺置結果，CAD 工程師 通常會參考設計的資料流來決定元件和模塊的相對位置。為了幫助實現此目標， 本論文提出兩個方法使得擺置結果能夠遵循資料流導向限制。首先，我們對連接到資料路徑為導向的元件(datapath-oriented objects)的線給出更大的權重，接著藉由一個改良的岡伯茲曲線(Gompertz curve)並且根據擺置利用率的狀況逐漸縮小權重的值，在不干擾其它元件散佈的前提下縮短資料路徑為導向的元件間的距離。 其次，我們針對每個資料路徑為導向的元件定義了多個理想擺置區域，如果這些元件不在對應的區域中，在數學解析擺置公式中，會藉由我們所提出一個新穎的乙狀函數(sigmoid function)給出額外的懲罰。此外，我們提出了兩個方法用來動態調整在數學解析擺置公式中擺置密度懲罰項的權重，在不犧牲擺置品質的情況下加速擺置的過程。實驗結果顯示相對其它沒有考量到資料流導向限制的作法，我們的方法可以得到更好的結果。不僅是線長，還有可繞度會在擺置結果中被改善。且外，我們的擺置器亦優於一個暫存器傳輸級感知且以資料流驅動的模塊擺置器(RTL-aware dataflow-driven macro placer)。

This article presents an analytical-based placement algorithm to handle dataflow constraint for mixed-size circuits. To obtain a better placement at an early stage,
engineers often reference dataflow of a design to determine the relative locations of cells and macros. To achieve this target, this thesis presents two methods to make a placement follow this constraint. First, we give larger weights to those nets which connect to datapath-oriented objects in the beginning, and then gradually shrink the values by the modified Gompertz curve according to the status of placement utilization in order to shorten their distances without interfering with object distribution. Second, we define desirable placement regions for each datapath-oriented object and propose a novel sigmoid function to give additional penalties to these objects in the analytical placement formulation if they are not in the regions. More importantly, we propose two procedures to adjust parameters used in the analytical placement formulation to speed up runtime without sacrificing its quality. The experiment demonstrates that our methodology can obtain better results than the other approach which does not consider dataflow constraint. Not only wirelength but also routability will be improved in the resulting placement. Furthermore, our placer outperforms the RTL-aware dataflow-driven macro placer.

[1] C. Alpert, A. Kahng, G.-J. Nam, S. Reda, and P. Villarrubia, “A semi-persistent clustering technique for VLSI circuit placement,” in Proc. of ACM International Symposium on Physical Design (ISPD), pp. 200–207, 2005.
[2] C.-H. Chang, Y.-W. Chang, and T.-C. Chen, “A Novel Damped-wave Framework for Macro Placement,” in Proc. ICCAD, pp. 504-511, 2017.
[3] 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 Tran. of TCAD, vol. 27, no. 7, pp. 1228-1240, 2008
[4] C.-K. Cheng, A. B. Kahng, I. Kang and L. Wang, “RePlAce: Advancing solution quality and routability validation in global placement,” IEEE Tran. of TCAD, vol. 38, no. 9, pp. 1717-1730, 2018.
[5] S. Chou, M.-K. Hsu, and Y.-W. Chang, “Structure-aware placement for datapath-intensive circuit designs,” in Proc. of DAC, pp. 762-767, 2012.
[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 ICCAD, pp. 663-668, 2010.
[7] J. Gu, Z. Jiang, Y. Lin and D. Z. Pan, “DREAMPlace 3.0: MultiElectrostatics Based Robust VLSI Placement with Region Constraints,” in Proc. of ICCAD, pp. 1-9, 2020.
[8] 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 DAC, pp. 1-6, 2017.
[9] C.-C. Huang, H.-Y. Lee, B.-Q. Lin, S.-W. Yang, C.-H. Chang, S.-T. Chen, Y.-W. Chang, T.-C. Chen, and I. Bustany “NTUplace4dr: A Detailed-Routing-Driven Placer for Mixed-Size Circuit Designs With Technology and Region Constraints,” IEEE Tran. of TCAD, vol. 37, no. 3, pp. 669-681, 2018.
[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 Tran. of TCAD, vol. 33, no. 12, pp. 1914-1927, 2014.
[11] A. B. Kahng and Q. Wang, “Implementation and extensibility of an analytic placer,” IEEE Tran. of TCAD, vol. 24, no. 5, pp. 734-747, 2005.
[12] A. B. Kahng and Q. Wang, “A faster implementation of APlace,” in Proc. of ISPD, pp. 218-220, 2006.
[13] W. Li, Y. Lin and D. Z. Pan, “elfPlace: Electrostatics-based Placement for Large-Scale Heterogeneous FPGAs,” in Proc. of ICCAD, pp. 1-8, 2019.
[14] T. Lin, C. Chu, J. R. Shinnerl, I. Bustany, and I. Nedelchev, “POLAR: Placement based on novel rough legalization and refinement,” in Proc. of ICCAD, pp. 357-362, 2013.
[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 Tran. of TVLSI, vol. 27, no. 1, pp. 57-68, 2019.
[16] J.-M. Lin, S.-T. Li, and Y.-T. Wang, “Routability-driven mixed-size placement prototyping approach considering design hierarchy and indirect connectivity between macros,” in Proc. of DAC, pp. 1-6, 2019.
[17] J.-M. Lin, Y.-L. Deng, Y.-C. Yang, J.-J. Chen, and P.-C. Lu, “Dataflowaware macro placement based on simulated evolution algorithm for mixed-size designs,” IEEE Tran. of TVLSI, vol. 29, no. 5, pp. 973-984, 2021.
[18] J. Lu, P. Chen, C.-C. Chang, L. Sha, D. J.-H. Huang, C.-C. Teng, and C.-K. Cheng, “FFTPL: An analytic placement algorithm using fast fourier transform for density equalization,” in Proc. of ASICON, pp. 1- 4, 2013.
[19] J. Lu, H. Zhuang, P. Chen, H. Chang, C.-C. Chang, Y.-C. Wong, L. Sha, D. Huang, Y. Luo, C.-C. Teng, and C.-K. Cheng, “ePlace-MS: Electrostatics-based placement for mixed-Size circuits,” IEEE Tran. of TCAD, vol. 34, no. 5, pp. 685-698, 2015.
[20] 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.
[21] A. Vidal-Obiols, J. Cortadella, J. Petit, M. Galceran-Oms, and F. Martorell, “RTL-Aware dataflow-driven macro placement,” in Proc. of DATE, pp. 186-191, 2019.
[22] 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 Tran. of TCAD, vol. 32, no. 2, pp. 228-241, 2013.
[23] Himax Technologies, Inc. About Himax. Accessed: November 23, 2020. [Online]. Available: https://www.himax.com.tw/company/about-himax/
[24] Synopsys, Inc. IC Compiler. Accessed: November 23, 2020. [Online]. Available: https://www.synopsys.com/implementation-and-signoff/physical-implementation/ic-compiler.html
[25] https://github.com/The-OpenROAD-Project/RePlAce