臺灣大學: 電子工程學研究所張耀文林子恆Lin, Tzu-HenTzu-HenLin2013-04-102018-07-102013-04-102018-07-102012http://ntur.lib.ntu.edu.tw//handle/246246/256701將技術應對過的線路邏輯元件擺置到一個二維的現場可程式邏輯閘陣列 (FPGA)上是個經典的問題。然而，近代電路日益增加的設計複雜度已改變了這 個問題並使得傳統的現場可程式邏輯閘陣列擺置技術不再適用。傳統的退火式現 場可程式邏輯閘陣列擺置器因可以達成高品質的擺置而幾十年來ㄧ直稱霸。然而， 對於近代高複雜度的設計，它們卻無法在合理的時間內完成擺置並同時維持高品 質。近年，工業界已移向另一個被期待能較佳處理高複雜度設計的技術，解析擺 置。因此，對於現場可程式邏輯閘陣列的設計，開發並使用解析擺置已成了必然 的趨勢。在這篇論文當中，我們提出了一個多階層時序與線長導向的解析現場可 程式邏輯閘陣列擺置演算法。這個演算法包含了四個階段：(1) 考慮元件排列的多層時序與線長導向數值分析全域擺置，(2) 分割式的重疊移除，(3) 線長導向 元件配對細部擺置，以及(4) 時序導向退火式細部擺置。我們提出的方法不只比 目前最著名最佳的退火式現場可程式邏輯閘陣列擺置器VPR 還快，更在關鍵路徑延遲與總繞線長度上優於VPR。更明確地，我們所提出的方法平均上能有VPR 6.91 倍的速度且擁有比VPR 小7%的關鍵路徑延遲與短1%的總繞線長度。Placing a technology-mapped netlist of logic blocks onto a 2D array of pre-fabricated con gurable logic blocks (CLB) on a eld programmable gate array (FPGA) chip is a classical problem. However, the increasing design complexity of modern circuits has reshaped this problem and made traditional FPGA placement techniques not appropriate anymore. Traditional simulated-annealing-based FPGA placers, placers which can achieve very high-quality placements, have been dominating for decades. Nevertheless, for modern high-complexity designs, they are not scalable while maintaining high quality. Recently, industry has migrated to another technology called analytical placement which is expected to better handle the scalability issue in high-complexity designs. Therefore, developing and applying analytical methods have become inevitable trends for FPGA placement. In this thesis, we propose a multilevel timing-and-wirelength-driven analytical placement algorithm for FPGAs. Our proposed algorithm consists of (1) multilevel timing-and-wirelength-driven analytical global placement with block alignment consideration, (2) partitioning-based legalization, (3) wirelength-driven block matching-based detailed placement, and (4) timing-driven simulated-annealing-based detailed placement. Our proposed ap- proach is not only faster than the well-known, state-of-the-art academic simulated-annealing-based FPGA placer VPR but also better than VPR in terms of critical path delay and total routed wirelength. More speci cally, our proposed method can achieve 6.91 X speedup on average with 7% smaller critical path delay and 1% shorter routed wirelength compared to VPR.140 bytestext/htmlen-US現場可程式邏輯閘陣列解析擺置全域擺置重疊移除時序線長FPGAAnalytical PlacementGlobal PlacementLegalizationTimingWirelengththesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/256701/1/index.html