Algorithm-Architecture Matching for Signal and Image Processing (eBook)

Best papers from Design and Architectures for Signal and Image Processing 2007 & 2008 & 2009

Guy Gogniat, Dragomir Milojevic, Adam Morawiec, Ahmet Erdogan (Herausgeber)

eBook Download: PDF

2010 | 2011
XII, 296 Seiten
Springer Netherland (Verlag)
978-90-481-9965-5 (ISBN)

Infos

Advances in signal and image processing together with increasing computing power are bringing mobile technology closer to applications in a variety of domains like automotive, health, telecommunication, multimedia, entertainment and many others. The development of these leading applications, involving a large diversity of algorithms (e.g. signal, image, video, 3D, communication, cryptography) is classically divided into three consecutive steps: a theoretical study of the algorithms, a study of the target architecture, and finally the implementation. Such a linear design flow is reaching its limits due to intense pressure on design cycle and strict performance constraints. The approach, called Algorithm-Architecture Matching, aims to leverage design flows with a simultaneous study of both algorithmic and architectural issues, taking into account multiple design constraints, as well as algorithm and architecture optimizations, that couldn't be achieved otherwise if considered separately. Introducing new design methodologies is mandatory when facing the new emerging applications as for example advanced mobile communication or graphics using sub-micron manufacturing technologies or 3D-Integrated Circuits. This diversity forms a driving force for the future evolutions of embedded system designs methodologies.

The main expectations from system designers' point of view are related to methods, tools and architectures supporting application complexity and design cycle reduction. Advanced optimizations are essential to meet design constraints and to enable a wide acceptance of these new technologies.

Algorithm-Architecture Matching for Signal and Image Processing presents a collection of selected contributions from both industry and academia, addressing different aspects of Algorithm-Architecture Matching approach ranging from sensors to architectures design. The scope of this book reflects the diversity of potential algorithms, including signal, communication, image, video, 3D-Graphics implemented onto various architectures from FPGA to multiprocessor systems. Several synthesis and resource management techniques leveraging design optimizations are also described and applied to numerous algorithms.

Algorithm-Architecture Matching for Signal and Image Processing should be on each designer's and EDA tool developer's shelf, as well as on those with an interest in digital system design optimizations dealing with advanced algorithms.

Inhalt

