在現今的電路設計中，隨著製程尺寸愈來愈小及電路內元件數量的急劇成長上升，使得整體的設計流程比以往來的困難。在傳統的設計流程中，往往將擺置及繞線兩個課題分開來討論、研究，以減少問題的複雜度。在擺置階段，繞線長度的最佳化是最主要的考量。然而，過小的繞線長度卻可能會因為邏輯閘擺置過於密集，而導致繞線過份擁擠而造成繞線失敗。因此，在擺置階段中一併考慮可繞度是必要的。在本論文中，我們提出一個在後擺置階段同時考慮繞線長以及可繞度的方法。我們的方法大略上分為兩個階段。首先，我們先處理擁擠度的問題，我們先將找出擁擠的區域，並且將區域內的區塊膨脹或壓縮，使得擁擠區域內的元件重新散佈；接下來，在依據元件間連線的方向，重新改變元件排序來解決內部擁擠的問題;最後，再考量將繞線長最佳化，並且將元件合法化來做為最終的設計。
由實驗數據我們可看出所提出的方法可有效的解決擁擠問題。我們將提出來的方法應用在ISPD05/06 的測試檔，根據ISPD07/08 繞線競賽的參數設定，並且用mPL6產生初始化的擺置結果。我們成功的在12組電路檔裡完全解決擁擠問題，大大提昇了電路可繞度，同時保有一定品質的繞線長度，以及可接受的總執行時間。

As design features decrease, the number of cells in a single chip increases dramatically, which makes modern circuit design become more complicated than ever. Traditionally, placement and routing problem are handled separately to reduce complex. In the placement stage, minimization of wirelength is the major consideration; however, small wirelength may cause circuits unroutable in the routing stage. Thus, it is necessary to consider routability in the placement stage. In this thesis, we propose a methodology to consider wirelength and routability in the post-placement stage. Our method can be roughly divided into two stages. In the first stage, we first deal with the congestion problem. Our approach first identifies the congested regions and inflates or compact bins in the corresponding areas to redistribute cells outside the regions. Then, cells are reordered with its wire-direction to reduce internal congestion. After the congestion problem is resolves, then the total wirelength is further minimized and all cells are legalized to obtain the final solution.
The experimental results show that our approach is effective and efficient in solving the congestion problem. The experiment is tested on the ISPD05/06 [1, 2] benchmarks with global placement solution generated by mPL6 and using the ISPD07/08 contest benchmark parameters [3, 4]. The results show that the congestion problem in 12 benchmarks can be solved by our method without deteriorating routed wirelength.

[1] ISPD05 placement contest benchmarks. http://www.sigda.org/ispd2005/contest.htm.
[2] ISPD06 placement contest benchmarks.
http://www.sigda.org/ispd2006/contest.htm.
[3] ISPD07 global routing contest benchmarks.
http://www.sigda.org/ispd2007/contest.htm.
[4] ISPD08 global routing contest benchmarks.
http://www.sigda.org/ispd2008/contest.htm.
[5] Y. Chang, Y. Lee, and T. Wang. NTHU-Route 2.0: a fast and stable global router. In Proc. Intl. Conf. on Computer-Aided Design, pages 338–343, 2008.
[6] M. Pan, N. Viswanathan, and C. Chu. An efficient and effective detailed placement algorithm. In Proc. Intl. Conf. on Computer-Aided Design, pages 48–55, 2005.
[7] T.-F. Chan, J. Cong, and M. Romesis, J.-R. Shinnerl, K. Sze, and M. Xie. mPL6: a robust multilevel mixed-size placement engine. In Proc. Intl. Symp. on Physical Design, pages 227–229, 2005.
[8] P. Spindler, and F.M. Johannes. Fast and accurate routing demand estimation for efficient routability-driven placement. In Proc. Design, Automation & Test in Europe, pages 1226-1231, 2007.
[9] C. Chu, and Y.-C. Wong. FLUTE: fast lookup table based rectilinear steiner minimal tree algorithm for VLSI design. IEEE Trans. on Computer-Aided Design and Integrated Circuits and Systems, vol. 27, no. 1, pages 70-83, January, 2008.
[10] K. Tsota, C.-K. Koh, and V. Balakrishnan. A study of routability estimation and clustering in placement. In Proc. Intl. Conf. on Computer-Aided Design, pages 363-366, 2009.
[11] K. Tsota, C.-K. Koh, and V. Balakrishnan. Guiding global placement with wire density. In Proc. Intl. Conf. on Computer-Aided Design, pages 212–217, 2008.
[12] W. Hou, H. Yu, X. Hong, Y. Cai, W. Wu, J. Gu, and W. Kao. A new congestion-driven placement algorithm based on cell inflation. In Proc. Asia and South Pacific Design Automation Conf., pages 605–608, 2001.
[13] U. Brenner and A. Rohe. An effective congestion-driven placement framework. In Proc. Intl. Symp. on Physical Design, pages 6–11, 2002.
[14] Z. Jiang, B. Su, and Y. Chang. Routability-driven analytical placement by net overlapping removal for large-scale mixed-size designs. In Proc. Design Automation Conf., pages 167–172, 2008.
[15] C. Li, M. Xie, C. Koh, J. Cong, and P. Madden. Routability-driven placement and white space allocation. IEEE Trans. on Computer-Aided Design and Integrated Circuits and Systems, vol. 26, no. 5, pages 167–172, May, 2008.
[16] Y. Zhang, and C. Chu. CROP: fast and effective congestion refinement of placement. In Proc. Intl. Conf. on Computer-Aided Design, pages 344-350, 2009.
[17] J.A. Roy, N. Viswanathan, G.-J. Nam, C.J. Alpert, and I.L. Markov. CRISP: congestion reduction by iterated spreading during placement. In Proc. Intl. Conf. on Computer-Aided Design, pages 357-362, 2009.
[18] K.-R. Dai, C.-H. Lu, and Y.-L. Li. GRPlacer: improving routability and wire-length of global routing with circuit replacement. In Proc. Intl. Conf. on Computer-Aided Design, pages 351-356, 2009.
[19] M. Pan and C. Chu. IPR: an integrated placement and routing algorithm. In Proc. Design Automation Conf., pages 59-62, 2007.
[20] M. Pan and C. Chu. FastRoute 2.0: a high-quality and efficient global router. In Proc. Asia and South Pacific Design Automation Conf., pages 250–255, 2007.
[21] N. Viswanathan and C. Chu. FastPlace: efficient analytical placement using cell shifting, iterative local refinement and a hybrid net model. In Proc. Intl. Symp. on Physical Design, pages 26–33, 2004.
[22] ISPD2011 Routability-driven Placement Contest.
http://www.ispd.cc/contests/11/ispd2011_contest.html
[23] P. Spindler, U. Schlichtmann, and F.-M. Johannes. Abacus: fast legalization of standard cell circuits with minimal movement. In Proc. Intl. Symp. on Physical Design, pages 47-53, 2008.