Design of Image Processing Embedded Systems Using Multidimensional Data Flow

Embedded Systems

Series Editors

Nikil D. Dutt

Peter Marwedel

Grant Martin

For further volumes:

http://www.springer.com/series/8563

Joachim Keinert ˙ Jürgen Teich

Design of Image Processing

Embedded Systems Using

Multidimensional Data Flow

123

Joachim Keinert

Michaelstraße 40

D-90425 Nürnberg

Germany

[email protected]

Jürgen Teich

Department of Computer Science 12

University of Erlangen-Nuremberg

Am Weichselgarten 3

D-91058 Erlangen

Germany

[email protected]

ISBN 978-1-4419-7181-4 e-ISBN 978-1-4419-7182-1

DOI 10.1007/978-1-4419-7182-1

Springer New York Dordrecht Heidelberg London

Library of Congress Control Number: 2010937183

c Springer Science+Business Media, LLC 2011

All rights reserved. This work may not be translated or copied in whole or in part without the written

permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York,

NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in

connection with any form of information storage and retrieval, electronic adaptation, computer

software, or by similar or dissimilar methodology now known or hereafter developed is forbidden.

The use in this publication of trade names, trademarks, service marks, and similar terms, even if

they are not identified as such, is not to be taken as an expression of opinion as to whether or not

they are subject to proprietary rights.

Printed on acid-free paper

Springer is part of Springer Science+Business Media (www.springer.com)

Preface

Overview of This Book

With the availability of chips offering constantly increasing computational performance and

functionality, design of more and more complex applications becomes possible. This is partic￾ularly true for the domain of image processing, which is characterized by huge computation

efforts. Unfortunately, this evolution risks to be stopped by the fact that employed design

methodologies remain on a rather low level of abstraction. The resulting design gap causes

increasing development costs or even project failure and thus threatens the technical progress.

Consequently, new design methodologies are urgently required. A corresponding review

about the state of the art reveals that different approaches are competing in order to solve

the above-mentioned challenges. The proposed techniques range from behavioral compilers

accepting standard C or Matlab code as input, over block-based design methods such as

Simulink and SystemC, to data flow specifications and polyhedral analysis. Each of them

offers important benefits, such as quick and easy hardware prototyping, higher levels of

abstractions, and enhanced system and algorithm analysis on different levels of granularity.

However, a solution combining the advantages of all these approaches is still missing. As a

consequence, system level design of image processing applications still causes various chal￾lenges. Corresponding examples are the lack to handle the resulting system complexity or to

cover important algorithmic properties. Equally, the synthesis of high-performance hardware

implementations is still difficult.

Fortunately, recent research is able to demonstrate that multidimensional data flow seems

to be a promising technique solving these drawbacks, because it combines the advantages

of block-based specification, data flow-related system analysis, and polyhedral optimization

on different levels of granularity. These benefits enable, for instance, the verification of the

application specification on a very high level of abstraction, the calculation of required mem￾ory sizes for correct algorithm implementation considering different design tradeoffs, and

the synthesis of high-performance communication infrastructures and algorithm implemen￾tations.

However, despite these advantages, multidimensional data flow still lives quite in the shad￾ows and is rarely adopted in both commercial and academic systems. Consequently, this book

aims to give an encompassing description of the related techniques in order to demonstrate

how multidimensional data flow can boost system implementation. In particular, this book

identifies some of the requirements for system level design of image processing algorithms

and gives an encompassing review in how far they are met by different approaches found in

literature and industry. Next, a multidimensional data flow model of computation is intro￾v

vi Preface

duced that is particularly adapted for image processing applications. Its ability to represent

both static and data-dependent point, local, and global algorithms as well as the possibil￾ity for seamless interaction with already existing one-dimensional models of computation

permit the description of complex systems. Based on these foundations, it is shown how

system analysis and synthesis can be simplified by automatic tool support. In particular, it is

explained in detail, how the amount of memory required for correct implementation can be

derived by means of polyhedral analysis and how communication primitives for high-speed

multidimensional communication can be generated. Application to different examples such as

a lifting-based wavelet transform, JPEG2000 encoding, JPEG decoding, or multi-resolution

filtering illustrates the concrete application of these techniques and demonstrates the capa￾bility to deliver better results in shorter time compared to related approaches while offering

more design flexibility.

Target Audience

As a consequence of the encompassing description of a system level design methodology

using multidimensional data flow, the book addresses particularly all those active or interested

in the research, development, or deployment of new design methodologies for data-intensive

embedded systems. These are intended to process huge amounts of data organized in form

of array streams. Image processing applications are particular prominent examples of this

algorithm class and are thus in the focus of this book.

In addition to this primary target audience, the book is also useful for system design

engineers by describing new technologies for inter-module communication as well as design

