隨著模組擺置變得越來越具有挑戰，我們提出一個演算法來去處理這個問題。通常先前的方法只專注於在線長及可繞度上進行優化。然而，考慮資料流關係可以進一步擺置品質，而且現在很少有研究在擺置模組時，將資料流加入考量。因此，我們採用K-L的方法將兩個資料路徑為導向(datapath-oriented)的模組進行交換來促使減少資料流流向的交錯彎曲，並且在模組合法化之前，先決定他們更好的擺置順序。由於模組擺置完成後，在擺置標準邏輯閘時，會使得標準邏輯閘的位置發生巨大的改變，這樣在估算線長及可繞度時就會非常不精確，因此，在模組擺置階段除了擺置模塊外，我們還會將標準邏輯閘進行擺置。由於可以建立較正確的擁擠圖，所以我們可以獲得可繞度更好的擺置結果。因此，除了在合法化時避免模組擺在高擁擠區域，在優化階段時，將移除一些其連線經過嚴重繞線擁擠區域的模組；而不像原始方法將擺置在擁擠區域的模組拔除，因為可能是其它模組擺在不好的位置上使其連線必須繞較為遙遠而導致擁擠。實驗結果顯示，我們方法的結果在線長及可繞度上，皆比先前方法 [16] 的結果更好。

As macro placement becomes more and more challenging, this paper proposes an algorithm to handle this problem. Previous works usually focus on optimizing the wirelength and routability. However, placement quality can be further improved by considering dataflows, and there exist few researches taking dataflow into consideration during the macro placement stage. Therefore, we employ a K-L based algorithm to swap two datapath-oriented macros to reduce dataflow winding and determine their better sequence before we legalize macros. Due to the standard cells locations will be changed which leads to estimating wirelength and routability inaccurately after macros are placed, we also place standard cells except for macros. Since a correct congestion map is constructed, we can obtain a placement with better routability. Thus, in addition to avoiding macros placed in the high congestion region in the legalization, we also remove and re-place some macros whose nets passing through serious routing congestion in the refinement. The experimental results show that our approach obtains better results than previous work [16] in terms of wirelength and routability.

[1]. Synopsys Inc. https://www.synopsys.com/company.html
[2]. Himax Inc. http:www.himax.com.tw/zh/company/about-himax/
[3]. C. Alpert, A. Kahng, G.-J. Nam, S. Reda, and P. G. Villarrubia, “A Semi-persistent Clustering Technique for VLSI Circuit Placement,” in Proc. of ISPD, pp. 200-207, 2005.
[4]. 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 TCAD, vol. 27, no. 9, pp. 657-662, 2008.
[5]. C. Chu and Y.-C. Wong, “FLUTE: Fast Lookup Table Based Rectilinear Steiner Minimal Tree Algorithm for VLSI Design,” IEEE TCAD, vol. 27, no. 1, pp. 70-83, Jan 2008.
[6]. S. Chou, M.-K. Hsu1, and Y.-W. Chang, “Structure-Aware Placement for Datapath-Intensive Circuit Designs,” in Proc. of DAC, July 2012.
[7]. Y.-F. Chen, C.-C. Huang, C.-H. Chiou, Y.-W. Chang, and C.-J. Wang, “Routability-driven Blockage-aware Macro Placement,” in Proc. of DAC, pp. 1-6, 2014.
[8]. C.-H. Chiou, C.-H. Chang, S.-T. Chen, and Y.-W. Chang, “Circular-contour-based Obstacle-aware Macro Placement,” in Proc. of ASP-DAC, pp. 172-177, 2016.
[9]. C.-H. Chang, Y.-W. Chang, T.-C. Chen, “A Novel Damped-wave Framework for Macro Placement,” in Proc. of ICCAD, pp. 504-511, 2017.
[10]. K.-R. Dai, W.-H Liu, Y.-L Li, “NCTU-GR: Efficient Simulated Evolution-based Rerouting and Congestion-relaxed Layer Assignment on 3-D Global Routing,” IEEE TVLSI, vol.22, no.3, pp. 459-472, 2012.
[11]. C.-C. Huang, B.-Q. Lin, H.-Y. Lee, Y.-W. Chang, K.-S. Wu, and J.-Z. Yang, “NTUplace4h: A Novel Routability-Driven Placement Algorithm for Hierarchical Mixed-Size Circuit Designs,” IEEE TCAD, vol. 33, no. 12, pp. 1914-1927, Dec. 2014.
[12]. 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, June 2017.
[13]. B. W. Kernighan and S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Syst. Tech. J. vol. 49, no. 2, pp. 291–307, 1970.
[14]. J.-M. Lin, Y.-W. Chang, and S.-P. Lin. “Corner Sequence–A Padmissible Floorplan Representation with A Worst Case Linear-time Packing Scheme,” IEEE TVLSI, vol. 11, no .4, pp. 679-686, 2003.
[15]. 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, June 2019.
[16]. 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 ICCAD 2019.
[17]. J.K. Ousterhout, “Corner Stitching: A Data-Structuring Technique for VLSI Layout Tools,” IEEE TCAD, vol. 3, no. 1, pp. 87-100, 1984.
[18]. A. Vidal-Obiols, J. Cortadella, J. Petit, M. Galceran-Oms, and F. Martorell, “RTL-Aware Dataflow-Driven Macro Placement,” in Proc. of DATE, March 2019.
[19]. M.-C. Wu and Y.-W. Chang, “Placement with Alignment and Performance Constraints Using the B*-tree Representation,” in Proc. of ICCD, pp. 568-571, 2004.
[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 ISPD, pp. 79–86, March 2012.