Compilation Techniques for Reconfigurable Architectures (eBook)

Joao M.P. Cardoso, Pedro C. Diniz (Autoren)

eBook Download: PDF

2011 | 2009
XII, 223 Seiten
Springer US (Verlag)
978-0-387-09671-1 (ISBN)

Infos

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.

Inhalt

Preface 6
Contents 8
Chapter 1: Introduction 12
1.1 The Promise of Reconfigurable Architectures and Systems 12
1.2 The Challenge: How to Program and Compilefor Reconfigurable Systems? 14
1.3 This Book: Key Techniques when Compilingto Reconfigurable Architecture 15
1.4 Organization of this Book 16
Chapter 2: Overview of Reconfigurable Architectures 18
2.1 Evolution of Reconfigurable Architectures 18
2.2 Reconfigurable Architectures: Key Characteristics 19
2.3 Granularity 21
2.3.1 Fine-Grained Reconfigurable Architectures 23
2.3.2 Coarse-Grained Reconfigurable Architectures 25
2.3.3 Hybrid Reconfigurable Architectures 27
2.3.4 Granularity and Mapping 30
2.4 Interconnection Topologies 31
2.5 System-Level Integration 32
2.6 Dynamic Reconfiguration 35
2.7 Computational and Execution Models 40
2.8 Streaming Data Input and Output 42
2.9 Summary 42
Chapter 3: Compilation and Synthesis Flows 44
3.1 Overview 44
3.1.1 Front-End 45
3.1.2 Middle-End 46
3.1.3 Back-End 48
3.2 Hardware Compilation and High-Level Synthesis 50
3.2.1 Generic High-Level Synthesis 51
3.2.2 Customized High-Level Synthesis for Fine-GrainedReconfigurable Architectures 52
3.2.3 Register-Transfer-Level/Logic Synthesis 56
3.2.4 High-Level Compilation for Coarse-GrainedReconfigurable Architectures 59
3.2.5 Placement and Routing 60
3.3 Illustrative Example 62
3.3.1 High-Level Source Code Example 62
3.3.2 Data-Flow Representation 63
3.3.3 Computation-Oriented Mapping and Scheduling 64
3.3.4 Data-Oriented Mapping and Transformations 66
3.3.5 Translation to Hardware 69
3.4 Reconfigurable Computing Issues and Their Impacton Compilation 70
3.4.1 Programming Languages and Execution Models 72
3.4.2 Intermediate Representations 73
3.4.3 Target Reconfigurable Architecture Features 75
3.5 Summary 76
Chapter 4: Code Transformations 77
4.1 Bit-Level Transformations 77
4.1.1 Bit-Width Narrowing 78
4.1.2 Bit-Level Optimizations 82
4.1.3 Conversion from Floating- to Fixed-Point Representations 85
4.1.4 Nonstandard Floating-Point Formats 87
4.2 Instruction-Level Transformations 87
4.2.1 Operator Strength Reduction 88
4.2.2 Height Reduction 90
4.2.3 Code Motion 94
4.3 Loop-Level Transformations 97
4.3.1 Loop Unrolling 97
4.3.2 Loop Tiling and Loop Strip-Mining 100
4.3.3 Loop Merging and Loop Distribution 104
4.4 Data-Oriented Transformations 105
4.4.1 Data Distribution 105
4.4.2 Data Replication 106
4.4.3 Data Reuse and Scalar Replacement in Registersand Internal RAMs 106
4.4.4 Other Data-Oriented Transformations 109
4.5 Function-Oriented Transformations 111
4.5.1 Function Inlining and Outlining 111
4.5.2 Recursive Functions 114
4.6 Which Code Transformations to Choose? 115
4.7 Summary 117
Chapter 5: Mapping and Execution Optimizations 118
5.1 Hardware Execution Techniques 118
5.1.1 Instruction-Level Parallelism 119
5.1.2 Speculative Execution 121
5.1.3 Predication and if-conversion 123
5.1.4 Multi Tasking 125
5.2 Partitioning 127
5.2.1 Temporal Partitioning 128
5.2.2 Spatial Partitioning 133
5.2.3 Illustrative Example 134
5.3 Mapping Program Constructs to Resources 136
5.3.1 Mapping Scalar Variables to Registers 136
5.3.2 Mapping of Operations to FUs 138
5.3.3 Mapping of Selection Structures 139
5.3.4 Sharing Functional Units FUs 140
5.3.5 Combining Instructions for RFUs 141
5.4 Pipelining 143
5.4.1 Pipelined Functional and Execution Units 144
5.4.2 Pipelining Memory Accesses 147
5.4.3 Loop Pipelining 148
5.4.4 Coarse-Grained Pipelining 153
5.4.5 Pipelining Configuration–Computation Sequences 154
5.5 Memory Accesses 155
5.5.1 Partitioning and Mapping of Arrays to Memory Resources 155
5.5.2 Improving Memory Accesses 157
5.6 Back-End Support 159
5.6.1 Allocation, Scheduling, and Binding 159
5.6.2 Module Generation 160
5.6.3 Mapping, Placement, and Routing 162
5.7 Summary 162
Chapter 6: Compilers for Reconfigurable Architectures 164
6.1 Early Compilation Efforts 164
6.2 Compilers for FPGA-Based Systems 166
6.2.1 The SPC Compiler 166
6.2.2 A C to Fine-Grained Pipelining Compiler 167
6.2.3 The DeepC Silicon Compiler 167
6.2.4 The COBRA-ABS Tool 167
6.2.5 The DEFACTO Compiler 168
6.2.6 The Streams-C Compiler 168
6.2.7 The Cameron Compiler 169
6.2.8 The MATCH Compiler 169
6.2.9 The Galadriel and Nenya Compilers 170
6.2.10 The Sea Cucumber Compiler 170
6.2.11 The Abstract-Machines Compiler 170
6.2.12 The CHAMPION Software Design Environment 171
6.2.13 The SPARCS Tool 172
6.2.14 The ROCCC Compiler 172
6.2.15 The DWARV Compiler 172
6.3 Compilers for Coarse-Grained Reconfigurable Architectures 173
6.3.1 The DIL Compiler 173
6.3.2 The RaPiD-C Compiler 174
6.3.3 The CoDe-X Compiler 174
6.3.4 The XPP-VC Compiler 175
6.3.5 The DRESC Compiler 175
6.4 Compilers for Hybrid Reconfigurable Architectures 176
6.4.1 The Chimaera-C Compiler 176
6.4.2 The Garp and the Nimble C Compilers 177
6.4.3 The NAPA-C Compiler 177
6.5 Compilation Efforts Summary 178
Chapter 7: Perspectives on Programming ReconfigurableComputing Platforms 186
7.1 How to Make Reconfigurable Computing a Reality? 186
7.1.1 Easy of Programming 187
7.1.2 Program Portability and Legacy Code Migration 188
7.1.3 Performance Portability 189
7.2 Research Directions in Compilation for ReconfigurableArchitectures 190
7.2.1 Programming Language Design 190
7.2.2 Intermediate Representation 190
7.2.3 Mapping to Multiple Computing Engines 191
7.2.4 Code Transformations 191
7.2.5 Design-Space Exploration and Compilation Time 192
7.2.6 Pipelined Execution 193
7.2.7 Memory Mapping Optimizations 194
7.2.8 Application-Specific Compilers and Cores 194
7.2.9 Resource Virtualization 195
7.2.10 Dynamic and Incremental Compilation 195
7.3 Tackling the Compilation Challenge for ReconfigurableArchitectures 196
7.4 Reconfigurable Architectures and Nanotechnology 198
7.5 Summary 198
Chapter 8: Final Remarks 199
References 201
List of Acronyms 220
Index 223

Produkt-Details

• Erscheint lt. Verlag: 2.4.2011
• Zusatzinfo: XII, 223 p. 88 illus.
• Verlagsort: New York
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Schlagworte: Compiler • Computer • Computer Architecture • field programmable gate array • FPGA • Hardware • Hardware Compilation • Mapping Techniques • programming • reconfigurable computing • Software Compilation
• ISBN-10: 0-387-09671-X / 038709671X
• ISBN-13: 978-0-387-09671-1 / 9780387096711