Reconfigurable Computing marks a revolutionary and hot topic that bridges the gap between the separate worlds of hardware and software design- the key feature of reconfigurable computing is its groundbreaking ability to perform computations in hardware to increase performance while retaining the flexibility of a software solution. Reconfigurable computers serve as affordable, fast, and accurate tools for developing designs ranging from single chip architectures to multi-chip and embedded systems.
Scott Hauck and Andre DeHon have assembled a group of the key experts in the fields of both hardware and software computing to provide an introduction to the entire range of issues relating to reconfigurable computing. FPGAs (field programmable gate arrays) act as the "computing vehicles to implement this powerful technology. Readers will be guided into adopting a completely new way of handling existing design concerns and be able to make use of the vast opportunities possible with reconfigurable logic in this rapidly evolving field.
- Designed for both hardware and software programmers
- Views of reconfigurable programming beyond standard programming languages
- Broad set of case studies demonstrating how to use FPGAs in novel and efficient ways
Inhaltsverzeichnis
1;Front Cover;1 2;Reconfigurable Computing;4 3;Copyright Page;5 4;Table of Contents;6 5;List of Contributors;21 6;Preface;24 7;Introduction;26 8;Part I: Reconfigurable Computing Hardware;32 8.1;Chapter 1. Device Architecture;34 8.1.1;1.1 LogicThe Computational Fabric;34 8.1.2;1.2 The Array and Interconnect;37 8.1.3;1.3 Extending Logic;43 8.1.4;1.4 Configuration;47 8.1.5;1.5 Case Studies;49 8.1.6;1.6 Summary;57 8.1.7;References;58 8.2;Chapter 2. Reconfigurable Computing Architectures;60 8.2.1;2.1 Reconfigurable Processing Fabric Architectures;61 8.2.2;2.2 RPF Integration into Traditional Computing Systems;66 8.2.3;2.3 Summary and Future Work;75 8.2.4;References;76 8.3;Chapter 3. Reconfigurable Computing Systems;78 8.3.1;3.1 Early Systems;78 8.3.2;3.2 PAM, VCC, and Splash;80 8.3.3;3.3 Small-Scale Reconfigurable Systems;83 8.3.4;3.4 Circuit Emulation;85 8.3.5;3.5 Accelerating Technology;87 8.3.6;3.6 Reconfigurable Supercomputing;90 8.3.7;3.7 Non-FPGA Research;92 8.3.8;3.8 Other System Issues;92 8.3.9;3.9 The Future of Reconfigurable Systems;93 8.3.10;References;94 8.4;Chapter 4. Reconfiguration Management;96 8.4.1;4.1 Reconfiguration;97 8.4.2;4.2 Configuration Architectures;97 8.4.3;4.3 Managing the Reconfiguration Process;107 8.4.4;4.4 Reducing Configuration Transfer Time;111 8.4.5;4.5 Configuration Security;113 8.4.6;4.6 Summary;114 8.4.7;References;115 9;Part II: Programming Reconfigurable Systems;118 9.1;Chapter 5. Compute Models and System Architectures;122 9.1.1;5.1 Compute Models;124 9.1.2;5.2 System Architectures;138 9.1.3;References;156 9.2;Chapter 6. Programming FPGA Applications in VHDL;160 9.2.1;6.1 VHDL Programming;161 9.2.2;6.2 Hardware Compilation Flow;181 9.2.3;6.3 Limitations of VHDL;184 9.2.4;References;184 9.3;Chapter 7. Compiling C for Spatial Computing;186 9.3.1;7.1 Overview of How C Code Runs on Spatial Hardware;187 9.3.2;7.2 Automatic Compilation;193 9.3.3;7.3 Uses and Variations of C Compilation to Hardware;206 9.3.4;7.4 Summary;211 9.3.5;Refere
nces;211 9.4;Chapter 8. Programming Streaming FPGA Applications Using Block Diagrams in Simulink;214 9.4.1;8.1 Designing High-Performance Datapaths Using Stream-Based Operators;215 9.4.2;8.2 An Image-Processing Design Driver;216 9.4.3;8.3 Specifying Control in Simulink;225 9.4.4;8.4 Component Reuse: Libraries of Simple and Complex Subsystems;229 9.4.5;8.5 Summary;232 9.4.6;References;233 9.5;Chapter 9. Stream Computations Organized for Reconfigurable Execution;234 9.5.1;9.1 Programming;236 9.5.2;9.2 System Architecture and Execution Patterns;239 9.5.3;9.3 Compilation;243 9.5.4;9.4 Runtime;244 9.5.5;9.5 Highlights;248 9.5.6;References;248 9.6;Chapter 10. Programming Data Parallel FPGA Applications Using the SIMD/Vector Model;250 9.6.1;10.1 SIMD Computing on FPGAs: An Example;250 9.6.2;10.2 SIMD Processing Architectures;252 9.6.3;10.3 Data Parallel Languages;253 9.6.4;10.4 Reconfigurable Computers for SIMD/Vector Processing;254 9.6.5;10.5 Variations of SIMD/Vector Computing;257 9.6.6;10.6 Pipelined SIMD/Vector Processing;259 9.6.7;10.7 Summary;260 9.6.8;References;261 9.7;Chapter 11. Operating System Support for Reconfigurable Computing;262 9.7.1;11.1 History;263 9.7.2;11.2 Abstracted Hardware Resources;265 9.7.3;11.3 Flexible Binding;267 9.7.4;11.4 Scheduling;270 9.7.5;11.5 Communication;274 9.7.6;11.6 Synchronization;279 9.7.7;11.7 Protection;280 9.7.8;11.8 Summary;283 9.7.9;References;283 9.8;Chapter 12. The JHDL Design and Debug System;286 9.8.1;12.1 JHDL Background and Motivation;286 9.8.2;12.2 The JHDL Design Language;288 9.8.3;12.3 The JHDL CAD System;296 9.8.4;12.4 JHDL'S Hardware Mode;299 9.8.5;12.5 Advanced JHDL Capabilities;300 9.8.6;12.6 Summary;303 9.8.7;References;304 10;Part III: Mapping Designs to Reconfigurable Platforms;306 10.1;Chapter 13. Technology Mapping;308 10.1.1;13.1 Structural Mapping Algorithms;309 10.1.2;13.2 Integrated Mapping Algorithms;315 10.1.3;13.3 Mapping Algorithms for Heterogeneous Resources;320 10.1.4;13.4 Summary;324 10.1.5;Refe
rences;324 10.2;FPGA Placement;328 10.3;Chapter 14. Placement for General-purpose FPGAs;330 10.3.1;14.1 The FPGA Placement Problem;330 10.3.2;14.2 Clustering;335 10.3.3;14.3 Simulated Annealing for Placement;337 10.3.4;14.4 Partition-Based Placement;343 10.3.5;14.5 Analytic Placement;346 10.3.6;14.6 Further Reading and Open Challenges;347 10.3.7;References;347 10.4;Chapter 15. Datapath Composition;350 10.4.1;15.1 Fundamentals;350 10.4.2;15.2 Tool Flow Overview;354 10.4.3;15.3 The Impact of Device Architecture;355 10.4.4;15.4 The Interface to Module Generators;357 10.4.5;15.5 The Mapping;360 10.4.6;15.6 Placement;364 10.4.7;15.7 Compaction;368 10.4.8;15.8 Summary and Future Work;375 10.4.9;References;375 10.5;Chapter 16. Specifying Circuit Layout on FPGAs;378 10.5.1;16.1 The Problem;378 10.5.2;16.2 Explicit Cartesian Layout Specification;382 10.5.3;16.3 Algebraic Layout Specification;383 10.5.4;16.4 Layout Verification for Parameterized Designs;391 10.5.5;16.5 Summary;393 10.5.6;References;394 10.6;Chapter 17. PathFinder: A Negotiation-based, Performance-driven Router for FPGAs;396 10.6.1;17.1 The History of PathFinder;397 10.6.2;17.2 The PathFinder Algorithm;398 10.6.3;17.3 Enhancements and Extensions to PathFinder;405 10.6.4;17.4 Parallel PathFinder;408 10.6.5;17.5 Other Applications of the PathFinder Algorithm;410 10.6.6;17.6 Summary;410 10.6.7;References;411 10.7;Chapter 18. Retiming, Repipelining, and C-slow Retiming;414 10.7.1;18.1 Retiming: Concepts, Algorithm, and Restrictions;415 10.7.2;18.2 Repipelining and C-slow Retiming;419 10.7.3;18.3 Implementations of Retiming;424 10.7.4;18.4 Retiming on Fixed-Frequency FPGAs;425 10.7.5;18.5 C-slowing as Multi-Threading;426 10.7.6;18.6 Why Isnt Retiming Ubiquitous?;429 10.7.7;References;429 10.8;Chapter 19. Configuration Bitstream Generation;432 10.8.1;19.1 The Bitstream;434 10.8.2;19.2 Downloading Mechanisms;437 10.8.3;19.3 Software to Generate Configuration Data;438 10.8.4;19.4 Summary;440 10.8.5;References;440 10.9
;Chapter 20. Fast Compilation Techniques;442 10.9.1;20.1 Accelerating Classical Techniques;445 10.9.2;20.2 Alternative Algorithms;453 10.9.3;20.3 Effect of Architecture;458 10.9.4;20.4 Summary;462 10.9.5;References;463 11;Part IV: Application Development;466 11.1;Chapter 21. Implementing Applications with FPGAs;470 11.1.1;21.1 Strengths and Weaknesses of FPGAs;470 11.1.2;21.2 Application Characteristics and Performance;472 11.1.3;21.3 General Implementation Strategies for FPGA-based Systems;476 11.1.4;21.4 Implementing Arithmetic in FPGAs;479 11.1.5;21.5 Summary;483 11.1.6;References;483 11.2;Chapter 22. Instance-specific Design;486 11.2.1;22.1 Instance-specific Design;486 11.2.2;22.2 Partial Evaluation;493 11.2.3;22.3 Summary;504 11.2.4;References;504 11.3;Chapter 23. Precision Analysis for Fixed-point Computation;506 11.3.1;23.1 Fixed-point Number System;506 11.3.2;23.2 Peak Value Estimation;509 11.3.3;23.3 Wordlength Optimization;516 11.3.4;23.4 Summary;529 11.3.5;References;530 11.4;Chapter 24. Distributed Arithmetic;534 11.4.1;24.1 Theory;534 11.4.2;24.2 DA Implementation;535 11.4.3;24.3 Mapping DA onto FPGAs;538 11.4.4;24.4 Improving DA Performance;539 11.4.5;24.5 An Application of DA on an FPGA;542 11.4.6;References;542 11.5;Chapter 25. Cordic Architectures for FPGA Computing;544 11.5.1;25.1 Cordic Algorithm;545 11.5.2;25.2 Architectural Design;557 11.5.3;25.3 FPGA Implementation of Cordic Processors;558 11.5.4;25.4 Summary;565 11.5.5;References;566 11.6;Chapter 26. Hardware/Software Partitioning;570 11.6.1;26.1 The Trend Toward Automatic Partitioning;571 11.6.2;26.2 Partitioning of Sequential Programs;573 11.6.3;26.3 Partitioning of Parallel Programs;588 11.6.4;26.4 Summary and Directions;589 11.6.5;References;590 12;Part V: Case Studies of FPGA Applications;592 12.1;Chapter 27. Spiht Image Compression;596 12.1.1;27.1 Background;596 12.1.2;27.2 Spiht Algorithm;597 12.1.3;27.3 Design Considerations and Modifications;602 12.1.4;27.4 Hardware Implementation;611
12.1.5;27.5 Design Results;618 12.1.6;27.6 Summary and Future Work;619 12.1.7;References;620 12.2;Chapter 28. Automatic Target Recognition Systems on Reconfigurable Devices;622 12.2.1;28.1 Automatic Target Recognition Algorithms;623 12.2.2;28.2 Dynamically Reconfigurable Designs;625 12.2.3;28.3 Reconfigurable Static Design;631 12.2.4;28.4 ATR Implementations;635 12.2.5;28.5 Summary;640 12.2.6;References;641 12.3;Chapter 29. Boolean Satisfiability: Creating Solvers Optimized for Specific Problem Instances;644 12.3.1;29.1 Boolean Satisfiability Basics;644 12.3.2;29.2 Sat-solving Algorithms;646 12.3.3;29.3 A Reconfigurable SAT Solver Generated According to an SAT Instance;649 12.3.4;29.4 A Different Approach to Reduce Compilation Time and Improve Algorithm Efficiency;658 12.3.5;29.5 Discussion;664 12.3.6;References;666 12.4;Chapter 30. Multi-FPGA Systems: Logic Emulation;668 12.4.1;30.1 Background;668 12.4.2;30.2 Uses of Logic Emulation Systems;670 12.4.3;30.3 Types of Logic Emulation Systems;671 12.4.4;30.4 Issues Related to Contemporary Logic Emulation;681 12.4.5;30.5 The Need for Fast FPGA Mapping;683 12.4.6;30.6 Case Study: The Virtualogic VLE Emulation System;684 12.4.7;30.7 Future Trends;697 12.4.8;30.8 Summary;698 12.4.9;References;699 12.5;Chapter 31. The Implications of Floating Point for FPGAs;702 12.5.1;31.1 Why is Floating Point Difficult?;702 12.5.2;31.2 Floating-point Application Case Studies;710 12.5.3;31.3 Summary;723 12.5.4;References;725 12.6;Chapter 32. Finite Difference Time Domain: A Case Study Using FPGAs;728 12.6.1;32.1 The FDTD Method;728 12.6.2;32.2 FDTD Hardware Design Case Study;738 12.6.3;32.3 Summary;754 12.6.4;References;754 12.7;Chapter 33. Evolvable FPGAs;756 12.7.1;33.1 The Poe Model of Bioinspired Design Methodologies;756 12.7.2;33.2 Artificial Evolution;758 12.7.3;33.3 Evolvable Hardware;760 12.7.4;33.4 Evolvable Hardware: A Taxonomy;764 12.7.5;33.5 Evolvable Hardware Digital Platforms;770 12.7.6;33.6 Conclusions and Future Direction
s;776 12.7.7;References;778 12.8;Chapter 34. Network Packet Processing in Reconfigurable Hardware;784 12.8.1;34.1 Networking with Reconfigurable Hardware;784 12.8.2;34.2 Network Protocol Processing;788 12.8.3;34.3 Intrusion Detection and Prevention;793 12.8.4;34.4 Semantic Processing;798 12.8.5;34.5 Complete Networking System Issues;801 12.8.6;34.6 Summary;806 12.8.7;References;807 12.9;Chapter 35. Active Pages:Memory-centric Computation;810 12.9.1;35.1 Active Pages;810 12.9.2;35.2 Performance Results;812 12.9.3;35.3 Algorithmic Complexity;817 12.9.4;35.4 Exploring Parallelism;825 12.9.5;35.5 Defect Tolerance;830 12.9.6;35.6 Related Work;832 12.9.7;35.7 Summary;833 12.9.8;References;833 13;Part VI: Theoretical Underpinnings and Future Directions;836 13.1;Chapter 36. Theoretical Underpinnings;838 13.1.1;36.1 General Computational Array Model;838 13.1.2;36.2 Implications of the General Model;840 13.1.3;36.3 Induced Architectural Models;845 13.1.4;36.4 Modeling Architectural Space;847 13.1.5;36.5 Implications;857 13.1.6;References;859 13.2;Chapter 37. Defect and Fault Tolerance;860 13.2.1;37.1 Defects and Faults;861 13.2.2;37.2 Defect Tolerance;861 13.2.3;37.3 Transient Fault Tolerance;874 13.2.4;37.4 Lifetime Defects;879 13.2.5;37.5 Configuration Upsets;880 13.2.6;37.6 Outlook;881 13.2.7;References;882 13.3;Chapter 38. Reconfigurable Computing and Nanoscale Architecture;884 13.3.1;38.1 Trends in Lithographic Scaling;885 13.3.2;38.2 Bottom-up Technology;886 13.3.3;38.3 Challenges;889 13.3.4;38.4 Nanowire Circuits;890 13.3.5;38.5 Statistical Assembly;893 13.3.6;38.6 Nanopla Architecture;895 13.3.7;38.7 Nanoscale Design Alternatives;901 13.3.8;38.8 Summary;903 13.4;References;904 14;Index;908