- 學位論文
應用於超大型積體電路擺置系統之細部擺置演算法
A Detailed Placement Algorithm for Large-Scale VLSI Circuits
摘要
近代高效能積體電路設計需要大量預留空間以利於後續效能最佳化，因此在擺置階段的元件擺置密度控制益發重要。有鑑於現有的細部擺置演算法往往為了縮減連線長度而大幅破壞原本的密度控制，在此篇論文中，我們提出一個能夠縮短連線長度同時保留元件密度分佈的細部擺置演算法。我們的方法包括能夠同時擺置大量元件的元件匹配技術、提高效能的窗格掃掠技術、以及漸近改善擺置密度分佈的元件滑動技術。根據實驗，我們的程式在考慮連線長度與擺置密度的擺置品質優於APlace2.0與FastPlace2.0的細部擺置程式達到4.9%與6.7%。而在僅考慮連線長度的擺置品質估計上也以0.3%、0.7%的幅度領先。實驗結果證明我們的演算法能夠在保留原本的元件擺置密度分佈的前提下，達到當今學術界細部擺置器的連線長度水平。
並列摘要
A modern circuit placement algorithm consists of three steps: global placement, legalization, and detailed placement. Global placement finds rough positions of the circuit blocks, legalization removes the overlaps, and detailed placement refines the result. Modern high-performance IC designs integrate millions of blocks in a single chip. Traditional detailed placement methods consider only local cells and thus cannot handle modern large-scale designs well. It is therefore desirable to develop a better detailed placement algorithm with a more global view. Most detailed placement algorithms focus on the wirelength reduction, but the density control in the placement step becomes more important due to the increasing white space in modern designs for further performance optimization. We present a detailed placement algorithm that can minimize the wirelength and preserve the density controlled by the global placement. We adopt three major techniques in our detailed placement algorithm: (1) a cell matching technique to rearrange a group of cells simultaneously, (2) a window sweeping method to enhance the window-based local refinement by perturbing the window size and sweep direction, and (3) a cell sliding technique to gradually slide cells out of density overflow regions. Experimental results show that our algorithm achieves high-quality placement results. For the new cost metric which considers the wirelength and density constraints, our algorithm is 4.9% and 6.7% better than the state-of-the-art results from the APlace 2.0 and FastPlace 2.0, respectively. Our resulting HPWL is still 0.3% and 0.7% shorter than the above detailed placers. The results show that our algorithm can preserve the density controlled by the global placement and our wirelength improvement is still quite competitive with other state-of-the-art detailed placers.