Design of Image Processing Embedded Systems Using Multidimensional Data Flow (eBook)

Preface 5
Overview of This Book 5
Target Audience 6
Prerequisites 6
How the Book Is Organized 6
Distinct Features and Benefits of This Book 9
Acknowledgments 11
Contents 12
List of Figures 17
List of Tables 20
List of Algorithms 21
1 Introduction 22
1.1 Motivation and Current Practices 22
1.2 Multidimensional System Level Design Overview 25
2 Design of Image Processing Applications 29
2.1 Classification of Image Processing Algorithms 30
2.2 JPEG2000 Image Compression 31
2.3 Parallelism of Image Processing Applications 35
2.4 System Implementation 36
2.4.1 Design Gap Between Available Software Solution and Desired Hardware Implementation 37
2.4.2 Lack of Architectural Verification 37
2.4.3 Missing Possibility to Explore Consequences of Implementation Alternatives 37
2.4.4 Manual Design of Memory System 38
2.4.5 Lack to Simulate the Overall System 38
2.4.6 Inability to Precisely Predict Required Computational Effort for Both Hardware and Software 38
2.5 Requirements for System Level Design of Image Processing Applications 38
2.5.1 Representation of Global, Local, and Point Algorithms 39
2.5.2 Representation of Task, Data, and Operation Parallelism 39
2.5.3 Capability to Represent Control Flow in Multidimensional Algorithms 39
2.5.4 Tight Interaction Between Static and Data-Dependent Algorithms 39
2.5.5 Support of Data Reordering 39
2.5.6 Fast Generation of RTL Implementations for Quick Feedback During Architecture Design 40
2.5.7 High-Level Verification 40
2.5.8 High-Level Performance Evaluation 40
2.5.9 Tool-Supported Design of Memory Systems 40
2.6 Multidimensional System Level Design 40
3 Fundamentals and Related Work 42
3.1 Behavioral Specification 42
3.1.1 Modeling Approaches 42
3.1.2 Sequential Languages 44
3.1.2.1 Communicating Sequential Processes 45
3.1.2.2 SystemC 46
3.1.3 One-Dimensional Data Flow 46
3.1.3.1 Synchronous Data Flow (SDF) 47
3.1.3.2 Cyclo-static Data Flow (CSDF) 49
3.1.3.3 Fractional Rate Data Flow (FRDF) 51
3.1.3.4 Parameterized Data Flow 52
3.1.3.5 Homogeneous Parameterized Data Flow (HPDF) 52
3.1.3.6 Data-Dependent Data Flow 53
3.1.3.7 FunState 54
3.1.3.8 Lessons Learned 54
3.1.4 Multidimensional Data Flow 54
3.1.4.1 Multidimensional Synchronous Data Flow (MDSDF) 55
3.1.4.2 Communicating Regular Processes (CRPs) 57
3.1.4.3 Array-OL 57
3.1.5 Conclusion 60
3.1.5.1 Border Processing 60
3.1.5.2 Communication Order 60
3.1.5.3 Dependency Modeling vs. Data Flow Interpretation 60
3.1.5.4 Tight Interaction Between One- and Multidimensional Data Flow 61
3.1.5.5 Restriction of Accepted Window Patterns 61
3.1.5.6 Flexible Delays 61
3.2 Behavioral Hardware Synthesis 61
3.2.1 Overview 62
3.2.2 SA-C 63
3.2.3 ROCCC 63
3.2.4 DEFACTO 64
3.2.4.1 Design Flow 64
3.2.4.2 Data Reuse 66
3.2.4.3 Evaluation and Relation with the Present Book 69
3.2.5 Synfora PICO Express 70
3.2.5.1 Design Flow 71
3.2.5.2 Evaluation and Relation with the Present Book 73
3.2.6 MMAlpha 73
3.2.7 PARO 74
3.2.8 Conclusion 75
3.3 Memory Analysis and Optimization 76
3.3.1 Memory Analysis for One-Dimensional Data Flow Graphs 76
3.3.2 Array-Based Analysis 78
3.3.3 Conclusion 83
3.4 Communication and Memory Synthesis 83
3.4.1 Memory Mapping 84
3.4.2 Parallel Data Access 84
3.4.3 Data Reuse 85
3.4.4 Out-of-Order Communication 85
3.4.5 Conclusion 87
3.5 System Level Design 87
3.5.1 Embedded Multi-processor Software Design 87
3.5.1.1 Omphale 87
3.5.1.2 ATOMIUM 90
3.5.2 Model-Based Simulation and Design 90
3.5.2.1 Image Processing Centric Approaches 91
3.5.2.2 System Level Design Tools for Multidimensional Signal Processing 93
3.5.3 System Level Mapping and Exploration 96
3.6 Conclusion 98
4 Electronic System Level Design of Image Processing Applications with SystemCoDesigner 100
4.1 Design Flow 100
4.1.1 Actor-Oriented Model 101
4.1.2 Actor Specification 102
4.1.3 Actor and Communication Synthesis 102
4.1.4 Automatic Design Space Exploration 103
4.1.5 System Building 105
4.1.6 Extensions 105
4.2 Case Study for the Motion-JPEG Decoder 105
4.2.1 Comparison Between VPC Estimates and Real Implementation 106
4.2.1.1 Evaluation of the Schedule Overhead 107
4.2.1.2 Evaluation of the Influence of the Cache 108
4.2.2 Influence of the Input Motion-JPEG Stream 109
4.3 Conclusions 110
5 Windowed Data Flow (WDF) 112
5.1 Sliding Window Communication 113
5.1.1 WDF Graph and Token Production 113
5.1.2 Virtual Border Extension 115
5.1.3 Token Consumption 116
5.1.4 Determination of Extended Border Values 118
5.1.5 WDF Delay Elements 118
5.2 Local WDF Balance Equation 119
5.3 Communication Order 121
5.4 Communication Control 124
5.4.1 Multidimensional FIFO 124
5.4.2 Communication Finite State Machine for Multidimensional Actors 126
5.5 Windowed Synchronous Data Flow (WSDF) 127
5.6 WSDF Balance Equation 129
5.6.1 Derivation of the WSDF Balance Equation 131
5.6.2 Application to an Example Graph 134
5.6.2.1 Actor Periods 135
5.7 Integration into SystemCoDesigner 136
5.8 Application Examples 137
5.8.1 Binary Morphological Reconstruction 137
5.8.1.1 Definition of the Binary Morphological Reconstruction 138
5.8.1.2 Calculation by Iterative One-Dilatation 139
5.8.1.3 Iterative Dilatation with Two Passes 140
5.8.1.4 FIFO-Based Morphological Reconstruction 143
5.8.2 Lifting-Based Wavelet Kernel 144
5.9 Limitations and Future Work 148
5.10 Conclusion 149
6 Memory Mapping Functions for Efficient Implementation of WDF Edges 151
6.1 Problem Formulation 152
6.2 Hierarchical Iteration Vectors 155
6.3 Memory Models 156
6.3.1 The Rectangular Memory Model 157
6.3.2 The Linearized Buffer Model 158
6.4 Simulation Results 162
6.5 Conclusion 167
7 Buffer Analysis for Complete Application Graphs 168
7.1 Problem Formulation 169
7.2 Buffer Analysis by Simulation 170
7.3 Polyhedral Representation of WSDF Edges 172
7.3.1 WSDF Lattice 173
7.3.2 Lattice Scaling 174
7.3.3 Out-of-Order Communication 176
7.3.4 Lattice Shifting Based on Dependency Vectors 181
7.3.5 Pipelined Actor Execution 189
7.4 Lattice Wraparound 190
7.4.1 Principle of Lattice Wraparound 192
7.4.2 Formal Description of the Lattice Wraparound 193
7.4.3 Lattice Shifting for Lattices with Wraparound 194
7.5 Scheduling of Complete WSDF Graphs 196
7.5.1 Lattice Scaling 197
7.5.2 Lattice Shifting 197
7.5.2.1 Determination of Strongly Connected Components 198
7.5.2.2 Internal Scheduling of the Strongly Connected Components 199
7.5.2.3 Shifting of the Strongly Connected Components 200
7.6 Buffer Size Calculation 202
7.6.1 ILP Formulation for Buffer Size Calculation 203
7.6.2 Memory Channel Splitting 207
7.7 Multirate Analysis 209
7.8 Solution Strategies 213
7.9 Results 214
7.9.1 Out-of-Order Communication 215
7.9.2 Application to Complex Graph Topologies 216
7.9.3 Memory Channel Splitting 219
7.9.4 Multirate Analysis 221
7.9.5 Limitations 221
7.10 Conclusion 223
8 Communication Synthesis 226
8.1 Problem Formulation 227
8.2 Hardware Architecture 231
8.2.1 Read and Write Order Control 232
8.2.1.1 Automatic Derivation of the Hierarchical Iteration Maxima and Mapping Matrices 234
8.2.1.2 Extended Iteration Vectors 234
8.2.2 Memory Partitioning 235
8.2.3 Source Address Generation 238
8.2.4 Virtual Memory Channel Mapping 243
8.2.4.1 Strategy for Virtual Memory Channel Mapping 244
8.2.4.2 Condition for Valid Virtual Memory Channel Mapping 246
8.2.4.3 Application to the JPEG Shuffle Operation 250
8.2.5 Trading Throughput Against Resource Requirements 250
8.2.6 Sink Address Generation 251
8.2.7 Fill-Level Control 253
8.2.7.1 Sink Fill-Level Control 254
8.2.7.2 Solution of the PIP 255
8.2.7.3 Source Fill-Level Control 257
8.2.8 Elimination of Modular Dependencies 261
8.3 Determination of Channel Sizes 264
8.4 Granularity of Scheduling 265
8.4.1 Latency Impact of Coarse-Grained Scheduling 265
8.4.2 Memory Size Impact of Coarse-Grained Scheduling 267
8.4.3 Controlling the Scheduling Granularity 267
8.5 Results 270
8.5.1 Implementation Strategy for High Clock Frequencies 270
8.5.2 Out-of-Order Communication 271
8.5.3 Out-of-Order Communication with Parallel Data Access 272
8.5.4 Influence of Different Memory Channel Sizes 275
8.5.5 Combination with Data Reuse 276
8.5.6 Impact of Scheduling Granularity 278
8.6 Conclusion and Future Work 279
9 Conclusion 281
9.1 Multidimensional System Design 281
9.2 Discussed Design Steps and Their Major Benefits 282
A Buffer Analysis by Simulation 284
A.1 Efficient Buffer Parameter Determination for the Rectangular Memory Model 22
A.1.1 Monitoring of Live Data Elements 284
A.1.2 Table-Based Buffer Parameter Determination 285
A.1.3 Determination of the Minimum Tables 287
A.1.4 Determination of the Maximum Tables 289
A.1.5 Complexity 292
A.2 Efficient Buffer Parameter Determination for the Linearized Buffer Model 292
A.2.1 Tree Data Structure for Tracking of Live Data Elements 293
A.2.2 Determination of the Lexicographically Smallest Live Data Element 294
A.2.3 Tree Update 295
A.2.4 Complexity of the Algorithm 297
A.3 Stimulation by Simulation 297
B Abbreviations 299
C Formula Symbols 301
References 303
Index 320