tradeoffs that can be exploited in embedded systems. And finally, the book wants to promote

multidimensional data flow and makes it more accessible for education and studies by giving

an encompassing description of related techniques, use cases, and applications.

Prerequisites

Since this book bridges different technologies such as data flow modeling, polyhedral analy￾sis, and hardware synthesis, important concepts necessary in the context of multidimensional

data flow are shortly summarized before their application. By this means it is avoided to

unnecessarily complicate understanding of the presented material. Nevertheless, it is assumed

that the reader is skilled in fundamental maths such as vector spaces and matrix multiplica￾tion. Integer linear optimization is used in both memory analysis and communication syn￾thesis. While the fundamentals are shortly summarized in this book, additional knowledge

can deliver more detailed insights. Furthermore, familiarity with basic concepts of image

processing helps in understanding the presented material. For a clearer picture of the overall

concepts, some experiences in software and hardware implementation are helpful, although

not strictly necessary.

How the Book Is Organized

The content of this book can be categorized in four major parts as depicted in Fig. 1:

Preface vii

• Introductory background information

• Related techniques

• Multidimensional modeling

• Analysis and synthesis

Fig. 1 Arrows depict concepts and information used in the corresponding target book parts. Bold

arrows define information that is fundamental for understanding the chapter which the arrow

points to

The first part containing the introductory background information basically aims to clarify

the purpose and the main focus of the described technologies. To this end, Chapter 1 (Intro￾duction) explains the need for new design technologies and overviews the overall design flow

described in this book. Chapter 2 (Design of Image Processing Applications) adds some gen￾eral considerations about the design of image processing embedded systems and exemplifies

a JPEG2000 encoder in order to clarify the type of algorithms that are addressed in this book.

The insights gained during its manual development have been formulated into a correspond￾ing set of requirements that shall be taken into account in the rest of this monograph.

viii Preface

The second part about related techniques summarizes concepts useful for system level

design of image processing applications. To this end, Chapter 3 (Fundamentals and Related

Work) reviews related approaches and evaluates their benefits for system level design of

image processing applications. In particular, it investigates a huge amount of different specifi￾cation techniques ranging from sequential languages enriched by communicating sequential

processes up to multidimensional data flow models. Furthermore, it evaluates their ability

to describe complex image processing applications. Additionally, Chapter 3 also summarizes

the capacities of several behavioral compilers, buffer analysis techniques, and communication

synthesis approaches. Furthermore, it discusses several system level design methodologies.

Subsequently, Chapter 4 presents an overview on the ESL tool SYSTEMCODESIGNER, since

it shall serve as an example how to combine multidimensional system design with available

ESL techniques. Furthermore, a case study in form of a Motion-JPEG decoder demonstrates

the potential of ESL design for image processing applications and discusses lessons learned

for both application modeling and synthesis.

Both Chapters 3 and 4 are thus intended to provide further insights into system level design

of embedded systems. In particular, they aim to clarify the benefits of multidimensional data

flow and its interaction with existing technologies. Consequently, both chapters can be con￾sulted as needed. The only exception represents Section 3.1.3 (One-Dimensional Data Flow)

that is recommended for all those not being familiar with one-dimensional data flow models

of computation.

Detailed discussion of multidimensional system level design then starts with the third and

central book part about multidimensional modeling, subdivided into two chapters. Chapter 5

(Windowed Data Flow (WDF)) introduces the windowed data flow (WDF) model of com￾putation used for application modeling in the remainder of this monograph. This includes

both a theoretical discussion and the application to two concrete examples, namely the binary

morphological reconstruction and the JPEG2000 lifting-based wavelet transform. In particu￾lar Sections 5.1 (Sliding Window Communication), 5.2 (Local WDF Balance Equation), 5.3

(Communication Order), and 5.4 (Communication Control) introduce fundamental concepts

required in the remainder of this monograph. The same holds for Sections 6.1 (Problem

Formulation), 6.2 (Hierarchical Iteration Vectors), and 6.3 (Memory Models). It discusses

fundamental concepts of memory organization within multidimensional arrays as required

in the remaining chapters. In particular, a study is performed that compares two different

memory allocation functions in terms of memory efficiency.

Based on those multidimensional modeling concepts, the fourth part of this book then

addresses system analysis and synthesis. More precisely, Chapter 7 (Buffer Analysis for

Complete Application Graphs) is dedicated to the question of automatic buffer size deter￾mination required for correct system implementation. Taking the results of Chapter 6 into

account, Chapter 7 presents a method for polyhedral buffer size requirement calculation in

case of complex graph topologies. Application to several examples like the lifting-based

wavelet transform, JPEG2000 block building, and multi-resolution image filtering demon￾strates that the resulting analysis times are suitable for system level design of complex

