Academic Packing for Commercial FPGA Architectures

文件名称: Academic Packing for Commercial FPGA Architectures 2017.pdf

所属分类: 硬件开发

开发工具:

文件大小: 1mb

下载次数: 0

上传时间: 2019-08-17

提供者: fengji******

下载 (1mb)

不能下载？报告错误

详细说明：With a few exceptions, academic packing algorithms for FPGAs are typically applied solely to theoretical architectures. This has allowed the algorithms to focus on the basic components of packing while abstracting away many of the details dictated by real hardware. As commercially available FPGAs haABSTRACT Academic Packing for Commercial FPGA architectures Travis d. haroldson Department of Electrical and Computer Engineering, BYU Doctor of philosophy With a few exceptions, academic packing algorithms for FPGAs are typically applied solely to theoretical architectures. This has allowed the algorithms to focus on the basic components of packing while abstracting away many of the details dictated by real hardware. As commercially available fpgas have advanced. however, the academic algorithms and architectures haye di- verged significantly from thcir commcrcial counterpart In this dissertation, the RapidSmith 2 framework is presented. This framework accurately reflects the architecture of Xilinx FPGAs and provides support for integrating custom tools into the commercial CAD tools. USing this framework, the rsvPack packing algorithm is implemented The rsvpack algorithm can accept a design synthesized using the commercial Xilinx cad tools pack designs which make use of the many features of commercial FPGA architectures and return the packed designs to the Xilinx Cad tools to be placed and routed in their software. This enables researchers to isolate the packing portion of the algorithm from the commercial flow and evalu ate different packing techniques while allowing the high-quality commercial tools to perform the remainder of the flow Integrating the rsvPack algorithm the commercial flow shows RSVPack produces packing which lead to circuits with minimum clock periods within 10%0, on average, of circuits generated using the pure Xilinx flow Included in this work is a novel table lookup-based algorithm which RSVPack utilizes to quickly determine the routability of a cluster. This algorithm performs 5 times faster on average than the current academic alternatives. Finally, using rsVPack, this dissertation explores various techniques for improving the quality of packing for Xilinx circuits. Together, this demonstrates the potential for academic research into FPGA CAD tools for commercial architectures Keywords: FPGA, packing, Xilinx, algorithms ACKNOWLEDGMENTS This path has taken far longer than I imagined when I started back in 2011. First and foremost, I need to express profound gratitude to my wife, Amanda. Even with the countless late nights and the many Saturdays that I have spent on campus instead of with her and our children, she has been amazingly patient and supportive of me throughout this entire process. I would also like to thank my children for their patience and bright smiles that always bring me cheer. I express gratitude to my parents. From my childhood, they have instilled in me a love and respect for learning that has enabled me through this work I would also like to recognize my colleagues I have worked with in the Configurable Com- puting Laboratory. I have enjoyed the many conversations I have had with them and each of them has made the work more enjoyable. In particular, I would like to acknowledge Josh Monson and Jon-Paul Anderson who have been some of the few constants throughout my studies. I appreci- ate the advice and recommendations both have freely offered me. I would also like to single out Thomas Townsend whose help has been instrumental in preparing RapidSmith 2 for public release I would like to thank my adviser, Brent Nelson. I appreciate his patience and the counsel he has provided at times when the path forward looked hopeless. Lastly, I would like to thank brad Hutchings who for the last couple of years has served as a second adviser to me. I appreciate his input and the insights he has brought as i have pursued my studies I This work was supported in part by the I/UCRC Program of the National Science Foundation within the NSF Center for High-Performance Reconfigurable Computing(CHREC), Grant No. 1265957 TABLE OF CONTENTS List of Tables List of Figures VI Chapter 1 Introduction 1.1 Contributions of this work 4 1.2 Dissertation Organization Chapter 2 Background and related Work 2.1 Xilinx FPGa architecture 2.1.1 Tiles 2.1.2 Sites 8 2.2 FPGA CAD Flow 2.2.1 Traditional cad flow 2. 2.2 Xilinx IsE Cad flow 13 2.2.3 Academic CAD Frameworks 14 224 Academic Packing Algorithms··. .16 2. 3 Xilinx Design Language and rapidsmith 18 2.3.1 XDLRC File Format 2.3.2XDL 19 2.3.3 XDL/ISE Interoperability 20 2.3.4 Rapidsmith 1 21 Chapter 3 Rapidsmith 2 23 3.1 Subsite Device representation 24 3.1. Building Site Templates 25 3.2 Design netlist 28 3.2.1 Route Trees 29 3.3 XDL Compatibility 30 3.3.1 Integrating Custom Packers into IsE with RapidSmith 2 32 3.3.2 Non-Xilinx Architectures in RapidSmith 2 32 Chapter 4 RSVPack: A Packer for Xilinx FPGAs 33 4.1 RSVPack overview 34 4.1.1 Pack Units 34 4.2 RSVPack Algorithm 35 4. 2. 1 Seeding clusters 35 4.2.2 Seeding a cluster 35 4.2.3 Cluster Legality validation 38 4.2.4 Conditional mode 44 4.2.5 Manual Pairing of LUTs and FFs 45 4.3 Table-Lookup routing Fcasibility Improvement 46 4.3.1 Routing Feasibility: VTRS AAPack versus RSVPack 46 4.4 dentifying packing Rulcs for Xilinx Architectur·· 4.3.2 Run Time Improvement 4 51 4.5 Integrating rsvPack into the Xilinx ISE CAD Flow .52 4.5.1 Pure ise flows 53 4.5.2 RSX Flow 54 4.53 RSV flow 54 4.6 RSVPack performance 4.6.1 Benchmark set 55 4.6.2 RSVPack results 56 4.6.3 Summary Chapter 5 Experimenting with Packing Xilinx FPGAs Using RSVPack 61 5.1 Experiment 1: Impact of Packing on Circuit Quality 5.1.1 Experiment setup 61 5.1.2 Rcsults 62 5.2 Experiment 2: Cluster Underutilization 5.2.1 Two-Hop Deep Cell selector 65 2 Experiment Setup 66 5.2.3 Results and conclusion .,.66 5.3 Experiment 3 Tile Versus Site Level Packing 67 5.3.1 Back ground 68 5.3.2 Experiment Setup 5.3.3 Results and analysis 70 5.3.4 Experiment Conclusions 73 5.4 Summary 74 Chapter 6 Conclusion 75 6. 1 Summary of rcscarch 75 6.2 Future Work 76 REFERENCES 78 ppendix a Publications and Documentation 84 Appendix b rapidsmith 2 Changelist 85 Appendix C Xdl-Unpacking and XDL-Packing algorithms 86 C1 Design Unpacking 86 C2 XDL-Packing 88 Appendix d Checks Required for Packing for a Virtex 6 Device 92 LIST OF TABLES 2.1 CAD Flow Stage Inputs and Outputs 4.1 Routing Connectivity Lookup Table for Figure 4.7a 48 4.2 Average Runtimes for Each Outcome of routing Fcasibility Checking(in microseconds) 50 4.3 Benchmarks Used to Analyze rsvPack 55 4.4 Number of Used Slices and Percent of Lut5s Merged 56 4.5 Clustering of LUT/FF Pairs and Nets Exposed From Slices 57 4.6 Minimum Periods of Benchmarks Implemented with Different Flows(in ns) 58 4.7 Total Wire Length of benchmarks Implemented with Different Flows (in Thousands of Tiles travelled 58 4.8 Implementation Runtimes for each Flow in Seconds(Median of 20 runs) 60 5.1 Influence of 2-Hop Deep cell Selector on Benchmarks 66 5.2 Used Slices for Rsv-Site and rsV-Tile Implemented Benchmarks 70 5.3 HPWL, Used Wire Length, and Minimum Periods of rsv-Site and rsv-Tile Imple mented Benchmarks 70 5.4 Run Times for rsv-Tile and rsv-Site in Seconds 72 5.5 Used Wirc Length and minimum Periods of rsX-Sitc and rsX-Tilc Implemented Benchmarks 72 LIST OF FIGURES 1.1 A Traditional Academic le(1.la)vs a virtex 6 le (1.1b) 1. 2 The Traditional Cad Flow 3 2.1 Hicrarchy of a Xilinx Tile 2. 2 Device arranged as a grid of Tiles 2.3 Connectivity Inside a Switch Box 6789 2. 4 A Xilinx Virtex 6 CLB and adjacent Switch Box 2.5 A Xilinx Virtex 6 Logic Element 2.6 Correspondence between the Traditional and Xilinx ISE CAd Flows 12 2.7 Sample of an XDlRc Device description 2.8 A 4-Bit Adder Netlist(a) and its XDL Representation(b) 20 2.9 Steps in the Ise Tool Chain Where Designs can be Converted to XDL 21 3.1 The Extended Device Representation in RapidSmith 2 24 3.2 The Site Level Hierarchy(shaded) of Xilinx FPGAs 25 3.3 An XDLRC Primitive_def (left)with its Rapid Smith 2 Representation (right)...... 26 3.4 A Polarity Mux Schematic(left) and its XDLRC Representation (right) 28 3.5 Rclationship Betwccn RapidSmith 2 Nctlist API Classes 29 3.6 Subsite and Intersite Sections of a route tree 30 3.7 Converting Between an XDL Instance and rs2's Cell-Based Netlist 30 3.8 Flow for a Custom Packer Using rapidSmith 2 32 4.1 Possible Invalid Packings for Clustcrs With Multiple Carry Chains 39 4.2 Examples of Legal and Illegal Fracturable LUT Usage 42 4.3 Example of an aslut that must be conditionally packed with a carry chain 43 4.4 Carry chain element using both do and co pins must be packed with a FF 43 4.5 Example of Entering and Resolving Conditional Mode 44 4.6 Example of packing lut/Ff Pairs Together 45 4.7 Example for Determining Routing Feasibility 48 4.8 Projected Run Times Using Pin Counting 50 4.9 Implementation Flows used in this work 53 4.10 Densities of Slices Packed with Xilinx and rsvPack(average of benchmarks 57 5.1 Average Increase in Minimum Period Against Packing Quality 62 5.2 Average Increase in Wire Length Against Packing Quality 63 5.3 Progression of Packing Density of Clusters over Packing Process .64 5.4 Example of a Pocket Forming Around a Cell (B) during Packing 64 5.5 Utilization of LEs in Slices when Using Single-Hop and Two-Hop Cell Selectors 67 5.6 Progression of Packing Density of Clusters over Packing Process with Two-Hop Cell elector 67 5.7 Flows for Comparing Tile-Level and Site-Level Based Packing 69 5. 8 Non-Overlapping Carry Chains Paired Together in a ClB 74 C 1 Converting between XDL and rapidsmith 2 with the design- Unpacker 86 C 2 A BEL entry in the unpack xm1 87 C. 3 A BEL entry in the pack. xml 90 ChAPTER 1. INTRODUCTION Publicly available research into FPGA CAD algorithms and frameworks is important in opening up exploration of novel concepts relating to the FPGa cad flow to the academic research community. The availability of this information and these tools enables new techniques to both the general Cad flow as well as special applications, such as fPga reliability and security that may not be addressed by the fpga vendor tools. because the commercial vendors do not release their algorithms and internal tools to the public, it is necessary for people interested in researching new algorithms and flows to develop their own tools. For the remainder of this dissertation, the public information on Cad tools available in the public research literature will be referred to as academic Academic research into Cad algorithms for commercial fPga architectures has been hin dered by a lack of CAD infrastructure for these devices. As commercial architectures have added advanced features and capabilities to the configurable logic blockS(ClBs), academic frameworks and algorithms have settled for working with FPGa architectures, like those used in [l that re scmble less and less the architectures available from the commercial vendor The traditional architecture used in academic research is comprised of a collection of clbs made up of multiple lutynip-flop(FF)pairs, called logic elements or LEs, like the one shown in Figure 1.la. In contrast, the LEs found in recent commercial architectures, like the one in Figure 1.1b, contain many special- purpose components connected with sophisticated routing and often interact with other LEs in the same ClB. Additionally, each of the lEs in the clBs in these architecture have slight variations leading to an irregular structure in how they interconnect Packing algorithms for FPGAs are especially affected by the added complexity of the CLBs. Packing is a step in the traditional FPGA CAd flow(Figure 1.2)and which is respon sible for assembling the LUTs, FFs, and other basic components into relatively-placed structures called clusters, that map onto the CLBs. Packing is, therefore, responsible for handling the highly-

(系统自动生成,下载前可以参看下载内容)