Preface 5
Contents 7
Contributors 9
Architectures for Embedded Applications 12
Lossless Multi-Mode Interband Image Compression and Its Hardware Architecture 13
Introduction 13
An Overview of LMMIC 15
Multi-Mode Strategy 17
Preprocessing 17
Run-Mode 17
Ternary-Mode 18
Regular-Mode 19
Band Shifting and Gradient-Based Switching 19
Band Shifting for Inter-Band Prediction 20
Gradient-Based Switching 21
Adaptation in Run-Mode and Ternary-Mode 22
Context Modelling 23
Performance Comparison 23
Hardware Architecture 26
Lossless Image Modelling 26
Probability Estimator and Arithmetic Coding 28
Arithmetic Coding 29
Probability Estimation 29
Overview 29
Working Mechanism of the Context Trees 29
Context Tree Initialization 31
Choice of Context Tree Node Size 32
Output of Probability Estimation 32
Architecture of Probability Estimator 33
Conclusions 35
References 35
Efficient Memory Management for Uniform and Recursive Grid Traversal 37
Introduction 37
State of the Art 39
Dataset Traversal 39
Memory Management 40
System Architecture 42
The nD-AP Cache 42
Uniform Grids 43
Uniform Grid Traversal 43
Uniform Grid Caching 45
Recursive Grids 46
Caching the RG Data Structure 46
Recursive Grids 46
RG Cache 47
Improving Reference Locality 47
Recursive Grid Traversal 49
Neighbour Finding Unit 49
Phase-Locked Ray Beam Propagation 50
Results 52
Hardware Complexity 53
Uniform Grid Traversal 53
Hierarchical Grid Traversal 54
Cache Efficiency 54
Cache Efficiency of the Uniform Grid Traversal 55
Visualization 55
Sinogram Computing 56
Cache Efficiency of the Recursive Grid Traversal 57
Discussion 58
Improvements 59
Conclusion 59
References 60
Mapping a Telecommunication Application on a Multiprocessor System-on-Chip 62
Introduction 62
Related Work 63
Application Specification 64
The Target Hardware Architecture 66
The Telecommunication Platform 67
The Classification Application 69
The Application Task Graph 69
DSX Design Space Explorer 71
DSX Architecture Description 71
DSX Application Description 72
DSX I/O Coprocessor Description 72
Classification and Scheduling Tasks 73
Bootstrap Task 74
DSX Mapping Description 75
Eliminating the Bottlenecks 77
Accesses to the InputChannels 78
Simultaneous Accesses to Memory Banks 79
Burst Size 80
Performance Results 81
Conclusion and Perspectives 83
References 84
Data Acquisition and Embedded Systems 87
A Standard 3.5T CMOS Imager Including a Light Adaptive System for Integration Time Optimization 88
Introduction 88
Automatic control of the integration time value 91
Architecture of the Sensor 93
Overview and Measures of Our Circuit 95
Discussion 97
Conclusions and Perspectives 97
References 99
Approximate Multiplication and Division for Arithmetic Data Value Speculation in a RISC Processor 101
Introduction 102
Contributions 102
Overview 103
Background 103
Approximate Arithmetic 103
Arithmetic Data Value Speculation 103
Simulation and Synthesis Tools 104
SimpleScalar 104
MediaBench 105
Operand Caches 105
Logic Synthesis 106
Approximate Multiplication 106
Counters 106
Multiplier Topology 106
Multiplier Results 107
Approximate Unsigned Division 111
Division Algorithm 112
Divider Implementation 112
Divider Results 114
Simulation of a RISC Processor with ADVS 116
Operand Cache Simulation 116
SimpleScalar Simulation 117
Conclusions 120
References 121
RANN: A Reconfigurable Artificial Neural Network Model for Task Scheduling on Reconfigurable System-on-Chip 123
Introduction 123
Problem Definition 124
Related Works 126
Temporal and Spatial Task Scheduling 126
ANNs Models for Task Scheduling 127
Implementation of ANNs 130
Scheduling for Reconfigurable Hardware using ANN 131
Management of an Unfixed Number of Tasks Within the Reconfigurable Unit 131
Management of Task Dependencies 133
Example of an RANN Structure 135
Discussion 136
Convergence Case Study 138
Implementation Results of the RANN 142
Execution Performance Comparisons 146
Conclusion 146
References 148
A New Three-Level Strategy for Off-Line Placement of Hardware Tasks on Partially and Dynamically Reconfigurable Hardware 151
Introduction 151
Related Work 152
Level 1: Off-Line Flow of Hardware Task Classification 154
Flow Terminology 154
Application Level 154
Physical Level 155
Flow Steps 157
Step 1: RZ Types Search or Hardware Task Classes Search 157
Step 2: Hardware Task Classification 159
Step 3: Decision of Increasing the Number of RZs 160
Level 2: RPBs Partitioning on the Target Device 160
Level 3: Two-Level Fitting 162
Modeling of Placement Problem 162
Exhaustive Complete Resolution of Placement Problem 166
Non-Exhaustive Complete Resolution of Placement Problem 167
Application and Results 170
Conclusion 174
References 175
End-to-End Bitstreams Repository Hierarchy for FPGA Partially Reconfigurable Systems 176
Introduction 176
Hierarchy Level L1 179
Cache Architecture 181
Hardware Architecture 181
Results 183
Hierarchy Level L2 183
Data Link over Ethernet 100 Mb/s 184
Error Rates 185
Hardware Architecture 186
Software Achitecture 187
Results 189
Hierarchy Level L3 190
Common Used Transport Protocols 190
TCP/IP Architecture Model 191
Software Architecture 192
lwIP as a TCP/IP Networking Stack 192
Software DPR Protocol 193
Hardware Architecture 194
Results 195
Conclusion and Perspectives 197
References 198
Embedded Systems Design 200
SystemC Multiprocessor RTOS Model for Services Distribution on MPSoC Platforms 201
Introduction 201
Related Work 202
RTOS Modeling 203
MPSoC Modeling and RTOS Distribution 206
Distant Communications and Services Requests 206
CAS Model 207
A Tool for Specific OS Definition 209
Goal of the Tool 209
Presentation of the DOGME Tool 209
Experiments and Results 212
A Robotic Vision System 212
Deployment Exploration 213
Results 215
Conclusion 217
References 218
A List Scheduling Heuristic with New Node Priorities and Critical Child Technique for Task Scheduling with Communication Contention 220
Introduction 220
Models and Definitions 222
DAG Model 222
Topology Graph Model 223
Task Scheduling with Communication Contention 224
Node Levels with Communication Contention 226
Existing Node Levels 226
New Node Levels 227
List Scheduling Heuristic 229
Sorting Nodes with Five Groups of Node Priorities 229
Processor Selection 229
Node and Edge Scheduling 231
Analysis of Time Complexity 232
Experimental Results 233
Comparison with an Example 233
Comparison with Random DAGs 234
Time Complexity 236
Conclusions and Prospects 237
References 238
Multiprocessor Scheduling of Dataflow Programs within the Reconfigurable Video Coding Framework 240
Introduction 240
Concepts of the Reconfigurable Video Coding Framework 241
The CAL Language 242
The Scheduling Approach 244
Case Study: MPEG-4 SP Decoder 245
Design Space Exploration 247
The Results 251
Conclusion 253
References 254
A High Level Synthesis Flow Using Model Driven Engineering 255
Introduction 255
Design Challenges 256
HLS Tool User 256
HLS Tool Designer 257
Proposed HLS Flow 257
Related Works 258
Model Driven Engineering 260
Model and Metamodel 261
Model Transformations 261
High Level Specification Models 263
UML Model 263
ISP Model and UML2ISP 265
Implementation at a Low Level 266
RTL Model 266
ISP 2RTL Transformation 267
RTL2VHDL Transformation 270
Case Study 270
UML Model 271
Generated Hardware Accelerator 272
Conclusion 274
References 274
Generation of Hardware/Software Systems Based on CAL Dataflow Description 277
Introduction 277
Objectives and principles 279
CAL Actor Language 280
Objectives: Unified Specification Formalism 281
The Global Interfaces Methodology 282
Effectiveness of CAL2C and CAL2HDL 283
First Design Case: MPEG-4 SP Decoder 283
Second Design Case: the Code Bar Decoder 285
Interfaces Driver Generation for Implementation 286
Driver Architecture Overview 286
Serialization and Deserialization Process 288
Comparison of the Efficiency 288
Comparison of the Hardware Implementation 289
Algorithm Synthesis 290
Design Cases with Interfaces Driver Generation 290
Ethernet Link 291
Ethernet on Cyclone II 291
Ethenet Link on Virtex 5 292
PCI Link 292
Conclusion 292
References 293
Index 295

Produkt-Details

• Erscheint lt. Verlag: 20.10.2010
• Reihe/Serie: Lecture Notes in Electrical Engineering
• Reihe/Serie: Lecture Notes in Electrical Engineering
• Zusatzinfo: XII, 296 p.
• Verlagsort: Dordrecht
• Sprache: englisch
• Themenwelt: Informatik ► Grafik / Design ► Digitale Bildverarbeitung
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Technik ► Elektrotechnik / Energietechnik
• Schlagworte: algorithm • Architecture • Design Methodologies • Hardware/Software Co-Design • Image Processing • Matching • Signal Processing
• ISBN-10: 90-481-9965-4 / 9048199654
• ISBN-13: 978-90-481-9965-5 / 9789048199655