Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/5448
Title: | 針對大型異質現場可程式化邏輯閘陣列之巨集暨解析擺置 Packing and Analytical Placement for Large-Scale Heterogeneous FPGAs |
Authors: | Yu-Chen Chen 陳昱臻 |
Advisor: | 張耀文(Yao-Wen Chang) |
Keyword: | 實體設計,資料路徑,電路巨集,電路擺置,異質電路, Physical Design,Datapath,Packing,Placement,Heterogeneous, |
Publication Year : | 2014 |
Degree: | 碩士 |
Abstract: | 隨著現場可程式邏輯閘陣列的演進,其晶片大量採用複雜元件如隨機存取記憶體以及數位訊號處理器以實現當代電路設計廣泛使用的矽智產。而複雜元件電路往往伴隨著資料路徑。在過去,電路巨集與擺置的問題雖然已被廣泛研究,資料路徑電路在電路巨集與擺置上的考量卻大多被忽視。然而,未考慮資料路徑之巨集與擺置將破壞電路的規律性,從而降低效能。除此之外,隨著電路設計複雜度的急遽上升,可擴展性已成為主要考量。另外,多數巨集之演算法過度聚集元件,也造成擺置上的困難並限制了擺置的最佳化。然而,學術界廣為使用的標竿電路卻遠小於現實電路,不足以顯現出演算法之可擴展性。
因此,在這篇論文中,我們針對上述問題提出了一個考慮密集資料路徑結構的巨集與擺置演算法。我們所提出的巨集演算法針對複雜元件、資料路徑以及一般元件分別採用不同的巨集方法。我們的巨集方法提供後續的擺置更大的彈性和潛力以得到更好的最佳化。此外,我們提出V型架構來加強演算法的可擴展性。而我們所提出的擺置演算法使用非線性最佳化的方式降低線長並針對密集資料路徑結構作處理 以獲得高品質的擺置。實驗結果顯示出,我們所提出的方法相較於先前的研究,可以有效地得到非常好的電路擺置結果,並且可以在大型異質標竿電路中得到驗證。 As field programmable gate arrays (FPGAs) have evolved, heterogeneous components such as random access memory blocks (RAMs) and digital signal processing blocks (DSPs) are widely applied to effectively implement intellectual property (IP) cores extensively used in modern circuits. The RAMs and DSPs are often accompanied with datapath-intensive circuits. Although FPGA packing and placement for general logic blocks have been studied extensively, not much work addresses the optimization of datapath. Packing and placement without considering datapath could break the regularity and lead to significantly worse results. Besides, scalability has become a first-order metric for modern FPGA design, mainly due to the dramatically increasing design complexity. Most commonly used academic benchmark suites, however, are relatively much smaller than the latest commercial FPGA chips, which may not demonstrate scalability well. Furthermore, most of the existing works on packing tend to be over-packed, which increases the difficulty for placement and limits the placement optimization. Therefore, to solve the issues above, we propose efficient and effective packing and analytical placement algorithms in this thesis. Our packing algorithm is composed of three stages to handle different structures of heterogeneous components and datapath blocks. Our packing provides a more placement-friendly netlist than VPR's, which gives a great potential for placers to achieve significant quality improvement. A V-shaped framework is proposed to enhance the scalability while considering more exact design constraints than existing works. Moreover, our wirelength-driven analytical placement algorithm applies effective nonlinear optimization techniques and utilizes the regularity of the datapaths to achieve scalability and high quality. A complex-block-alignment function is proposed to better handle the heterogeneity, and a multilevel framework is applied to further enhance the scalability of our placement algorithm. Experimental results show that our method is scalable while preserving high quality. Our approach achieves a 199.80x speedup, compared to the VPR's latest packing flow (VPR 7.0), and a 3.07x speedup with 6% shorter wirelength, compared to the VPR's latest placement flow, based on a set of modern large-scale FPGA benchmarks, Titan23 benchmark suites. The overall flow achieves a 18.30x speedup with 50% shorter wirelength, compared to the VPR's packing and placement flow. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/5448 |
Fulltext Rights: | 同意授權(全球公開) |
Appears in Collections: | 電子工程學研究所 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-103-1.pdf | 1.51 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.