Compilation Techniques for Reconfigurable Architectures

by Cardoso, Joao M. P.; Diniz, Pedro C.

• ISBN13: 9780387096704
• ISBN10: 0387096701
• Format: Hardcover
• Copyright: 2008-10-17
• Publisher: Springer Verlag

Summary

"This book describes a wide range of code transformations and mapping techniques for compiling programs written in high-level programming languages to reconfigurable architectures. While many of these transformations and mapping techniques have been developed in the context of compilation for traditional architectures and high-level synthesis, their application to reconfigurable architectures poses a whole new set of challenges - particularly when targeting fine-grained reconfigurable architectures such as contemporary Field-Programmable Gate-Arrays (FPGAs)." "Organized in eight chapters, this book provides a helpful structure for practitioners and graduate students in the area of computer science and electrical and computer engineering to effectively map computations to reconfigurable architectures."--BOOK JACKET.

Table of Contents

Introduction	p. 1
The Promise of Reconfigurable Architectures and Systems	p. 1
The Challenge: How to Program and Compile for Reconfigurable Systems?	p. 3
This Book: Key Techniques when Compiling to Reconfigurable Architecture	p. 4
Organization of this Book	p. 5
Overview of Reconfigurable Architectures	p. 7
Evolution of Reconfigurable Architectures	p. 7
Reconfigurable Architectures: Key Characteristics	p. 8
Granularity	p. 10
Fine-Grained Reconfigurable Architectures	p. 12
Coarse-Grained Reconfigurable Architectures	p. 14
Hybrid Reconfigurable Architectures	p. 16
Granularity and Mapping	p. 19
Interconnection Topologies	p. 20
System-Level Integration	p. 21
Dynamic Reconfiguration	p. 24
Computational and Execution Models	p. 29
Streaming Data Input and Output	p. 31
Summary	p. 31
Compilation and Synthesis Flows	p. 33
Overview	p. 33
Front-End	p. 34
Middle-End	p. 35
Back-End	p. 37
Hardware Compilation and High-Level Synthesis	p. 39
Generic High-Level Synthesis	p. 40
Customized High-Level Synthesis for Fine-Grained Reconfigurable Architectures	p. 41
Register-Transfer-Level/Logic Synthesis	p. 45
High-Level Compilation for Coarse-Grained Reconfigurable Architectures	p. 48
Placement and Routing	p. 49
Illustrative Example	p. 51
High-Level Source Code Example	p. 51
Data-Flow Representation	p. 52
Computation-Oriented Mapping and Scheduling	p. 53
Data-Oriented Mapping and Transformations	p. 55
Translation to Hardware	p. 58
Reconfigurable Computing Issues and Their Impact on Compilation	p. 59
Programming Languages and Execution Models	p. 61
Intermediate Representations	p. 62
Target Reconfigurable Architecture Features	p. 64
Summary	p. 65
Code Transformations	p. 67
Bit-Level Transformations	p. 67
Bit-Width Narrowing	p. 68
Bit-Level Optimizations	p. 72
Conversion from Floating- to Fixed-Point Representations	p. 75
Nonstandard Floating-Point Formats	p. 77
Instruction-Level Transformations	p. 77
Operator Strength Reduction	p. 78
Height Reduction	p. 80
Code Motion	p. 84
Loop-Level Transformations	p. 87
Loop Unrolling	p. 87
Loop Tiling and Loop Strip-Mining	p. 90
Loop Merging and Loop Distribution	p. 94
Data-Oriented Transformations	p. 95
Data Distribution	p. 95
Data Replication	p. 96
Data Reuse and Scalar Replacement in Registers and Internal RAMs	p. 96
Other Data-Oriented Transformations	p. 99
Function-Oriented Transformations	p. 101
Function Inlining and Outlining	p. 101
Recursive Functions	p. 104
Which Code Transformations to Choose?	p. 105
Summary	p. 107
Mapping and Execution Optimizations	p. 109
Hardware Execution Techniques	p. 109
Instruction-Level Parallelism	p. 110
Speculative Execution	p. 112
Predication and if-conversion	p. 114
Multi Tasking	p. 116
Partitioning	p. 118
Temporal Partitioning	p. 119
Spatial Partitioning	p. 124
Illustrative Example	p. 125
Mapping Program Constructs to Resources	p. 127
Mapping Scalar Variables to Registers	p. 127
Mapping of Operations to FUs	p. 129
Mapping of Selection Structures	p. 130
Sharing Functional Units FUs	p. 131
Combining Instructions for RFUs	p. 132
Pipelining	p. 134
Pipelined Functional and Execution Units	p. 135
Pipelining Memory Accesses	p. 138
Loop Pipelining	p. 139
Coarse-Grained Pipelining	p. 144
Pipelining Configuration-Computation Sequences	p. 145
Memory Accesses	p. 146
Partitioning and Mapping of Arrays to Memory Resources	p. 146
Improving Memory Accesses	p. 148
Back-End Support	p. 150
Allocation, Scheduling, and Binding	p. 150
Module Generation	p. 151
Mapping, Placement, and Routing	p. 153
Summary	p. 153
Compilers for Reconfigurable Architectures	p. 155
Early Compilation Efforts	p. 155
Compilers for FPGA-Based Systems	p. 157
The SPC Compiler	p. 157
A C to Fine-Grained Pipelining Compiler	p. 158
The DeepC Silicon Compiler	p. 158
The COBRA-ABS Tool	p. 158
The DEFACTO Compiler	p. 159
The Streams-C Compiler	p. 159
The Cameron Compiler	p. 160
The MATCH Compiler	p. 160
The Galadriel and Nenya Compilers	p. 161
The Sea Cucumber Compiler	p. 161
The Abstract-Machines Compiler	p. 161
The CHAMPION Software Design Environment	p. 162
The SPARCS Tool	p. 163
The ROCCC Compiler	p. 163
The DWARV Compiler	p. 163
Compilers for Coarse-Grained Reconfigurable Architectures	p. 164
The DIL Compiler	p. 164
The RaPiD-C Compiler	p. 165
The CoDe-X Compiler	p. 165
The XPP-VC Compiler	p. 166
The DRESC Compiler	p. 166
Compilers for Hybrid Reconfigurable Architectures	p. 167
The Chimaera-C Compiler	p. 167
The Garp and the Nimble C Compilers	p. 168
The NAPA-C Compiler	p. 168
Compilation Efforts Summary	p. 169
Perspectives on Programming Reconfigurable Computing Platforms	p. 177
How to Make Reconfigurable Computing a Reality?	p. 177
Easy of Programming	p. 178
Program Portability and Legacy Code Migration	p. 179
Performance Portability	p. 180
Research Directions in Compilation for Reconfigurable Architectures	p. 181
Programming Language Design	p. 181
Intermediate Representation	p. 181
Mapping to Multiple Computing Engines	p. 182
Code Transformations	p. 182
Design-Space Exploration and Compilation Time	p. 183
Pipelined Execution	p. 184
Memory Mapping Optimizations	p. 185
Application-Specific Compilers and Cores	p. 185
Resource Virtualization	p. 186
Dynamic and Incremental Compilation	p. 186
Tackling the Compilation Challenge for Reconfigurable Architectures	p. 187
Reconfigurable Architectures and Nanotechnology	p. 189
Summary	p. 189
Final Remarks	p. 191
References	p. 193
List of Acronyms	p. 213
Index	p. 217
Table of Contents provided by Ingram. All Rights Reserved.