請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/5448
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 張耀文(Yao-Wen Chang) | |
dc.contributor.author | Yu-Chen Chen | en |
dc.contributor.author | 陳昱臻 | zh_TW |
dc.date.accessioned | 2021-05-15T17:59:10Z | - |
dc.date.available | 2019-03-18 | |
dc.date.available | 2021-05-15T17:59:10Z | - |
dc.date.copyright | 2014-03-18 | |
dc.date.issued | 2014 | |
dc.date.submitted | 2014-02-12 | |
dc.identifier.citation | [1] Altera Corp. http://www.altera.com/.
[2] Xilinx Inc. http://www.xilinx.com/. [3] T. Ahmed, P. D. Kundarewich, J. H. Anderson, B. L. Taylor, and R. Aggarwal. Architecture-specific packing for virtex-5 FPGAs. In Proceedings of Symposium on Field Programmable Gate Arrays, pages 5-13, 2008. [4] M. J. Alexander, J. P. Cohoon, J. L. Ganley, and G. Robins. Placement and routing for performance-oriented FPGA layout. VLSI Design, 7(1):97-110, Jan. 1998. [5] C. Alpert, A. Kahng, G.-J. Nam, S. Reda, and P. Villarrubia. A semi-persistent clustering technique for VLSI circuit placement. In Proceedings of ACM International Symposium on Physical Design, pages 200-207, San Francisco, USA, Apr. 2005. [6] V. Betz and J. Rose. Cluster-based logic blocks for FPGAs: area-efficiency vs. input sharing and size. In Proceedings of Custom Integrated Circuits Conference, pages 551-554, Santa Clara, USA, May. 1997. [7] V. Betz and J. Rose. VPR: a new packing, placement and routing tool for FPGA research. In Proceedings of Field-Programmable Logic and Applications, pages 213-222, London, UK, Sep. 1997. [8] V. Betz and J. Rose. Architecture and CAD for Deep-Submicron FPGAs. Kluwer, 1999. [9] E. Bozorgzadeh, S. O. Memik, X. Yang, and M. Sarrafzadeh. RPack: routability-driven packing for cluster-based FPGAs. In Proceedings of Asia and South Pacific Design Automation Conference, pages 629-634, Yokohama, Japan, Feb. 2001. [10] T. J. Callahan, P. Chong, A. DeHon, and T. Wawrzynek. Fast module mapping and placement for datapaths in FPGAs. In Proceedings of Symposium on Field Programmable Gate Arrays, pages 123-132, Monterey, USA, Feb. 1998. [11] T. F. Chan, J. Cong, J. R. Shinnerl, K. Sze, and M. Xie. mPL6: enhanced multilevel mixed-size placement. In Proceedings of ACM International Symposium on Physical Design, pages 212-214, San Jose, USA, Apr. 2006. [12] D. T. Chen, K. Vorwerk, and A. Kennings. Improving timing-driven FPGA packing with physical information. In Proceedings of Field-Programmable Logic and Applications, pages 117-123, Amsterdam, Dutch, Aug. 2007. [13] T.-C. Chen, Z.-W. Jiang, T.-C. Hsu, H.-C. Chen, and Y.-W. Chang. NTUplace3: an analytical placer for large-scale mixed-size designs with preplaced blocks and density constraints. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 27(7):1228-1240, Jul. 2008. [14] C.-L. E. Cheng. RISA: accurate and efficient placement routability modeling. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 690-695, San Jose, USA, Nov. 1994. [15] S. Chou, M.-K. Hsu, and Y.-W. Chang. Structure-aware placement for datapath-intensive circuit designs. In Proceedings of ACM/IEEE Design Automation Conference, pages 762-767, San Francisco, USA, Jun. 2012. [16] J. Cong and M. Romesis. Performance-driven multi-level clustering with application to hierarchical FPGA mapping. In Proceedings of ACM/IEEE Design Automation Conference, pages 389-394, Las Vegas, USA, Jun. 2001. [17] M. E. Dehkordi and S. D. Brown. Performance-driven recursive multilevel clustering. In Proceedings of IEEE International Conference on Field-Programmable Technology, pages 262-269, Tokyo, Japan, Dec. 2003. [18] W. Feng. K-way partitioning based packing for FPGA logic blocks without input bandwidth constraint. In Proceedings of IEEE International Conference on Field-Programmable Technology, pages 8-15, Seoul, South Korea, Dec. 2012. [19] M. R. Garey, D. S. Johnson, and L. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science, 1(3):237-267, Feb. 1976. [20] P. Gopalakrishnan, X. Li, and L. Pileggi. Architecture-aware FPGA placement using metric embedding. In Proceedings of ACM/IEEE Design Automation Conference, pages 460-465, San Francisco, USA, Jul. 2006. [21] M. Gort and J. H. Anderson. Analytical placement for heterogeneous FPGAs. In Proceedings of Field-Programmable Logic and Applications, pages 143-150, Oslo, Norway, Aug. 2012. [22] H. Hassan, M. Anis, and M. Elmasry. LAP: a logic activity packing methodology for leakage power-tolerant FPGAs. In Proceedings of International Symposium on Low Power Electronics and Design, pages 257-262, San Diego, USA, Aug. 2005. [23] S. Hauck and A. Dehon. Reconfigurable Computing. Morgan Kaufmann, 2008. [24] D. Hill. US patent 6,370,673: Method and system for high speed detailed placement of cells within an integrated circuit design. 2002. [25] M.-K. Hsu, Y.-W. Chang, and V. Balabanov. TSV-aware analytical placement for 3D IC designs. In Proceedings of ACM/IEEE Design Automation Conference, pages 664-669, San Diego, USA, Jun. 2011. [26] M.-K. Hsu, S. Chou, T.-H. Lin, and Y.-W. Chang. Routability-driven analytical placement for mixed-size circuit designs. In Proceedings of the International Conference on Computer-Aided Design, pages 80-84, San Jose, USA, Nov. 2010. [27] E. Hung, F. Eslami, and S. J. Wilton. Escaping the academic sandbox: realizing VPR circuits on xilinx devices. In Proceedings of Field-Programmable Custom Computing Machines, pages 45-52, Seattle, USA, Apr. 2013. [28] G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar. Multilevel hypergraph partitioning: applications in VLSI domain. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 7(1):69-79, Mar. 1999. [29] G. Karypis and V. Kumar. Multilevel k-way hypergraph partitioning. In Proceedings of ACM/IEEE Design Automation Conference, pages 343-348, New Orleans, USA, Jun. 1999. [30] M.-C. Kim, D.-J. Lee, and I. L. Markov. SimPL: an effective placement algorithm. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 31(1):50-60, Jan. 2012. [31] M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich. GORDIAN: VLSI placement by quadratic programming and slicing optimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 10(3):356-365, Mar. 1991. [32] T.-H. Lin, P. Banerjee, and Y.-W. Chang. An efficient and effective analytical placer for FPGAs. In Proceedings of ACM/IEEE Design Automation Conference, page 10, Austin, USA, Jun. 2013. [33] J. Luu, J. H. Anderson, and J. S. Rose. Architecture description and packing for logic blocks with hierarchy, modes and complex interconnect. In Proceedings of Symposium on Field Programmable Gate Arrays, pages 227-236, Monterey, USA, Feb. 2011. [34] J. Luu, I. Kuon, P. Jamieson, T. Campbell, A. Ye, W. M. Fang, K. Kent, and J. Rose. VPR 5.0: FPGA cad and architecture exploration tools with single-driver routing, heterogeneity and process scaling. ACM Transactions on Reconfigurable Technology and Systems, 4(4):32, Dec. 2011. [35] P. Maidee, C. Ababei, and K. Bazargan. Timing-driven partitioning-based placement for island style FPGAs. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 24(3):395-406, Mar. 2005. [36] V. Manohararajah, G. R. Chiu, D. P. Singh, and S. D. Brown. Difficulty of predicting interconnect delay in a timing driven FPGA CAD flow. In Proceedings of International Workshop on System Level Interconnect Prediction, pages 3-8, Munich, Germany, Mar. 2006. [37] A. Marquardt, V. Betz, and J. Rose. Timing-driven placement for FPGAs. In Proceedings of Symposium on Field Programmable Gate Arrays, pages 203-213, Monterey, USA, Feb. 2000. [38] A. S. Marquardt, V. Betz, and J. Rose. Using cluster-based logic blocks and timing-driven packing to improve FPGA speed and density. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 12(3):288-298, Apr. 1999. [39] Z. Marrakchi, H. Mrabet, and H. Mehrez. Hierarchical FPGA clustering based on multilevel partitioning approach to improve routability and reduce power dissipation. In Proceedings of International Conference on Reconfigurable Computing and FPGAs, pages 4-25, Puebla, Mexico, Sep. 2005. [40] F. Mo, A. Tabbara, and R. K. Brayton. A force-directed macro-cell placer. In Proceedings of IEEE/ACM International Conference on Computer-Aided Design, pages 177-181, San Jose, USA, Nov. 2000. [41] K. E. Murray, S. Whitty, S. Liu, J. Luu, and V. Betz. Titan: enabling large and complex benchmarks in academic CAD. In Proceedings of Field-Programmable Logic and Applications, pages 1-8, Porto, Portugal, Sep. 2013. [42] W. C. Naylor, R. Donelly, and L. Sha. US patent 6,301,693: Non-linear optimization system and method for wire length and delay optimization for an automatic electric circuit placer. 2001. [43] A. Pandit, L. Easwaran, and A. Akoglu. Concurrent timing based and routability driven depopulation technique for FPGA packing. In Proceedings of IEEE International Conference on Field-Programmable Technology, pages 325-328, Taipei, Taiwan, Dec. 2008. [44] S. T. Rajavel and A. Akoglu. Mo-pack: many-objective clustering for FPGA CAD. In Proceedings of ACM/IEEE Design Automation Conference, pages 818-823, San Diego, USA, Jun. 2011. [45] G. Sigl, K. Doll, and F. M. Johannes. Analytical placement: A linear or a quadratic objective function? In Proceedings of ACM/IEEE Design Automation Conference, pages 427-432, San Francisco, USA, Jun. 1991. [46] A. Singh, G. Parthasarathy, and M. Marek-Sadowska. Efficient circuit clustering for area and power reduction in FPGAs. ACM Transactions on Design Automation of Electronic Systems, 7(4):643-663, Feb. 2002. [47] C. N. Sze, T.-C. Wang, and L.-C. Wang. Multilevel circuit clustering for delay minimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 23(7):1073-1085, Jun. 2004. [48] D. Xie, J. Xu, and J. Lai. A new FPGA placement algorithm for heterogeneous resources. In Proceedings of ACIS International Conference on Computer and Information Science, pages 742-746, Changsha, China, Oct. 2009. [49] M. Xu, G. Gr_ewal, and S. Areibi. StarPlace: A new analytic method for FPGA placement. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 44(3):192-204, Feb. 2011. [50] Y. Xu and M. Khalid. QPF: efficient quadratic placement for FPGAs. In Proceedings of Field-Programmable Logic and Applications, pages 555-558, Tampere, Finland, Aug. 2005. [51] M. Yang, H. Xu, and A. Almaini. Power-aware FPGA packing algorithm. In Proceedings of ACIS International Conference on Computer and Information Science, pages 817-819, Changsha, China, Oct. 2009. [52] A. G. Ye and J. Rose. Using multi-bit logic blocks and automated packing to improve field-programmable gate array density for implementing datapath circuits. In Proceedings of IEEE International Conference on Field-Programmable Technology, pages 129-136, Brisbane, Australia, Dec. 2004. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/5448 | - |
dc.description.abstract | 隨著現場可程式邏輯閘陣列的演進,其晶片大量採用複雜元件如隨機存取記憶體以及數位訊號處理器以實現當代電路設計廣泛使用的矽智產。而複雜元件電路往往伴隨著資料路徑。在過去,電路巨集與擺置的問題雖然已被廣泛研究,資料路徑電路在電路巨集與擺置上的考量卻大多被忽視。然而,未考慮資料路徑之巨集與擺置將破壞電路的規律性,從而降低效能。除此之外,隨著電路設計複雜度的急遽上升,可擴展性已成為主要考量。另外,多數巨集之演算法過度聚集元件,也造成擺置上的困難並限制了擺置的最佳化。然而,學術界廣為使用的標竿電路卻遠小於現實電路,不足以顯現出演算法之可擴展性。
因此,在這篇論文中,我們針對上述問題提出了一個考慮密集資料路徑結構的巨集與擺置演算法。我們所提出的巨集演算法針對複雜元件、資料路徑以及一般元件分別採用不同的巨集方法。我們的巨集方法提供後續的擺置更大的彈性和潛力以得到更好的最佳化。此外,我們提出V型架構來加強演算法的可擴展性。而我們所提出的擺置演算法使用非線性最佳化的方式降低線長並針對密集資料路徑結構作處理 以獲得高品質的擺置。實驗結果顯示出,我們所提出的方法相較於先前的研究,可以有效地得到非常好的電路擺置結果,並且可以在大型異質標竿電路中得到驗證。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-05-15T17:59:10Z (GMT). No. of bitstreams: 1 ntu-103-R00943096-1.pdf: 1546208 bytes, checksum: 165891187b7876c107ad728bdb82f6b0 (MD5) Previous issue date: 2014 | en |
dc.description.tableofcontents | Acknowledgements ii
Abstract (Chinese) iii Abstract v List of Tables ix List of Figures x Chapter 1. Introduction 1 1.1 Introduction to FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 FPGA Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 FPGA Design Flow . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Datapath Circuit in FPGA . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 FPGA Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4 FPGA Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.6 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.7 Our Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.8 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 Chapter 2. Preliminaries 20 2.1 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.2 Analytical Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2.1 Wirelength Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2.2 Density Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 Chapter 3. The Heterogeneous Packing and Placement Algorithms 26 3.1 Algorithm Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.2 Heterogeneous Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 3.2.1 Identification Packing . . . . . . . . . . . . . . . . . . . . . . . . . 29 3.2.2 Datapath Extraction and Packing . . . . . . . . . . . . . . . . . . 30 3.2.3 General Logic Packing . . . . . . . . . . . . . . . . . . . . . . . . 33 3.2.3.1 Affinity Calculation . . . . . . . . . . . . . . . . . . . . . . 33 3.2.3.2 Packing Order . . . . . . . . . . . . . . 34 3.2.4 V-Shaped Framework . . . . . . . . . . . . . . . . . . . . . . . . . 35 3.3 Heterogeneous Analytical Placement . . . . . . . . . . . . . . . . . . . . 36 3.3.1 Multilevel Mixed-Size Prototyping . . . . . . . . . . . . . . . . . . 37 3.3.2 Look-Ahead Legalization . . . . . . . . . . . . . . . . . . . . . . . 41 3.3.3 Datapath Placement . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.3.4 General Logic Refinement . . . . . . . . . . . . . . . . . . . . . . 43 3.3.5 Detailed Placement . . . . . . . . . . . . . . . . . . . . . . . . . . 45 Chapter 4. Experimental Results 46 Chapter 5. Conclusions and Future Work 55 Bibliography 57 | |
dc.language.iso | en | |
dc.title | 針對大型異質現場可程式化邏輯閘陣列之巨集暨解析擺置 | zh_TW |
dc.title | Packing and Analytical Placement for Large-Scale Heterogeneous FPGAs | en |
dc.type | Thesis | |
dc.date.schoolyear | 102-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 陳宏明(Hung-Ming Chen),黃世旭(Shih-Hsu Huang),黃俊郎(Jiun-Lang Huang) | |
dc.subject.keyword | 實體設計,資料路徑,電路巨集,電路擺置,異質電路, | zh_TW |
dc.subject.keyword | Physical Design,Datapath,Packing,Placement,Heterogeneous, | en |
dc.relation.page | 64 | |
dc.rights.note | 同意授權(全球公開) | |
dc.date.accepted | 2014-02-13 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電子工程學研究所 | zh_TW |
顯示於系所單位: | 電子工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-103-1.pdf | 1.51 MB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。