Keinert / Teich Design of Image Processing Embedded Systems Using Multidimensional Data Flow

1. Auflage 2010
ISBN: 978-1-4419-7182-1
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 314 Seiten

Reihe: Embedded Systems

This book presents a new set of embedded system design techniques called multidimensional data flow, which combine the various benefits offered by existing methodologies such as block-based system design, high-level simulation, system analysis and polyhedral optimization. It describes a novel architecture for efficient and flexible high-speed communication in hardware that can be used both in manual and automatic system design and that offers various design alternatives, balancing achievable throughput with required hardware size. This book demonstrates multidimensional data flow by showing its potential for modeling, analysis, and synthesis of complex image processing applications. These applications are presented in terms of their fundamental properties and resulting design constraints. Coverage includes a discussion of how far the latter can be met better by multidimensional data flow than alternative approaches. Based on these results, the book explains the principles of fine-grained system level analysis and high-speed communication synthesis. Additionally, an extensive review of related techniques is given in order to show their relation to multidimensional data flow.

Autoren/Hrsg.

Keinert, Joachim

Teich, Jürgen

Inhaltsverzeichnis

1;Preface;5
1.1;Overview of This Book;5
1.2;Target Audience;6
1.3;Prerequisites;6
1.4;How the Book Is Organized;6
1.5;Distinct Features and Benefits of This Book;9
2;Acknowledgments;11
3;Contents;12
4;List of Figures;17
5;List of Tables;20
6;List of Algorithms;21
7;1 Introduction;22
7.1;1.1 Motivation and Current Practices;22
7.2;1.2 Multidimensional System Level Design Overview;25
8;2 Design of Image Processing Applications;29
8.1;2.1 Classification of Image Processing Algorithms;30
8.2;2.2 JPEG2000 Image Compression;31
8.3;2.3 Parallelism of Image Processing Applications;35
8.4;2.4 System Implementation;36
8.4.1;2.4.1 Design Gap Between Available Software Solution and Desired Hardware Implementation;37
8.4.2;2.4.2 Lack of Architectural Verification;37
8.4.3;2.4.3 Missing Possibility to Explore Consequences of Implementation Alternatives;37
8.4.4;2.4.4 Manual Design of Memory System;38
8.4.5;2.4.5 Lack to Simulate the Overall System;38
8.4.6;2.4.6 Inability to Precisely Predict Required Computational Effort for Both Hardware and Software;38
8.5;2.5 Requirements for System Level Design of Image Processing Applications;38
8.5.1;2.5.1 Representation of Global, Local, and Point Algorithms;39
8.5.2;2.5.2 Representation of Task, Data, and Operation Parallelism;39
8.5.3;2.5.3 Capability to Represent Control Flow in Multidimensional Algorithms;39
8.5.4;2.5.4 Tight Interaction Between Static and Data-Dependent Algorithms;39
8.5.5;2.5.5 Support of Data Reordering;39
8.5.6;2.5.6 Fast Generation of RTL Implementations for Quick Feedback During Architecture Design;40
8.5.7;2.5.7 High-Level Verification;40
8.5.8;2.5.8 High-Level Performance Evaluation;40
8.5.9;2.5.9 Tool-Supported Design of Memory Systems;40
8.6;2.6 Multidimensional System Level Design;40
9;3 Fundamentals and Related Work ;42
9.1;3.1 Behavioral Specification;42
9.1.1;3.1.1 Modeling Approaches;42
9.1.2;3.1.2 Sequential Languages;44
9.1.2.1;3.1.2.1 Communicating Sequential Processes;45
9.1.2.2;3.1.2.2 SystemC;46
9.1.3;3.1.3 One-Dimensional Data Flow;46
9.1.3.1;3.1.3.1 Synchronous Data Flow (SDF);47
9.1.3.2;3.1.3.2 Cyclo-static Data Flow (CSDF);49
9.1.3.3;3.1.3.3 Fractional Rate Data Flow (FRDF);51
9.1.3.4;3.1.3.4 Parameterized Data Flow;52
9.1.3.5;3.1.3.5 Homogeneous Parameterized Data Flow (HPDF);52
9.1.3.6;3.1.3.6 Data-Dependent Data Flow;53
9.1.3.7;3.1.3.7 FunState;54
9.1.3.8;3.1.3.8 Lessons Learned;54
9.1.4;3.1.4 Multidimensional Data Flow;54
9.1.4.1;3.1.4.1 Multidimensional Synchronous Data Flow (MDSDF);55
9.1.4.2;3.1.4.2 Communicating Regular Processes (CRPs);57
9.1.4.3;3.1.4.3 Array-OL;57
9.1.5;3.1.5 Conclusion;60
9.1.5.1;3.1.5.1 Border Processing;60
9.1.5.2;3.1.5.2 Communication Order;60
9.1.5.3;3.1.5.3 Dependency Modeling vs. Data Flow Interpretation;60
9.1.5.4;3.1.5.4 Tight Interaction Between One- and Multidimensional Data Flow;61
9.1.5.5;3.1.5.5 Restriction of Accepted Window Patterns;61
9.1.5.6;3.1.5.6 Flexible Delays;61
9.2;3.2 Behavioral Hardware Synthesis;61
9.2.1;3.2.1 Overview;62
9.2.2;3.2.2 SA-C;63
9.2.3;3.2.3 ROCCC;63
9.2.4;3.2.4 DEFACTO;64
9.2.4.1;3.2.4.1 Design Flow;64
9.2.4.2;3.2.4.2 Data Reuse;66
9.2.4.3;3.2.4.3 Evaluation and Relation with the Present Book;69
9.2.5;3.2.5 Synfora PICO Express;70
9.2.5.1;3.2.5.1 Design Flow;71
9.2.5.2;3.2.5.2 Evaluation and Relation with the Present Book;73
9.2.6;3.2.6 MMAlpha;73
9.2.7;3.2.7 PARO;74
9.2.8;3.2.8 Conclusion;75
9.3;3.3 Memory Analysis and Optimization;76
9.3.1;3.3.1 Memory Analysis for One-Dimensional Data Flow Graphs;76
9.3.2;3.3.2 Array-Based Analysis;78
9.3.3;3.3.3 Conclusion;83
9.4;3.4 Communication and Memory Synthesis;83
9.4.1;3.4.1 Memory Mapping;84
9.4.2;3.4.2 Parallel Data Access;84
9.4.3;3.4.3 Data Reuse;85
9.4.4;3.4.4 Out-of-Order Communication;85
9.4.5;3.4.5 Conclusion;87
9.5;3.5 System Level Design;87
9.5.1;3.5.1 Embedded Multi-processor Software Design;87
9.5.1.1;3.5.1.1 Omphale;87
9.5.1.2;3.5.1.2 ATOMIUM;90
9.5.2;3.5.2 Model-Based Simulation and Design;90
9.5.2.1;3.5.2.1 Image Processing Centric Approaches;91
9.5.2.2;3.5.2.2 System Level Design Tools for Multidimensional Signal Processing;93
9.5.3;3.5.3 System Level Mapping and Exploration;96
9.6;3.6 Conclusion;98
10;4 Electronic System Level Design of Image Processing Applications with SystemCoDesigner;100
10.1;4.1 Design Flow;100
10.1.1;4.1.1 Actor-Oriented Model;101
10.1.2;4.1.2 Actor Specification;102
10.1.3;4.1.3 Actor and Communication Synthesis;102
10.1.4;4.1.4 Automatic Design Space Exploration;103
10.1.5;4.1.5 System Building;105
10.1.6;4.1.6 Extensions;105
10.2;4.2 Case Study for the Motion-JPEG Decoder;105
10.2.1;4.2.1 Comparison Between VPC Estimates and Real Implementation;106
10.2.1.1;4.2.1.1 Evaluation of the Schedule Overhead;107
10.2.1.2;4.2.1.2 Evaluation of the Influence of the Cache;108
10.2.2;4.2.2 Influence of the Input Motion-JPEG Stream;109
10.3;4.3 Conclusions;110
11;5 Windowed Data Flow (WDF);112
11.1;5.1 Sliding Window Communication;113
11.1.1;5.1.1 WDF Graph and Token Production;113
11.1.2;5.1.2 Virtual Border Extension;115
11.1.3;5.1.3 Token Consumption;116
11.1.4;5.1.4 Determination of Extended Border Values;118
11.1.5;5.1.5 WDF Delay Elements;118
11.2;5.2 Local WDF Balance Equation;119
11.3;5.3 Communication Order;121
11.4;5.4 Communication Control;124
11.4.1;5.4.1 Multidimensional FIFO;124
11.4.2;5.4.2 Communication Finite State Machine for Multidimensional Actors;126
11.5;5.5 Windowed Synchronous Data Flow (WSDF);127
11.6;5.6 WSDF Balance Equation;129
11.6.1;5.6.1 Derivation of the WSDF Balance Equation;131
11.6.2;5.6.2 Application to an Example Graph;134
11.6.2.1;5.6.2.1 Actor Periods;135
11.7;5.7 Integration into SystemCoDesigner;136
11.8;5.8 Application Examples;137
11.8.1;5.8.1 Binary Morphological Reconstruction;137
11.8.1.1;5.8.1.1 Definition of the Binary Morphological Reconstruction;138
11.8.1.2;5.8.1.2 Calculation by Iterative One-Dilatation;139
11.8.1.3;5.8.1.3 Iterative Dilatation with Two Passes;140
11.8.1.4;5.8.1.4 FIFO-Based Morphological Reconstruction;143
11.8.2;5.8.2 Lifting-Based Wavelet Kernel;144
11.9;5.9 Limitations and Future Work;148
11.10;5.10 Conclusion;149
12;6 Memory Mapping Functions for Efficient Implementation of WDF Edges ;151
12.1;6.1 Problem Formulation;152
12.2;6.2 Hierarchical Iteration Vectors;155
12.3;6.3 Memory Models;156
12.3.1;6.3.1 The Rectangular Memory Model;157
12.3.2;6.3.2 The Linearized Buffer Model;158
12.4;6.4 Simulation Results;162
12.5;6.5 Conclusion;167
13;7 Buffer Analysis for Complete Application Graphs ;168
13.1;7.1 Problem Formulation;169
13.2;7.2 Buffer Analysis by Simulation;170
13.3;7.3 Polyhedral Representation of WSDF Edges;172
13.3.1;7.3.1 WSDF Lattice;173
13.3.2;7.3.2 Lattice Scaling;174
13.3.3;7.3.3 Out-of-Order Communication;176
13.3.4;7.3.4 Lattice Shifting Based on Dependency Vectors;181
13.3.5;7.3.5 Pipelined Actor Execution;189
13.4;7.4 Lattice Wraparound;190
13.4.1;7.4.1 Principle of Lattice Wraparound;192
13.4.2;7.4.2 Formal Description of the Lattice Wraparound;193
13.4.3;7.4.3 Lattice Shifting for Lattices with Wraparound;194
13.5;7.5 Scheduling of Complete WSDF Graphs;196
13.5.1;7.5.1 Lattice Scaling;197
13.5.2;7.5.2 Lattice Shifting;197
13.5.2.1;7.5.2.1 Determination of Strongly Connected Components;198
13.5.2.2;7.5.2.2 Internal Scheduling of the Strongly Connected Components;199
13.5.2.3;7.5.2.3 Shifting of the Strongly Connected Components;200
13.6;7.6 Buffer Size Calculation;202
13.6.1;7.6.1 ILP Formulation for Buffer Size Calculation;203
13.6.2;7.6.2 Memory Channel Splitting;207
13.7;7.7 Multirate Analysis;209
13.8;7.8 Solution Strategies;213
13.9;7.9 Results;214
13.9.1;7.9.1 Out-of-Order Communication;215
13.9.2;7.9.2 Application to Complex Graph Topologies;216
13.9.3;7.9.3 Memory Channel Splitting;219
13.9.4;7.9.4 Multirate Analysis;221
13.9.5;7.9.5 Limitations;221
13.10;7.10 Conclusion;223
14;8 Communication Synthesis;226
14.1;8.1 Problem Formulation;227
14.2;8.2 Hardware Architecture;231
14.2.1;8.2.1 Read and Write Order Control;232
14.2.1.1;8.2.1.1 Automatic Derivation of the Hierarchical Iteration Maxima and Mapping Matrices;234
14.2.1.2;8.2.1.2 Extended Iteration Vectors;234
14.2.2;8.2.2 Memory Partitioning;235
14.2.3;8.2.3 Source Address Generation;238
14.2.4;8.2.4 Virtual Memory Channel Mapping;243
14.2.4.1;8.2.4.1 Strategy for Virtual Memory Channel Mapping;244
14.2.4.2;8.2.4.2 Condition for Valid Virtual Memory Channel Mapping;246
14.2.4.3;8.2.4.3 Application to the JPEG Shuffle Operation;250
14.2.5;8.2.5 Trading Throughput Against Resource Requirements;250
14.2.6;8.2.6 Sink Address Generation;251
14.2.7;8.2.7 Fill-Level Control;253
14.2.7.1;8.2.7.1 Sink Fill-Level Control;254
14.2.7.2;8.2.7.2 Solution of the PIP;255
14.2.7.3;8.2.7.3 Source Fill-Level Control;257
14.2.8;8.2.8 Elimination of Modular Dependencies;261
14.3;8.3 Determination of Channel Sizes;264
14.4;8.4 Granularity of Scheduling;265
14.4.1;8.4.1 Latency Impact of Coarse-Grained Scheduling;265
14.4.2;8.4.2 Memory Size Impact of Coarse-Grained Scheduling;267
14.4.3;8.4.3 Controlling the Scheduling Granularity;267
14.5;8.5 Results;270
14.5.1;8.5.1 Implementation Strategy for High Clock Frequencies;270
14.5.2;8.5.2 Out-of-Order Communication;271
14.5.3;8.5.3 Out-of-Order Communication with Parallel Data Access;272
14.5.4;8.5.4 Influence of Different Memory Channel Sizes;275
14.5.5;8.5.5 Combination with Data Reuse;276
14.5.6;8.5.6 Impact of Scheduling Granularity;278
14.6;8.6 Conclusion and Future Work;279
15;9 Conclusion ;281
15.1;9.1 Multidimensional System Design;281
15.2;9.2 Discussed Design Steps and Their Major Benefits;282
16;A Buffer Analysis by Simulation;284
16.1;A.1 Efficient Buffer Parameter Determination for the Rectangular Memory Model;22
16.1.1;A.1.1 Monitoring of Live Data Elements;284
16.1.2;A.1.2 Table-Based Buffer Parameter Determination;285
16.1.3;A.1.3 Determination of the Minimum Tables;287
16.1.4;A.1.4 Determination of the Maximum Tables;289
16.1.5;A.1.5 Complexity;292
16.2;A.2 Efficient Buffer Parameter Determination for the Linearized Buffer Model;292
16.2.1;A.2.1 Tree Data Structure for Tracking of Live Data Elements;293
16.2.2;A.2.2 Determination of the Lexicographically Smallest Live Data Element;294
16.2.3;A.2.3 Tree Update;295
16.2.4;A.2.4 Complexity of the Algorithm;297
16.3;A.3 Stimulation by Simulation;297
17;B Abbreviations;299
18;C Formula Symbols;301
19;References;303
20;Index;320