Reconfigurable Computing (eBook)

Contents 5
Acknowledgments 9
1 An Introduction to Reconfigurable Computing 11
1.1 What is RC? 11
1.2 RC Architectures 13
1.3 How did RC originate? 14
1.4 Inside the FPGA 16
1.5 Mapping Algorithms to Hardware 17
1.6 RC Applications 18
1.7 Example: Dot Product 19
1.8 Further Reading 20
2 Reconfigurable Logic Devices 21
2.1 Field-Programmable Gate Arrays 22
2.1.1 Basic Architecture 22
Programmable Logic 24
Routing 26
Programmable I/O Architectures 31
2.1.2 Specialized Function Blocks 32
Embedded Memory 33
Embedded Arithmetic Logic 33
High-Speed Serial I/O 34
Embedded Microprocessors 34
2.1.3 Programming Architecture 36
2.2 Coarse-Grained Reconfigurable Arrays 38
2.2.1 Raw 39
2.2.2 PipeRench 40
2.2.3 RaPiD 42
2.2.4 PACT XPP 43
2.2.5 MathStar 45
2.3 Summary 46
3 Reconfigurable Computing Systems 47
3.1 Parallel Processing on Reconfigurable Computers 47
3.1.1 Instruction Level Parallelism 47
3.1.2 Task Level Parallelism 49
3.2 A Survey of Reconfigurable Computing Systems 51
3.2.1 I/O Bus Accelerator 53
3.2.2 Massively Parallel FPGA array 55
3.2.3 Reconfigurable Supercomputer 55
3.2.4 Reconfigurable Logic Co-processor 57
3.3 Summary 59
4 Languages and Compilation 61
4.1 Design Cycle 61
4.2 Languages 64
4.2.1 Algorithmic RC Languages 65
Algorithmic Language Example 67
4.2.2 Hardware Description Languages (HDL) 67
A VHDL Example 69
4.3 High Level Compilation 70
4.3.1 Compiler Phases 75
4.3.2 Analysis and Optimizations 76
4.3.3 Scheduling 77
4.4 Low Level Design Flow 78
4.4.1 Logic Synthesis 79
4.4.2 Technology Mapping 80
4.4.3 Logic Placement 81
4.4.4 Signal Routing 82
4.4.5 Configuration Bitstreams 83
4.5 Debugging Reconfigurable Computing Applications 84
4.5.1 Basic Needs for Debugging 84
Observability: 84
Controllability: 84
Execution Control: 84
Debugging Data Bandwidth: 84
System Execution Speed: 85
Instrumentation Costs: 85
Ease of Use: 85
4.5.2 Debugging Facilities 85
4.5.3 Challenges for RC Application Debugging 94
4.6 Summary 95
5 Digital Signal Processing Applications 97
5.1 What is Digital Signal Processing? 97
5.2 Why Use Recon.gurable Computing for DSP? 99
5.2.1 Reconfigurable Computing’s Suitability for DSP 99
5.2.2 Comparing DSP Implementation Technologies 102
5.3 DSP Application Building Blocks 106
5.3.1 Basic Operations and Elements 107
5.3.2 Filtering 112
5.3.3 Transforms 113
5.4 Example DSP Applications 118
5.4.1 Beamforming 118
5.4.2 Software Radio 122
5.5 Summary 127
6 Image Processing 129
6.1 RC for Image and Video Processing 129
6.2 Local Neighborhood Functions 131
6.2.1 Cellular Arrays for Pixel Parallelism 133
6.2.2 Image Pipelines for Instruction-Level Parallelism 133
6.3 Convolution 134
6.4 Morphology 135
6.5 Feature Extraction 137
6.6 Automatic Target Recognition 139
6.7 Image Matching 141
6.8 Evolutionary Image Processing 144
6.9 Summary 149
7 Network Security 151
7.1 Cryptographic Applications 151
7.1.1 Cryptography Basics 152
Symmetric Algorithms 152
Block Symmetric Algorithms 153
Stream ciphers, 154
Asymmetric Algorithms 154
7.1.2 RC Cryptographic Algorithm Implementations 156
7.2 Network Protocol Security 158
7.2.1 RC Network Interface 158
7.2.2 Security Protocols 161
7.2.3 Network Defense 162
7.3 Summary 165
8 Bioinformatics Applications 167
8.1 Introduction 167
8.2 Applications 169
8.2.1 Genome Assembly 169
8.2.2 Content-Based Search 170
8.2.3 Genome Comparison 170
8.2.4 Molecular Phylogeny 171
8.2.5 Pattern Matching 171
8.2.6 Protein Domain Databases 172
8.3 Dynamic Programming Algorithms 173
8.3.1 Alignments 173
8.3.2 Dynamic Programming Equations 174
8.3.3 Gap Functions 176
8.3.4 Systolic DP Computation 176
8.3.5 Backtracking 177
8.3.6 Modulo Encoding 179
8.3.7 FPGA Implementations 180
8.4 Seed-Based Heuristics 180
8.4.1 Filtering, Heuristics, and Quality Values 181
8.4.2 BLAST: a 3-Stages Heuristic 181
8.4.3 Seed Indexing 182
8.4.4 FPGA Implementations 184
8.5 Profiles, HMMs and Language Models 184
8.5.1 Position-Dependent Pro.les 184
8.5.2 Hidden Markov Models 185
8.5.3 Language Models 186
8.6 Bioinformatics FPGA Accelerators 187
8.6.1 Splash 188
8.6.2 Perle 188
8.6.3 GenStorm 188
8.6.4 RDisk 188
8.6.5 BioXL/H 191
8.6.6 DeCypher 191
8.7 Summary 191
9 Supercomputing Applications 193
9.1 Introduction 193
9.2 Monte Carlo Simulation of Radiative Heat Transfer 194
9.2.1 Algorithm Description 195
9.2.2 Hardware Implementation 197
9.2.3 Performance 198
9.3 Urban Road Traffic Simulation 202
9.3.1 CA Traffic Modeling 203
9.3.2 Intersections and Global Behavior 204
9.3.3 Constructive Approach 206
9.3.4 Streaming Approach 208
9.4 Summary 213
References 215
Index 243