applications and competitive with alternative approaches. Furthermore, it will be shown that

analytical methods deliver better solutions in shorter time compared to buffer analysis via

simulation, while offering more design tradeoffs.

The so-derived buffer sizes can be directly used for efficient communication synthesis.

To this end, Chapter 8 (Communication Synthesis) considers the derivation of high-speed

hardware communication primitives from WDF specifications. This allows to interconnect

hardware modules by a high-performance point-to-point communication. The corresponding

technology can be used both for classical hardware design and for system level design with

Preface ix

multidimensional data flow. To this end, Chapter 8 presents all analysis steps required to

transform a WDF edge into an efficient hardware implementation. Application to different

examples originating from a JPEG2000 encoder and a JPEG decoder demonstrates the bene￾fits of the methodology. Furthermore, Chapter 8 illustrates how the hardware communication

primitive can be combined with a behavioral synthesis tool in order to handle overlapping

sliding windows.

The book is concluded by Chapter 9. Appendix A (Buffer Analysis by Simulation) then

delivers some supplementary information concerning a buffer analysis performed during sim￾ulation as applied in Chapter 6. Appendix B summarizes the abbreviations used within this

book while Appendix C contains repeatedly used formula symbols.

Distinct Features and Benefits of This Book

Although combining the benefits of various design methodologies such as block-based sys￾tem design, high-level simulation, system analysis, and polyhedral optimization, multidi￾mensional data flow is still not very widely known. Whereas there exist several books dis￾cussing the one-dimensional counterparts, similar literature is not available for multidimen￾sional modeling. Consequently, this book aims to provide a detailed insight into these design

methodologies. Furthermore, it wants to provide an encompassing review on related work

and techniques in order to show their relation to multidimensional data flow.

By these means, the book is intended to contribute to the promotion of multidimensional

data flow in both academic and industrial projects. Furthermore, it aims to render the sub￾ject more accessible for education. In more detail, this monograph provides the following

contributions:

• First encompassing book on multidimensional data flow covering different models of

computation. In particular, both modeling, synthesis, and analysis are discussed in detail

demonstrating the potential of the underlying concepts.

• The book bridges different technologies such as data flow modeling, polyhedral analysis,

and hardware synthesis, which are normally only considered independently of each other

in different manuscripts. Consequently, their combination possess significant difficulties,

since even the terminology used in the different domains varies. By combining the above￾mentioned technologies in one book and describing them in a consistent way, the book can

leverage new potential in system design.

• Analysis in how far multidimensional data flow can better fit the designers’ requirements

compared to alternative description techniques, such as well-known one-dimensional data

flow or communicating sequential processes.

• Description of how multidimensional data flow can coexist with classical one-dimensional

models of computation.

• Explanation of a novel architecture for efficient and flexible high-speed communication

in hardware that can be used in both manual and automatic system design and that offers

various design alternatives trading achievable throughput against required hardware sizes.

• Detailed description of how to calculate required buffer sizes for implementation of static

image processing applications. Various illustrations help to apply the method both in ESL

tools and in manual system design.

• Compared to books on geometric memory analysis, a significant extension assures that

this method can be applied for data reordering and image subsampling in hardware imple￾mentations.

x Preface

• New concepts for embedded system design, such as trading communication buffer sizes

against computational logic by different scheduling mechanisms.

• Various experimental results in order to demonstrate the capabilities of the described

architectures and design methods. In particular, several example applications such as

JPEG2000 encoding, Motion-JPEG decoding, binary morphological reconstruction, and

multi-resolution filtering are discussed.

The content of this book has been created, edited and verified with highest possible care.

Nevertheless, errors and mistakes of any kind cannot be excluded. This includes, but is not

restricted to, missing information, wrong descriptions, erroneous results, possible algorithmic

mistakes or citation flaws causing that algorithms may not work as expected.

Erlangen, Germany Joachim Keinert

Jürgen Teich

Acknowledgments

This book is the result of a 5-year research activity that I could conduct in both the Fraunhofer

Institute for Integrated Circuits IIS in Erlangen and at the Chair for Hardware-Software￾Co-Design belonging to the University of Erlangen-Nuremberg. This constellation allowed

me to combine the theory of system level design with the requirements for design of high￾performance image processing applications. In particular, the experiences gained during the

development of multiple embedded devices for image processing within the Fraunhofer

research organization have been a valuable inspiration for the presented technologies. There￾fore, I want to express my gratitude toward all those who supported me within this period of

time.

I especially want to thank Prof. Jürgen Teich for supervising the underlying research

activity and for his motivation to tackle the right mathematical problems, in particular

data flow graph models of computation and polyhedral analysis. My superior at the Fraun￾hofer Institute for Integrated Circuits, Dr. Siegfried Fößel, also merits special thanks for

