請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33526
標題: | 應用於超大型積體電路擺置系統之細部擺置演算法 A Detailed Placement Algorithm for Large-Scale VLSI Circuits |
作者: | Tien-Chang Hsu 許天彰 |
指導教授: | 張耀文(Yao-Wen Chang) |
關鍵字: | 擺置,細部擺置, placement,detailed placement, |
出版年 : | 2006 |
學位: | 碩士 |
摘要: | 近代高效能積體電路設計需要大量預留空間以利於後續效能最佳化,因此在擺置階段的元件擺置密度控制益發重要。有鑑於現有的細部擺置演算法往往為了縮減連線長度而大幅破壞原本的密度控制,在此篇論文中,我們提出一個能夠縮短連線長度同時保留元件密度分佈的細部擺置演算法。我們的方法包括能夠同時擺置大量元件的元件匹配技術、提高效能的窗格掃掠技術、以及漸近改善擺置密度分佈的元件滑動技術。根據實驗,我們的程式在考慮連線長度與擺置密度的擺置品質優於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. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/33526 |
全文授權: | 有償授權 |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-95-1.pdf 目前未授權公開取用 | 1.22 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。