Compilation techniques for reconfigurable architectures

Title:

Personal Author:

Cardoso, Joao M. P.

Publication Information:

New York, NY : Springer, 2008

Physical Description:

xii, 223 p. : ill. 24 cm.

ISBN:

9780387096704

Subject Term:

Adaptive computing systems

Compilers (Computer programs)

Field programmable gate arrays

Added Author:

Diniz, Pedro C.

Available:*

Library	Item Barcode	Call Number	Material Type	Item Category 1	Status
Searching... Perpustakaan Raja Zarith Sofiah	35000000004199	QA76.9.A3 C37 2008	Open Access Book	Book	Searching... Unknown
Searching... PSZ JB	30000010197645	QA76.9.A3 C37 2008	Open Access Book	Book	Searching... Unknown

The extreme ?exibility of recon?gurable architectures and their performance pot- tial have made them a vehicle of choice in a wide range of computing domains, from rapid circuit prototyping to high-performance computing. The increasing availab- ity of transistors on a die has allowed the emergence of recon?gurable architectures with a large number of computing resources and interconnection topologies. To - ploit the potential of these recon?gurable architectures, programmers are forced to map their applications, typically written in high-level imperative programming l- guages, such as C or MATLAB, to hardware-oriented languages such as VHDL or Verilog. In this process, they must assume the role of hardware designers and software programmers and navigate a maze of program transformations, mapping, and synthesis steps to produce ef?cient recon?gurable computing implementations. The richness and sophistication of any of these application mapping steps make the mapping of computations to these architectures an increasingly daunting process. It is thus widely believed that automatic compilation from high-level programming languages is the key to the success of recon?gurable computing. This book describes a wide range of code transformations and mapping te- niques for programs described in high-level programming languages, most - tably imperative languages, to recon?gurable architectures.