the provided support and for his help in making this book possible. Dr. Christian Haubelt

from the University of Erlangen-Nuremberg contributed to this book by means of multi￾ple reviews and by his coordination of the SYSTEMCODESIGNER tool. This enabled its

extension with a multidimensional design methodology in order to demonstrate the under￾lying concepts and techniques. In this context I could particularly profit from the work of

Joachim Falk, designer of the SYSTEMOC library and of a huge tool set for manipula￾tion of the resulting graph topologies. Similarly, the cooperation with Hritam Dutta and

Dr. Frank Hannig has been an important prerequisite for combining data flow-based system

design with polyhedral analysis. In addition, the various discussions with Prof. Shuvra Bhat￾tacharyya, member of the University of Maryland, helped to better understand and evaluate

the advantages of multidimensional system design. And of course I also want to thank Mr.

Charles Glaser from Springer for his assistance in achieving this book.

Erlangen, Germany Joachim Keinert

May 2010

xi

Contents

1 Introduction ........................................................... 1

1.1 Motivation and Current Practices .................................... 1

1.2 Multidimensional System Level Design Overview ..................... 4

2 Design of Image Processing Applications .................................. 9

2.1 Classification of Image Processing Algorithms . . . . . . . . . . . . . . . . . . . . . . . . 10

2.2 JPEG2000 Image Compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.3 Parallelism of Image Processing Applications . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4 System Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.4.1 Design Gap Between Available Software Solution and Desired

Hardware Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4.2 Lack of Architectural Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4.3 Missing Possibility to Explore Consequences of Implementation

Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.4.4 Manual Design of Memory System. . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4.5 Lack to Simulate the Overall System . . . . . . . . . . . . . . . . . . . . . . . . 18

2.4.6 Inability to Precisely Predict Required Computational Effort

for Both Hardware and Software . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.5 Requirements for System Level Design of Image Processing Applications . 18

2.5.1 Representation of Global, Local, and Point Algorithms . . . . . . . . . 19

2.5.2 Representation of Task, Data, and Operation Parallelism . . . . . . . . 19

2.5.3 Capability to Represent Control Flow in Multidimensional

Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.5.4 Tight Interaction Between Static and Data-Dependent Algorithms 19

2.5.5 Support of Data Reordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.5.6 Fast Generation of RTL Implementations for Quick Feedback

During Architecture Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.5.7 High-Level Verification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.5.8 High-Level Performance Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.5.9 Tool-Supported Design of Memory Systems . . . . . . . . . . . . . . . . . . 20

2.6 Multidimensional System Level Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3 Fundamentals and Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1 Behavioral Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

3.1.1 Modeling Approaches. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

xiii

xiv Contents

3.1.2 Sequential Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

3.1.3 One-Dimensional Data Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

3.1.4 Multidimensional Data Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.1.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3.2 Behavioral Hardware Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.2.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2.2 SA-C. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2.3 ROCCC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

3.2.4 DEFACTO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2.5 Synfora PICO Express . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

3.2.6 MMAlpha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

3.2.7 PARO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3.2.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3 Memory Analysis and Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

3.3.1 Memory Analysis for One-Dimensional Data Flow Graphs. . . . . . 57

3.3.2 Array-Based Analysis. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.3.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.4 Communication and Memory Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

3.4.1 Memory Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.4.2 Parallel Data Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.4.3 Data Reuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.4.4 Out-of-Order Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

3.4.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3.5 System Level Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

3.5.1 Embedded Multi-processor Software Design . . . . . . . . . . . . . . . . . . 68

3.5.2 Model-Based Simulation and Design . . . . . . . . . . . . . . . . . . . . . . . . 71

3.5.3 System Level Mapping and Exploration . . . . . . . . . . . . . . . . . . . . . . 77

3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

4 Electronic System Level Design of Image Processing Applications with

SYSTEMCODESIGNER . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.1 Design Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

4.1.1 Actor-Oriented Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

4.1.2 Actor Specification . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.1.3 Actor and Communication Synthesis . . . . . . . . . . . . . . . . . . . . . . . . 83

4.1.4 Automatic Design Space Exploration . . . . . . . . . . . . . . . . . . . . . . . . 84

4.1.5 System Building . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.1.6 Extensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.2 Case Study for the Motion-JPEG Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.2.1 Comparison Between VPC Estimates and Real Implementation . . 87

4.2.2 Influence of the Input Motion-JPEG Stream . . . . . . . . . . . . . . . . . . 90

4.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

5 Windowed Data Flow (WDF) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

5.1 Sliding Window Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.1.1 WDF Graph and Token Production . . . . . . . . . . . . . . . . . . . . . . . . . . 94

5.1.2 Virtual Border Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

5.1.3 Token Consumption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97