AlgorithmArchitecture Matching for Signal and Image Processing

Lecture Notes in Electrical Engineering

Volume 73

For other titles published in this series, go to

www.springer.com/series/7818

Guy Gogniat Dragomir Milojevic

Adam Morawiec Ahmet Erdogan

Editors

AlgorithmArchitecture Matching

for Signal and

Image Processing

Best papers from Design and Architectures

for Signal and Image Processing 2007 & 2008

& 2009

Editors

Guy Gogniat

Lab-STICC-CNRS, UMR 3192, Centre de

Recherche

Université de Bretagne Sud – UEB

BP 92116

56321 Lorient Cedex

France

[email protected]

Dragomir Milojevic

Université libre de Bruxelles

CP 165-56, Av. FD Roosevelt 50

1050 Bruxelles

Belgium

[email protected]

Adam Morawiec

ECSI

Av. de Vignate 2

38610 Gières

France

[email protected]

Ahmet Erdogan

School of Engineering

The University of Edinburgh

Mayfield Road

EH9 3JL Edinburgh

United Kingdom

[email protected]

ISSN 1876-1100

ISBN 978-90-481-9964-8

e-ISSN 1876-1119

e-ISBN 978-90-481-9965-5

DOI 10.1007/978-90-481-9965-5

Springer Dordrecht Heidelberg London New York

Library of Congress Control Number: 2010938790

No part of this work may be reproduced, stored in a retrieval system, or transmitted in any form or by

any means, electronic, mechanical, photocopying, microfilming, recording or otherwise, without written

permission from the Publisher, with the exception of any material supplied specifically for the purpose

of being entered and executed on a computer system, for exclusive use by the purchaser of the work.

Cover design: VTEX, Vilnius

Printed on acid-free paper

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

Preface

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.

This book presents a collection of selected contributions 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.

The contributions of this book are split into three parts addressing major issues

when designing embedded systems. The first part proposes key contributions in the

domain of architectures for embedded applications and especially for image and

vi Preface

telecommunication processing. The second part focuses on data acquisition and design techniques for embedded systems. First, an optimized sensor for image acquisition is detailed. Then several multiplication and division operators are described.

The end of this part proposes several contributions in the domain of partial and dynamic reconfiguration for signal and image processing. This technology leads to

complex design issues which are addressed in this chapter. The third part targets

embedded systems design. RTOS for embedded systems and scheduling techniques

are first addressed. Finally CAD tools for signal and image processing are detailed.

The coverage of this book is large and provides an in-depth analysis of existing techniques and methodologies to design embedded systems targeting image and signal

processing.

Guy Gogniat

Dragomir Milojevic

Adam Morawiec

Ahmet Erdogan

Contents

Part 1 Architectures for Embedded Applications

Lossless Multi-Mode Interband Image Compression and Its Hardware

Architecture ................................ 3

Xiaolin Chen, Nishan Canagarajah, and Jose L. Nunez-Yanez

Efficient Memory Management for Uniform and Recursive Grid Traversal 27

Tomasz Toczek and Stéphane Mancini

Mapping a Telecommunication Application on a Multiprocessor

System-on-Chip . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

Daniela Genius, Etienne Faure, and Nicolas Pouillon

Part 2 Data Acquisition and Embedded Systems

A Standard 3.5T CMOS Imager Including a Light Adaptive System for

Integration Time Optimization . . . . . . . . . . . . . . . . . . . . . 81

Gilles Sicard, Estelle Labonne, and Robin Rolland

Approximate Multiplication and Division for Arithmetic Data Value

Speculation in a RISC Processor . . . . . . . . . . . . . . . . . . . . 95

Daniel R. Kelly, Braden J. Phillips, and Said Al-Sarawi

RANN: A Reconfigurable Artificial Neural Network Model for Task

Scheduling on Reconfigurable System-on-Chip . . . . . . . . . . . . 117

Daniel Chillet, Sébastien Pillement, and Olivier Sentieys

A New Three-Level Strategy for Off-Line Placement of Hardware Tasks

on Partially and Dynamically Reconfigurable Hardware . . . . . . . 145

Ikbel Belaid, Fabrice Muller, and Maher Benjemaa

End-to-End Bitstreams Repository Hierarchy for FPGA Partially

Reconfigurable Systems . . . . . . . . . . . . . . . . . . . . . . . . . 171

Jérémie Crenne, Pierre Bomel, Guy Gogniat, and Jean-Philippe Diguet

vii

viii Contents

Part 3 Embedded Systems Design

SystemC Multiprocessor RTOS Model for Services Distribution on

MPSoC Platforms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197

Benoît Miramond, Emmanuel Huck, Thomas Lefebvre, and François

Verdier

A List Scheduling Heuristic with New Node Priorities and Critical Child

Technique for Task Scheduling with Communication Contention . . 217

Pengcheng Mu, Jean-François Nezan, and Mickaël Raulet

Multiprocessor Scheduling of Dataflow Programs within the

Reconfigurable Video Coding Framework . . . . . . . . . . . . . . . 237

Jani Boutellier, Christophe Lucarz, Victor Martin Gomez, Marco

Mattavelli, and Olli Silvén

A High Level Synthesis Flow Using Model Driven Engineering . . . . . . 253

Sébastien Le Beux, Laurent Moss, Philippe Marquet, and Jean-Luc

Dekeyser

Generation of Hardware/Software Systems Based on CAL Dataflow

Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

Richard Thavot, Romuald Mosqueron, Julien Dubois, and Marco

Mattavelli

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293