1 Introduction	p. 1
1.1 The Promise of Reconfigurable Architectures and Systems	p. 1
1.2 The Challenge: How to Program and Compile for Reconfigurable Systems?	p. 3
1.3 This Book: Key Techniques when Compiling to Reconfigurable Architecture	p. 4
1.4 Organization of this Book	p. 5
2 Overview of Reconfigurable Architectures	p. 7
2.1 Evolution of Reconfigurable Architectures	p. 7
2.2 Reconfigurable Architectures: Key Characteristics	p. 8
2.3 Granularity	p. 10
2.3.1 Fine-Grained Reconfigurable Architectures	p. 12
2.3.2 Coarse-Grained Reconfigurable Architectures	p. 14
2.3.3 Hybrid Reconfigurable Architectures	p. 16
2.3.4 Granularity and Mapping	p. 19
2.4 Interconnection Topologies	p. 20
2.5 System-Level Integration	p. 21
2.6 Dynamic Reconfiguration	p. 24
2.7 Computational and Execution Models	p. 29
2.8 Streaming Data Input and Output	p. 31
2.9 Summary	p. 31
3 Compilation and Synthesis Flows	p. 33
3.1 Overview	p. 33
3.1.1 Front-End	p. 34
3.1.2 Middle-End	p. 35
3.1.3 Back-End	p. 37
3.2 Hardware Compilation and High-Level Synthesis	p. 39
3.2.1 Generic High-Level Synthesis	p. 40
3.2.2 Customized High-Level Synthesis for Fine-Grained Reconfigurable Architectures	p. 41
3.2.3 Register-Transfer-Level/Logic Synthesis	p. 45
3.2.4 High-Level Compilation for Coarse-Grained Reconfigurable Architectures	p. 48
3.2.5 Placement and Routing	p. 49
3.3 Illustrative Example	p. 51
3.3.1 High-Level Source Code Example	p. 51
3.3.2 Data-Flow Representation	p. 52
3.3.3 Computation-Oriented Mapping and Scheduling	p. 53
3.3.4 Data-Oriented Mapping and Transformations	p. 55
3.3.5 Translation to Hardware	p. 58
3.4 Reconfigurable Computing Issues and Their Impact on Compilation	p. 59
3.4.1 Programming Languages and Execution Models	p. 61
3.4.2 Intermediate Representations	p. 62
3.4.3 Target Reconfigurable Architecture Features	p. 64
3.5 Summary	p. 65
4 Code Transformations	p. 67
4.1 Bit-Level Transformations	p. 67
4.1.1 Bit-Width Narrowing	p. 68
4.1.2 Bit-Level Optimizations	p. 72
4.1.3 Conversion from Floating- to Fixed-Point Representations	p. 75
4.1.4 Nonstandard Floating-Point Formats	p. 77
4.2 Instruction-Level Transformations	p. 77
4.2.1 Operator Strength Reduction	p. 78
4.2.2 Height Reduction	p. 80
4.2.3 Code Motion	p. 84
4.3 Loop-Level Transformations	p. 87
4.3.1 Loop Unrolling	p. 87
4.3.2 Loop Tiling and Loop Strip-Mining	p. 90
4.3.3 Loop Merging and Loop Distribution	p. 94
4.4 Data-Oriented Transformations	p. 95
4.4.1 Data Distribution	p. 95
4.4.2 Data Replication	p. 96
4.4.3 Data Reuse and Scalar Replacement in Registers and Internal RAMs	p. 96
4.4.4 Other Data-Oriented Transformations	p. 99
4.5 Function-Oriented Transformations	p. 101
4.5.1 Function Inlining and Outlining	p. 101
4.5.2 Recursive Functions	p. 104
4.6 Which Code Transformations to Choose?	p. 105
4.7 Summary	p. 107
5 Mapping and Execution Optimizations	p. 109
5.1 Hardware Execution Techniques	p. 109
5.1.1 Instruction-Level Parallelism	p. 110
5.1.2 Speculative Execution	p. 112
5.1.3 Predication and if-conversion	p. 114
5.1.4 Multi Tasking	p. 116
5.2 Partitioning	p. 118
5.2.1 Temporal Partitioning	p. 119
5.2.2 Spatial Partitioning	p. 124
5.2.3 Illustrative Example	p. 125
5.3 Mapping Program Constructs to Resources	p. 127
5.3.1 Mapping Scalar Variables to Registers	p. 127
5.3.2 Mapping of Operations to FUs	p. 129
5.3.3 Mapping of Selection Structures	p. 130
5.3.4 Sharing Functional Units FUs	p. 131
5.3.5 Combining Instructions for RFUs	p. 132
5.4 Pipelining	p. 134
5.4.1 Pipelined Functional and Execution Units	p. 135
5.4.2 Pipelining Memory Accesses	p. 138
5.4.3 Loop Pipelining	p. 139
5.4.4 Coarse-Grained Pipelining	p. 144
5.4.5 Pipelining Configuration-Computation Sequences	p. 145
5.5 Memory Accesses	p. 146
5.5.1 Partitioning and Mapping of Arrays to Memory Resources	p. 146
5.5.2 Improving Memory Accesses	p. 148
5.6 Back-End Support	p. 150
5.6.1 Allocation, Scheduling, and Binding	p. 150
5.6.2 Module Generation	p. 151
5.6.3 Mapping, Placement, and Routing	p. 153
5.7 Summary	p. 153
6 Compilers for Reconfigurable Architectures	p. 155
6.1 Early Compilation Efforts	p. 155
6.2 Compilers for FPGA-Based Systems	p. 157
6.2.1 The SPC Compiler	p. 157
6.2.2 A C to Fine-Grained Pipelining Compiler	p. 158
6.2.3 The DeepC Silicon Compiler	p. 158
6.2.4 The COBRA-ABS Tool	p. 158
6.2.5 The DEFACTO Compiler	p. 159
6.2.6 The Streams-C Compiler	p. 159
6.2.7 The Cameron Compiler	p. 160
6.2.8 The MATCH Compiler	p. 160
6.2.9 The Galadriel and Nenya Compilers	p. 161
6.2.10 The Sea Cucumber Compiler	p. 161
6.2.11 The Abstract-Machines Compiler	p. 161
6.2.12 The CHAMPION Software Design Environment	p. 162
6.2.13 The SPARCS Tool	p. 163
6.2.14 The ROCCC Compiler	p. 163
6.2.15 The DWARV Compiler	p. 163
6.3 Compilers for Coarse-Grained Reconfigurable Architectures	p. 164
6.3.1 The DIL Compiler	p. 164
6.3.2 The RaPiD-C Compiler	p. 165
6.3.3 The CoDe-X Compiler	p. 165
6.3.4 The XPP-VC Compiler	p. 166
6.3.5 The DRESC Compiler	p. 166
6.4 Compilers for Hybrid Reconfigurable Architectures	p. 167
6.4.1 The Chimaera-C Compiler	p. 167
6.4.2 The Garp and the Nimble C Compilers	p. 168
6.4.3 The NAPA-C Compiler	p. 168
6.5 Compilation Efforts Summary	p. 169
7 Perspectives on Programming Reconfigurable Computing Platforms	p. 177
7.1 How to Make Reconfigurable Computing a Reality?	p. 177
7.1.1 Easy of Programming	p. 178
7.1.2 Program Portability and Legacy Code Migration	p. 179
7.1.3 Performance Portability	p. 180
7.2 Research Directions in Compilation for Reconfigurable Architectures	p. 181
7.2.1 Programming Language Design	p. 181
7.2.2 Intermediate Representation	p. 181
7.2.3 Mapping to Multiple Computing Engines	p. 182
7.2.4 Code Transformations	p. 182
7.2.5 Design-Space Exploration and Compilation Time	p. 183
7.2.6 Pipelined Execution	p. 184
7.2.7 Memory Mapping Optimizations	p. 185
7.2.8 Application-Specific Compilers and Cores	p. 185
7.2.9 Resource Virtualization	p. 186
7.2.10 Dynamic and Incremental Compilation	p. 186
7.3 Tackling the Compilation Challenge for Reconfigurable Architectures	p. 187
7.4 Reconfigurable Architectures and Nanotechnology	p. 189
7.5 Summary	p. 189
8 Final Remarks	p. 191
References	p. 193
List of Acronyms	p. 213
Index	p. 217

Available:*

On Order

Summary

Summary

Table of Contents