3 Reconfigurable Computing Systems (p. 37-38)

In this chapter, we will discuss general purpose computing systems that incorporate FPGAs into the system architecture. While modern FPGAs include processors, memory blocks, and built-in I/O interfaces on-chip, recon.gurable systems, even those with a single FPGA or tiled processor array contain off-chip memory and I/O resources as well. Since recon.gurable computing is concerned with parallel operations at any level of granularity, we will motivate the roles that FPGAs can play by first discussing parallel processing models and how they might use reconfigurable logic. We will then survey the field of reconfigurable processing systems.

3.1 Parallel Processing on Recon.gurable Computers

Reconfigurable computing systems derive high performance by exploiting parallelism at multiple levels of granularity, from instruction through task level parallelism. In this section we introduce the levels of parallelism and discuss the use of recon.gurable hardware at various granularity of parallelization.

3.1.1 Instruction Level Parallelism

The lowest level of granularity we consider is instruction-level parallelism. In conventional microprocessors, instruction-level parallelism is exploited in the micro-architecture of a superscalar processor. By having multiple instructions in progress in di.erent stages of completion, the superscalar processor is able to complete more than one instruction in a clock cycle.

Very Long Instruction Word (VLIW) processors offer another method for fine-grained parallel operation. A VLIW processor contains multiple function units operating in parallel. In Figure 3.1, the instruction word contains fields for two integer operations, two floating point operations, two memory operations, and a branch. To compile for a superscalar processor, the compiler simply generates a sequential instruction stream, and the processor parallelizes the instruction stream at run time. In contrast, the VLIW processor executes the instruction word generated by the compiler, requiring the compiler to schedule concurrent operations at compile time.

Co-processor parallelism is achieved within a single instruction stream. A customized parallel instruction is performed by co-processor. Examples of co-processors include MMX/SSE units or vector units. Instructions for the co-processor are integrated into the instruction set of the processor. The coprocessor shares register files and other internal state with other arithmetic units, such as the floating point units, as shown in Figure 3.2.