Contributors

Said Al-Sarawi CHiPTec, Centre for High Performance Integrated Technologies

and Systems, The University of Adelaide, Adelaide, Australia,

[email protected]

Ikbel Belaid University of Nice-Sophia Antipolis/LEAT-CNRS, 250 rue Albert

Einstein, 06560 Valbonne, France, [email protected]

Maher Benjemaa National Engineering School of Sfax/Research Unit ReDCAD,

Sfax, Tunisia, [email protected]

Sebastien Le Beux Institut des Nanotechnologies de Lyon, Ecole Centrale de

Lyon, 36, Avenue Guy de Collongue, 69134 Ecully Cedex, France,

[email protected]

Pierre Bomel LAB-STICC, Université Européenne de Bretagne, Lorient, France,

[email protected]

Jani Boutellier Computer Science and Engineering Laboratory, University of

Oulu, Oulu, Finland, [email protected]

Nishan Canagarajah University of Bristol, Bristol, UK,

[email protected]

Xiaolin Chen University of Bristol, Bristol, UK, [email protected]

Daniel Chillet University of Rennes 1, IRISA/INRIA, BP 80518, 6 rue de Kerampont, F22305 Lannion, France, [email protected]

Jérémie Crenne LAB-STICC, Université Européenne de Bretagne, Lorient, France,

[email protected]

Jean-Luc Dekeyser LIFL and INRIA Lille Nord-Europe, Parc Scientifique de

la Haute Borne, Park Plaza, Bât A, 40 avenue Halley, Villeneuve d’Ascq 59650,

France, [email protected]

Jean-Philippe Diguet LAB-STICC, Université Européenne de Bretagne, Lorient,

France, [email protected]

x Contributors

Julien Dubois Laboratoire LE2I, Université de Bourgogne, 21000 Dijon, France,

[email protected]

Etienne Faure SoC Department, LIP6, 4 place Jussieu, 75252 Paris Cedex, France,

[email protected]

Daniela Genius SoC Department, LIP6, 4 place Jussieu, 75252 Paris Cedex,

France, [email protected]

Guy Gogniat LAB-STICC, Université Européenne de Bretagne, Lorient, France,

[email protected]

Victor Martin Gomez Computer Science and Engineering Laboratory, University

of Oulu, Oulu, Finland, [email protected]

Emmanuel Huck ETIS Laboratory, UMR CNRS 8051, Université de CergyPontoise/ENSEA, 6, avenue du Ponceau, 95014 Cergy-Pontoise, France,

[email protected]

Daniel R. Kelly CHiPTec, Centre for High Performance Integrated Technologies

and Systems, The University of Adelaide, Adelaide, Australia,

[email protected]

Estelle Labonne TIMA Laboratory (CNRS, Grenoble INP, UJF), Grenoble, France

Thomas Lefebvre ETIS Laboratory, UMR CNRS 8051, Université de CergyPontoise/ENSEA, 6, avenue du Ponceau, 95014 Cergy-Pontoise, France,

[email protected]

Christophe Lucarz Microelectronic Systems Laboratory, École Polytechnique

Fédérale de Lausanne, Lausanne, Switzerland, [email protected]

Stéphane Mancini GIPSA-lab, INPG-CNRS, 961 rue de la Houille Blanche Domaine Universitaire-B.P. 46, 38402, Saint Martin d’Heres, France,

[email protected]

Philippe Marquet LIFL and INRIA Lille Nord-Europe, Parc Scientifique de la

Haute Borne, Park Plaza, Bât A, 40 avenue Halley, Villeneuve d’Ascq 59650,

France, [email protected]

Marco Mattavelli SCI-STI-MM, Ecole Polytechnique Fédérale de Lausanne, CH

1015 Lausanne, Switzerland, [email protected]

Marco Mattavelli Microelectronic Systems Laboratory, École Polytechnique

Fédérale de Lausanne, Lausanne, Switzerland, [email protected]

Benoît Miramond ETIS Laboratory, UMR CNRS 8051, Université de CergyPontoise/ENSEA, 6, avenue du Ponceau, 95014 Cergy-Pontoise, France,

[email protected]

Romuald Mosqueron SCI-STI-MM, Ecole Polytechnique Fédérale de Lausanne,

CH 1015 Lausanne, Switzerland, [email protected]

Contributors xi

Laurent Moss Ecole Polytechnique de Montréal, Campus de l’Université de Montréal, 2500, chemin de Polytechnique, 2900 boulevard Edouard-Montpetit, Montréal, Quebec H3T 1J4, Canada, [email protected]

Pengcheng Mu Ministry of Education Key Lab for Intelligent Networks and Network Security, School of Electronic and Information Engineering, Xi’an Jiaotong

University, Xi’an 710049, P.R. China, [email protected]

Fabrice Muller University of Nice-Sophia Antipolis/LEAT-CNRS, 250 rue Albert

Einstein, 06560 Valbonne, France, [email protected]

Jean-François Nezan IETR/Image and Remote Sensing Group, CNRS UMR

6164/INSA Rennes, 20, avenue des Buttes de Coësmes, 35043 Rennes Cedex,

France, [email protected]

Jose L. Nunez-Yanez University of Bristol, Bristol, UK,

[email protected]

Braden J. Phillips CHiPTec, Centre for High Performance Integrated Technologies and Systems, The University of Adelaide, Adelaide, Australia,

[email protected]

Sébastien Pillement University of Rennes 1, IRISA/INRIA, BP 80518, 6 rue de

Kerampont, F22305 Lannion, France