近年來，電子設計自動化軟體隨著積體電路工業越來越發達，合法擺置階段是電子設計自動化軟體中極為重要的部分。合法擺置階段將電路元件擺在合法的位置上，因為在這個階段會決定標準元件（standard cell）的位置，所以如何決定擺置位置是一項很重要的議題。 在目前的擺置階段（placement）較著重的部分是在可繞性（routability）的估測，相較於以往所做的線長（wire-length）考量不同，過短的線長可能會導致擺置地太擁擠，以至於在繞線（routing）階段時可能會導致繞不完的情形產生。因此可繞性問題便在改善當擺置完後能提供一個較高的可繞性擺置結果。而這些可繞性的考量以往都是在全域擺置（global placement）做評估，因此在合法擺置（legalization）間段若只是找尋最短距離擺置或者找尋最短線長擺置時，可能就會犧牲掉在全域擺置時所做的可繞性評估，因此在擺置合法化階段時若能加入可繞性的評估，必能提供較好的可繞性擺置結果。 在本篇論文中，我們提出利用建立擁擠地圖（congestion map）表示擁擠區塊，根據這個地圖提供給標準元件移動的力量，這個力量目的是希望能夠避開溢位邊緣（routing edge），但是為了要保持原本全域擺置的結果，我們給的移動範圍只限於一單位網格（bin），若擺置密度（placement density）可以承受的就會直接移入，否則就會做交換元件的動作。我們採取了網格基準（bin-based）[15]的擺置合法化做擺置，但我們為了要讓標準元件保留在原始的網格，我們給予了一個花費成本（cost）搜尋合法位置。實驗結果顯示，我們提出的方法可以減少溢位（overflow）發生的情形。 In recent years, several electronic-design automation (EDA) tools for placement are proposed and developed. Legalization is a very important stage for placing cells on legal positions. The existed methods for legalization usually try to minimize the total wire-length of cells. However, considering wire-length only in the placement stage is not sufficient for placing standard cells. A congested placement result may incur the routing difficult due to the congested problem in the placement rows. Therefore, legalization needs to consider the routability instead of the wire-length or displacement minimization. In this thesis, we adopt a congestion map to indicate the usage of routing edges. Standard cells will be moved by forces to avoid overflow edges. In order to preserve the global placement result, the searching range is limited in the surrounding bins. Then, we use bin-based [15] legalization to find the positions of cells. Finally, we propose a cost function to search optimal position. To evaluate our proposed method, we use the benchmarks provided by ICCAD 2012 placement contest as experimental data. Experimental results show that the proposed method can produce better placement results that incur less overflows in the global routing stage.
