Reconfigurable Computing (eBook)

Front Cover 1
Reconfigurable Computing 4
Copyright Page 5
Table of Contents 6
List of Contributors 21
Preface 24
Introduction 26
Part I: Reconfigurable Computing Hardware 32
Chapter 1. Device Architecture 34
1.1 Logic—The Computational Fabric 34
1.2 The Array and Interconnect 37
1.3 Extending Logic 43
1.4 Configuration 47
1.5 Case Studies 49
1.6 Summary 57
References 58
Chapter 2. Reconfigurable Computing Architectures 60
2.1 Reconfigurable Processing Fabric Architectures 61
2.2 RPF Integration into Traditional Computing Systems 66
2.3 Summary and Future Work 75
References 76
Chapter 3. Reconfigurable Computing Systems 78
3.1 Early Systems 78
3.2 PAM, VCC, and Splash 80
3.3 Small-Scale Reconfigurable Systems 83
3.4 Circuit Emulation 85
3.5 Accelerating Technology 87
3.6 Reconfigurable Supercomputing 90
3.7 Non-FPGA Research 92
3.8 Other System Issues 92
3.9 The Future of Reconfigurable Systems 93
References 94
Chapter 4. Reconfiguration Management 96
4.1 Reconfiguration 97
4.2 Configuration Architectures 97
4.3 Managing the Reconfiguration Process 107
4.4 Reducing Configuration Transfer Time 111
4.5 Configuration Security 113
4.6 Summary 114
References 115
Part II: Programming Reconfigurable Systems 118
Chapter 5. Compute Models and System Architectures 122
5.1 Compute Models 124
5.2 System Architectures 138
References 156
Chapter 6. Programming FPGA Applications in VHDL 160
6.1 VHDL Programming 161
6.2 Hardware Compilation Flow 181
6.3 Limitations of VHDL 184
References 184
Chapter 7. Compiling C for Spatial Computing 186
7.1 Overview of How C Code Runs on Spatial Hardware 187
7.2 Automatic Compilation 193
7.3 Uses and Variations of C Compilation to Hardware 206
7.4 Summary 211
References 211
Chapter 8. Programming Streaming FPGA Applications Using Block Diagrams in Simulink 214
8.1 Designing High-Performance Datapaths Using Stream-Based Operators 215
8.2 An Image-Processing Design Driver 216
8.3 Specifying Control in Simulink 225
8.4 Component Reuse: Libraries of Simple and Complex Subsystems 229
8.5 Summary 232
References 233
Chapter 9. Stream Computations Organized for Reconfigurable Execution 234
9.1 Programming 236
9.2 System Architecture and Execution Patterns 239
9.3 Compilation 243
9.4 Runtime 244
9.5 Highlights 248
References 248
Chapter 10. Programming Data Parallel FPGA Applications Using the SIMD/Vector Model 250
10.1 SIMD Computing on FPGAs: An Example 250
10.2 SIMD Processing Architectures 252
10.3 Data Parallel Languages 253
10.4 Reconfigurable Computers for SIMD/Vector Processing 254
10.5 Variations of SIMD/Vector Computing 257
10.6 Pipelined SIMD/Vector Processing 259
10.7 Summary 260
References 261
Chapter 11. Operating System Support for Reconfigurable Computing 262
11.1 History 263
11.2 Abstracted Hardware Resources 265
11.3 Flexible Binding 267
11.4 Scheduling 270
11.5 Communication 274
11.6 Synchronization 279
11.7 Protection 280
11.8 Summary 283
References 283
Chapter 12. The JHDL Design and Debug System 286
12.1 JHDL Background and Motivation 286
12.2 The JHDL Design Language 288
12.3 The JHDL CAD System 296
12.4 JHDL'S Hardware Mode 299
12.5 Advanced JHDL Capabilities 300
12.6 Summary 303
References 304
Part III: Mapping Designs to Reconfigurable Platforms 306
Chapter 13. Technology Mapping 308
13.1 Structural Mapping Algorithms 309
13.2 Integrated Mapping Algorithms 315
13.3 Mapping Algorithms for Heterogeneous Resources 320
13.4 Summary 324
References 324
FPGA Placement 328
Chapter 14. Placement for General-purpose FPGAs 330
14.1 The FPGA Placement Problem 330
14.2 Clustering 335
14.3 Simulated Annealing for Placement 337
14.4 Partition-Based Placement 343
14.5 Analytic Placement 346
14.6 Further Reading and Open Challenges 347
References 347
Chapter 15. Datapath Composition 350
15.1 Fundamentals 350
15.2 Tool Flow Overview 354
15.3 The Impact of Device Architecture 355
15.4 The Interface to Module Generators 357
15.5 The Mapping 360
15.6 Placement 364
15.7 Compaction 368
15.8 Summary and Future Work 375
References 375
Chapter 16. Specifying Circuit Layout on FPGAs 378
16.1 The Problem 378
16.2 Explicit Cartesian Layout Specification 382
16.3 Algebraic Layout Specification 383
16.4 Layout Verification for Parameterized Designs 391
16.5 Summary 393
References 394
Chapter 17. PathFinder: A Negotiation-based, Performance-driven Router for FPGAs 396
17.1 The History of PathFinder 397
17.2 The PathFinder Algorithm 398
17.3 Enhancements and Extensions to PathFinder 405
17.4 Parallel PathFinder 408
17.5 Other Applications of the PathFinder Algorithm 410
17.6 Summary 410
References 411
Chapter 18. Retiming, Repipelining, and C-slow Retiming 414
18.1 Retiming: Concepts, Algorithm, and Restrictions 415
18.2 Repipelining and C-slow Retiming 419
18.3 Implementations of Retiming 424
18.4 Retiming on Fixed-Frequency FPGAs 425
18.5 C-slowing as Multi-Threading 426
18.6 Why Isn’t Retiming Ubiquitous? 429
References 429
Chapter 19. Configuration Bitstream Generation 432
19.1 The Bitstream 434
19.2 Downloading Mechanisms 437
19.3 Software to Generate Configuration Data 438
19.4 Summary 440
References 440
Chapter 20. Fast Compilation Techniques 442
20.1 Accelerating Classical Techniques 445
20.2 Alternative Algorithms 453
20.3 Effect of Architecture 458
20.4 Summary 462
References 463
Part IV: Application Development 466
Chapter 21. Implementing Applications with FPGAs 470
21.1 Strengths and Weaknesses of FPGAs 470
21.2 Application Characteristics and Performance 472
21.3 General Implementation Strategies for FPGA-based Systems 476
21.4 Implementing Arithmetic in FPGAs 479
21.5 Summary 483
References 483
Chapter 22. Instance-specific Design 486
22.1 Instance-specific Design 486
22.2 Partial Evaluation 493
22.3 Summary 504
References 504
Chapter 23. Precision Analysis for Fixed-point Computation 506
23.1 Fixed-point Number System 506
23.2 Peak Value Estimation 509
23.3 Wordlength Optimization 516
23.4 Summary 529
References 530
Chapter 24. Distributed Arithmetic 534
24.1 Theory 534
24.2 DA Implementation 535
24.3 Mapping DA onto FPGAs 538
24.4 Improving DA Performance 539
24.5 An Application of DA on an FPGA 542
References 542
Chapter 25. Cordic Architectures for FPGA Computing 544
25.1 Cordic Algorithm 545
25.2 Architectural Design 557
25.3 FPGA Implementation of Cordic Processors 558
25.4 Summary 565
References 566
Chapter 26. Hardware/Software Partitioning 570
26.1 The Trend Toward Automatic Partitioning 571
26.2 Partitioning of Sequential Programs 573
26.3 Partitioning of Parallel Programs 588
26.4 Summary and Directions 589
References 590
Part V: Case Studies of FPGA Applications 592
Chapter 27. Spiht Image Compression 596
27.1 Background 596
27.2 Spiht Algorithm 597
27.3 Design Considerations and Modifications 602
27.4 Hardware Implementation 611
27.5 Design Results 618
27.6 Summary and Future Work 619
References 620
Chapter 28. Automatic Target Recognition Systems on Reconfigurable Devices 622
28.1 Automatic Target Recognition Algorithms 623
28.2 Dynamically Reconfigurable Designs 625
28.3 Reconfigurable Static Design 631
28.4 ATR Implementations 635
28.5 Summary 640
References 641
Chapter 29. Boolean Satisfiability: Creating Solvers Optimized for Specific Problem Instances 644
29.1 Boolean Satisfiability Basics 644
29.2 Sat-solving Algorithms 646
29.3 A Reconfigurable SAT Solver Generated According to an SAT Instance 649
29.4 A Different Approach to Reduce Compilation Time and Improve Algorithm Efficiency 658
29.5 Discussion 664
References 666
Chapter 30. Multi-FPGA Systems: Logic Emulation 668
30.1 Background 668
30.2 Uses of Logic Emulation Systems 670
30.3 Types of Logic Emulation Systems 671
30.4 Issues Related to Contemporary Logic Emulation 681
30.5 The Need for Fast FPGA Mapping 683
30.6 Case Study: The Virtualogic VLE Emulation System 684
30.7 Future Trends 697
30.8 Summary 698
References 699
Chapter 31. The Implications of Floating Point for FPGAs 702
31.1 Why is Floating Point Difficult? 702
31.2 Floating-point Application Case Studies 710
31.3 Summary 723
References 725
Chapter 32. Finite Difference Time Domain: A Case Study Using FPGAs 728
32.1 The FDTD Method 728
32.2 FDTD Hardware Design Case Study 738
32.3 Summary 754
References 754
Chapter 33. Evolvable FPGAs 756
33.1 The Poe Model of Bioinspired Design Methodologies 756
33.2 Artificial Evolution 758
33.3 Evolvable Hardware 760
33.4 Evolvable Hardware: A Taxonomy 764
33.5 Evolvable Hardware Digital Platforms 770
33.6 Conclusions and Future Directions 776
References 778
Chapter 34. Network Packet Processing in Reconfigurable Hardware 784
34.1 Networking with Reconfigurable Hardware 784
34.2 Network Protocol Processing 788
34.3 Intrusion Detection and Prevention 793
34.4 Semantic Processing 798
34.5 Complete Networking System Issues 801
34.6 Summary 806
References 807
Chapter 35. Active Pages:Memory-centric Computation 810
35.1 Active Pages 810
35.2 Performance Results 812
35.3 Algorithmic Complexity 817
35.4 Exploring Parallelism 825
35.5 Defect Tolerance 830
35.6 Related Work 832
35.7 Summary 833
References 833
Part VI: Theoretical Underpinnings and Future Directions 836
Chapter 36. Theoretical Underpinnings 838
36.1 General Computational Array Model 838
36.2 Implications of the General Model 840
36.3 Induced Architectural Models 845
36.4 Modeling Architectural Space 847
36.5 Implications 857
References 859
Chapter 37. Defect and Fault Tolerance 860
37.1 Defects and Faults 861
37.2 Defect Tolerance 861
37.3 Transient Fault Tolerance 874
37.4 Lifetime Defects 879
37.5 Configuration Upsets 880
37.6 Outlook 881
References 882
Chapter 38. Reconfigurable Computing and Nanoscale Architecture 884
38.1 Trends in Lithographic Scaling 885
38.2 Bottom-up Technology 886
38.3 Challenges 889
38.4 Nanowire Circuits 890
38.5 Statistical Assembly 893
38.6 Nanopla Architecture 895
38.7 Nanoscale Design Alternatives 901
38.8 Summary 903
References 904
Index 908