近年來，隨著設計複雜度的增加，多重排高元件的擺置問題受到很多關注，元件從原本單一高度轉變為多重高度，這樣的改變除了可以使得整體晶片的面積使用效率提高外，連帶的整體效能也能更加提升，卻也會使得元件再擺置時會遇到更多的挑戰。首先，在處理多重排高度元件的擺置時，需要考慮到此元件對其他行數間，與相鄰元件擺放的重疊問題，第二個，由於元件高度的不一致，我們必須依照電源軌道去進行擺置。如果元件高度為奇數，我們可以將其擺置在任一行數，反之如果高度為偶數時，則必須擺置在特定的行數間，這是由於奇數高元件上下所對應的電源是相反的，假若其違反這項限制時，只需透過上下翻轉就能輕易解決。除了上面兩個問題外，圍籬區域的限制在最近也備受關注，這是由於設計者希望將功能相近的元件擺置在指定的區域，進而增加整體的設計效率，在處理這些具有圍籬限制的擺置問題時，由於這些指定區域只能擺置這個群組的元件，導致我們必須先檢查所有元件並將每個元件移動到各自的可擺放區域，但是這樣的直接移動可能會導致一些區域，元件密度過高而大大增加後面合法化的困難度，所以本篇提出一個能考慮圍籬區域限制之多重排高元件擺置方法。

Cell placement is getting more complicated when multiple-row height cells are widely used in modern designs. These cells make placement more difficult because placing a single cell has to consider placement of cells in other rows. Moreover, it has to satisfy the P/G alignment constraint and fence-region constraint. Many previous algorithms try to legalize a multiple-row height cell in a specified window and continuously enlarge the size of the window until the cell is legalized. However, this procedure usually causes excessive displacement and larger wirelength. Hence, this paper proposes a dynamic programming based algorithm to reorder cells instead of enlarging the window. Furthermore, the result is refined by a minimum cost maximum flow algorithm. The experimental results show that our algorithm achieves 20% less maximum displacement and 2% total displacement compared to the 1st placer on the benchmarks of IC/CAD 2017 Contest.

[1] C. -H. Wang, Y. -Y Wu, J. Chen, Y. -W. Chang, S. -Y. Kuo, W. Zhu, and G. Fan, ”An Effective Legalization Algorithm for Mixed-Cell-Height Standard Cells”, Proc. ASP-DAC, pp. 450-455, Jan. 2017.
[2] D. Hill, ”Method and System for High Speed Detailed Placement of Cells within Integrated Circuit Designs”, U.S. Patent 6370673, April. 2002.
[3] I. S. Bustany, D. Chinnery, J. R. Shinnerl, and V. Yutsis, ”ISPD 2015 Benchmarks with Fence Regions and Routing Blockages for Detailed Routing-Driven Placement”, Proc. ISPD, pp. 157-164, April. 2015.
[4] J. Chen, Z. Zhu, W. Zhu, and Y. -W. Chang, ”Toward Optimal Legalization for Mixed-Cell-Height Circuit Designs”, Proc. DAC, pp. 52, Jun. 2017.
[5] N. K. Darav, A. Kennings, D. Westwick, and L. Behjat, ”High Performance Global Placement and Legalization Accounting for Fence Regions”, Proc. ICCAD, pp. 514-519, Nov. 2015.
[6] N. K. Darav, I. S. Bustany, A. Kennings, and R. Mamidi, ”ICCAD- 2017 CAD Contest in Multi-Deck Standard Cell Legalization and Benshmarks”, Proc. ICCAD, pp. 867-871, Nov. 2017.
[7] P. Spindler, U. Schlichtmann and F. M. Johannes, ”Abacus: Fast Legalization of Standard Cell Circuits with Minimal Movement”, Proc. ISPD, pp. 47-53, April. 2008.
[8] S.-H. Baek, H.-Y. Kim, Y.-K. Lee, D.-Y. Jin, S.-C. Park and J.-D. Cho, ”Ultra High Density Standard Cell Library Using Multi-Height Cell Structure”, Proc. SPIE, 2008.
[9] T. R. Gheewala, M. J. Colwell, H. H. Yang, D. G. Breid, ”Dualheight Cell with Variable Width Power Rail Architecture”, US Patent US6838713, 2005.
[10] Y. Lin, B. Yu, X. Xu, J. -R. Gao, N. Viswanathan, and W. -H. Liu, ”MrDP: Multiple-row Detailed Placement of Heterogeneous-sized Cells for Advanced Nodes”, Proc. ICCAD, pp. 7, Nov. 2016.
[11] W. -K. Chow, C. -W. Pui, and E. F. Y. Young, ”Legalization Algorithm for Multiple-Row Height Standard Cell Design”, Proc. DAC, pp. 1-6, Jun. 2016.