As the sizes of modern circuit designs become bigger and bigger, implementing those large circuits into FPGA become arduous. The state-of-the-art academic FPGA place-and-route tool, VPR, has good quality but needs around a whole day to complete a placement when the input circuit netlist contains millions of lookup tables, excluding the runtime needed for routing. / To speed up the placement process, we propose a routability-driven placement algorithm for FPGAs, which adopts techniques used in ASIC global placer. Our placer follows the lower-bound-and-upper-bound iterative optimization process in ASIC placers like Ripple. The total half perimeter wirelength (HPWL) of the circuit is used as the objective cost function and it modeled using the Bound2Bound net model. In lower bound computation, a placement solution with the minimum HPWL is determined by the conjugate gradient method. In upper bound computation, an almost-legalized result is produced by spreading cells linearly in the whole placement area. Those positions are then served as fixed-point anchors and fed into the next lower bound computation. Furthermore, global routing will be performed in the upper bound computation to estimate the routing segments usage, as a mean to consider congestion in the placement. The two bounds computations are computed alternatively until their results converge. / We tested our approach using 20 MCNC benchmarks and 16 large benchmarks for performance and scalability. Experimental results show that based on the island-style architecture which VPR is most optimized, our approach can obtain a placement result 8× faster than VPR with 2% more in channel width, or 3× faster with 1% more in channel width when considering congestion either. Our approach is even 20× faster in placing large benchmarks having over 50,000 lookup tables, however, with 10% more in channel width. Based on the Xilinx Virtex-5 architecture from a recent related work, we can out-perform VPR by reducing the channel width by 3% with almost 3× speedup in runtime. / 現今的電路設計得愈來愈大，要把這些巨大的電路實現在現場可程式邏輯門陣列(FPGA)上變得愈來愈困難，由其在布局及布線程序上變得十分耗時。儘管在一般的情況下，現時在學術領域中，最先進的用在FPGA上的布局及布線工具能夠提供高質素的布局結果，但當所需要布局的電路所包含的邏輯元件數達到數百萬個以上時，該工具也要耗費一整天的時間才能完成整個布局程序，其中並未計算之後布線程序所額外需要的時間。 / 有見及此，我們參考了一些應用在特殊應用積體電路(ASIC)設計軟體上的布局方法，並提出了一個專為FPGA而設的偏向優化Routability的布局算法來縮短布局程序所需要的時間。我們的算法以Bound2Bound模型來模擬電路內邏輯元件間的接線，並估算其Half-Perimeter線長(HPWL)來作為我們的目標函數進行優化。我們採用了一些ASIC布局軟體，如Ripple內的上限及下限交互計算的迭代優化程序。在下限的運算過程中，我們在無視節點重疊的情況下，使用了共軛梯度法來找出HPWL的最少值。在上限的運算過程中，我們把在下限計算找到的結果平均散佈在整個可布局的區域內，從而減少節點重疊的情況來得出一接近有效的布局結果。接著，這些節點的位置會被用作定點錨，附加在下一次的下限計算中，並引導它得出一節點重疊相對較少的布局結果。此外，我們可以選擇在上限的運算過程中加入Global Routing程序來估計該布局結果所需的線段數，從而在布局過程中考慮布線過份擁塞的情況。上限及下限的計算會不斷交互進行，直至雙方所得的結果聚合為止。 / 我們使用了20個MCNC基準電路及16個大型基準電路，來測試我們的布局算法的性能和可擴展性。實驗結果指出，針對島狀結構的FPGA，我們的算法能夠比VPR快8倍得出布局結果，但其通道寬度(Channel Width)卻增加了2%。如果在考慮布線擁塞度的情況下，我們的算法能夠比VPR快3倍，但其通道寬度卻增加了1%。再者，對於一些擁有超過50000個邏輯元件的大型基準電路，相比於VPR，雖然我們的算法能夠提供20倍的速度增長，但其布局結果的通道寬度卻增加了10%。如果我們使用在最近的相關研究中使用的Xilinx Virtex-5結構的話，我們的算法能夠比VPR快接近3倍得出布局結果，並且減少約3%的通道寬度。 / Lam, Ka Chun. / Thesis M.Phil. Chinese University of Hong Kong 2014. / Includes bibliographical references (leaves 64-70). / Abstracts also in Chinese. / Title from PDF title page (viewed on 12, October, 2016). / Detailed summary in vernacular field only. / Detailed summary in vernacular field only. / Detailed summary in vernacular field only.
| Identifer | oai:union.ndltd.org:cuhk.edu.hk/oai:cuhk-dr:cuhk_1291514 |
| Date | January 2014 |
| Contributors | Lam, Ka Chun , active 2014 (author.), Young, Fung Yu (thesis advisor.), Chinese University of Hong Kong Graduate School. Division of Computer Science and Engineering. (degree granting institution.) |
| Source Sets | The Chinese University of Hong Kong |
| Language | English, Chinese |
| Detected Language | English |
| Type | Text, bibliography, text |
| Format | electronic resource, electronic resource, remote, 1 online resource (x, 70 leaves) : illustrations (some color), computer, online resource |
| Rights | Use of this resource is governed by the terms and conditions of the Creative Commons "Attribution-NonCommercial-NoDerivatives 4.0 International" License (http://creativecommons.org/licenses/by-nc-nd/4.0/) |
Page generated in 0.0019 seconds