Embedded multiprocessors: scheduling and synchronization

dded

lltiprocessors

Ang and Synchronization

SUNDARARAJAN SRIRAM

SHUVRA S. BHATTACHARYYA

Tsuhan Chen, Carne~ie

Sadaoki Furui, Tokyo lnstifut~ of ~echnolo~y

Aggelos K. Katsaggeios, ~o~~~es~ern University

S. Y. Kung, ~rinceton Un~~ersity

P. K. Raja Rajasekaran, Texas lnsfru~ents

John A. Sorenson, Technical University of ~en~ar~

1. Digital Signal Processing for Multimedia Systems, edited by

~eshab K. Parhi and Taka0 ~i~hituni

[L. Multimedia Systems, Standards, and Networks, edited by Atul Puri

and Tsu~an Chen

3. Embedded ~ultiprocessors: Sc~~duling and S~c~onization,

Sun~ararajarl Sriram and Shuvra S. ~hattac~a~ya

~ddition~l ~olu~es in Prepara~ion

Signal Processing for Intelligent Sensor Systems, David C. ~wa~so~

Compressed Video Over Networks, edited by ~ing-~in~ Sun and Amy

~iebman

Blind Equalization and Identi~cation, Zhi Ding and Ye (~eo~rey) Li

MARCEL

MARCEL DEKKER, INC. NEW YORK e BASEL

DEKKER

Sriram, ~undararajan

Embedded multiprocessors : scheduling and sync~ronization/

Sundararajan Sriram, Shuvra S. Bhattacharyya.

Includes bibliographical references and index.

ISBN 0-8247-9318-8 (alk. paper)

p. cm. - (Signal processing series ; 3)

1. Embedded computer ems. 2. M~tiprocessors. 3. Multimedia

systems. 4. Scheduling. I. ttacharyya, Shuvra S. TI. Title.

111. Signal processing (Marcel Deaer, Inc.) ; 3.

T~78~~.E42 S65 2000

004.l&dc21 00-0~2900

This book is printed on acid-free paper.

Marcel Dekker, Inc.

270 Madison Avenue, New York, W 10016

tel: 2 12-696-9000; fax: 2 12-685-4540

Marcel Dekker AG

~utgasse 4, Postfach 8 12, CH-400 1 Basel, Switzerland

tel: 41-61-261-8482; fax: 41-61-261-8896

The ~ublisher offers discounts on ths book when ordered in bulk quantities. For

more info~tion, write to Special Sa~es~rofessional Marketing at the

~eadqua~ers address above.

Neither this book nor any part my be reproduced or transmitted in any fom or by

any means, electronic or mechanical, including photocop~g, micro~l~ng, and

recording, or by any ~fo~tion storage and retrieval system, without permission

in writing from the publisher.

Current printing (last digit)

l0987654321

To my parent^, and Uma

Sundararajan Sriram

~~und~ati

Shuvra S. Bhattacharyya

This Page Intentionally Left Blank

Over the past 50 years, digital siglla~ rocessing has evolved as a major engi￾neering disc~p~~ne. The fields of signal processing have grown from the origin

of fast Fourier transforln and digital filter design to statistical spectral analysis

and array processing, and image, audio, and lnultiln~dia processing, and shaped

developments in high-performance VLSI signal processor design. Indeed, there

are few fields that enjoy so many applications-signal processing is every￾where in our lives.

When one uses a cellular phone, the voice is compressed, coded, and

modulated using signal processing techniques. As a cruise missile winds along

hillsides searching for the target, the signal processor is busy processing the

images taken along the way. When we are watching a movie in HDTV,

millions of audio and video data are being sent to our homes and received with

unbelievable fidelity. When scientists compare DNA samples, fast pattern

recognition techniques are being used. On and on, one can see the impact of

signal processing in almost every engineering and scientific discipline,

Because of the immense importan~e of signal processing and the fast￾growing demands of business and in dust^, this series on signal processing

serves to report up-to-date developments and advances in the field. The topics

of interest include but are not limited to the following:

Signal theory and analysis

Statistical signal processing

Speech and audio processing

Image and video processing

~~ltil~edia signlprocessing and technology

Signal processing for colnlnunications

Signal processing architectures and VLSI design

I hope this series will provide the interested audience with higll-~uality,

state-of-the-art signal processing literature through research monographs,

edited books, and rigorously written textbooks by experts in their fields.

K. J. Ray Liu

V

DSP 1

DSP 2

MCU

ASIC 4

o 5 10 (5 io l

Embedded systems are computers that are not first and foremost comput￾ers. They are pervasive, appearing in automobiles, telephones, pagers, consumer

electronics, toys, aircraft, trains, security systems, weapons systems, printers,

modems, copiers, thermostats, manufacturing systems, appliances, etc. A techni￾cally active person today probably interacts regularly with more embedded sys￾tems than conventional computers. This is a relatively recent phenomenon. Not

so long ago automobiles depended on finely tuned mechanical systems for the

timing of ignition and its synchronization with other actions. It was not so long

ago that modems were finely tuned analog circuits.

Embedded systems usually encapsulate domain expertise. Even small soft￾ware programs may be very sophisticated, requiring deep understanding of the

domain and of supporting technologies such as signal processing. Because of

this, such systems are often designed by engineers who are classically trained in

the domain, for example, in internal combustion engines or in communication

theory. They have little background in the theory of computation, parallel com￾puting, and concurrency theory. Yet they face one of the most difficult problems

addressed by these disciplines, that of coordinating multiple concurrent activities

in real tjme, often in a safety-critical environment. Moreover, they face these

problems in a context that is often extremely cost-sensitive, mandating optimal

designs, and time-critical, mandatin~ rapid designs.

Embedded software is unique in that parallelism is routine. Most modems

and cellular telephones, for example, incorporate multiple programmable proces￾sors. Moreover, embedded systems typically include custom digital and analog

hardware that must interact with the software, usually in real time. That hardware

operates in parallel with the processor that runs the software, and the software

must interact with it much as it would interact with another software process run￾ning in parallel. Thus, in having to deal with real-time issues and parallelism, the

designers of embedded software face on a daily basis problems that occur only in

esoteric research in the broader field of computer science.

uter scientists refer to use of physica~ly distinct computational

resources (processors) as “parallelism,” and to the logical property that multiple

activities occur at the same time as “concu~ency.” Paral~e~ism implies concur￾rency, but the reverse is not true. Almost all operating systems deal with concur￾rent , which is managed by multiplexing multiple processes or threads on a

processor. A few also deal with parallelism, for example by mapping

S onto physically distinct processors. Typical embedded systems exhibit

both concu~ency and parallelism, but their context is different from that of gen￾In embedded systems, concu~entasks are often statically defined, largely

the lifetime of the system. A cellular phone, for example, has

nct modes of operation (dialing, talking, standby, etc.), and in

each mode of operatio ll-defined set of tasks is concu~e~tly active (speech

encoding, etc.). The static structure of the concur￾r much more detailed analysis and optimization

in a more dynamic environment. is book is about such

ose opera tin^ systems in many ways.

analysis and optimization.

rdered transaction strategy, for example, leverages that relatively

static of embedded software to dramatically reduce the synchronization

overhead of communication between processors. It recognizes that embedded

software is intrinsically less predictable than hardware and more predictable than

eneral-pu~ose software. Indeed, minimizing synchronization overhead by

static info~ation about the application is the major theme of this

book.

In general-pu~ose computation, communication is relatively expensive.

Consider for example the interface between the audio hardw~e and the software

of a typical personal computer today. Because the transaction costs are extremely

h, data is extensively buffered, resu~ting in extremely long latencies. A path

from the microphone of a PC into the software and back out to the speaker typi￾cally has latencies of hundreds of milliseconds. This severely limits the utility of

the audio hardware of the computer. Embed ed systems cannot tolerate such

latencies.

major theme of this book is communication between components. The

iven in the book are firmly rooted in a manipulable and tractable for￾d yet are directly applied to hardware design. The closely related IPC

ssor communication) graph and synchronization graph models, intro￾hapters 7 and 9, capture the essential prope~ies of this com~unica￾e of graph-theoretic properties of IPC and sync~onization graphs,

optimi~ation problems are formulated and solved. For example, the notion of

resynchroni~ation, where explicit synchronization operations are minimi~ed

through manipulation of the sync~onization graph, proves to be an effective

optimi~ation tool.

In some ways, embedded software has more in common with hardware

than with traditional software. ardware is highly parallel. Conceptually9 hard￾ware is an assemblage of components that operate continuously or discretely in

time and interact via sync~onous or asynchronous communication, oftw ware is

an assemblage of components that trade off use"of a CPU, operating sequentially,

and communicating by leaving traces of their (past and completed) execution on

a stack or in memo^.

Hardware is temporal. In the extreme case, analog hardware operates in a

continuum, a computational medium that is totally beyond the reach of software,

Communication is not just synchronous; it is physical and fluid, oftw ware is

sequential and discrete. ~oncu~ency in software is about reconciling sequences,

Concu~ency in hardware is about reconciling signals, This book ~xamines paral￾lel software from the perspective of signals, and identifies joint hardware/soft￾ware designs that are ~articularly well-suited for embedded systems.

The prima^ abstraction mechanism in software is the ~rocedure (or the

method in object-oriented designs). Procedures are terminating computations.

The primary abstraction mechanism in hardware is a module that operat

allel with the other components. These modules represent non-termina

putations. These are very different abstraction mechanisms. Hardw

do not start, execute, complete, and return. They just are. In embedded systems9

software components often have the same property. They do not te~inate.

~onceptually, the distinction between hardware and software, from the

perspective of co~putation9 has only to do with the degree of concu~ency and

the role of time. An application with a large amount of concu~ency and a heavy

temporal content rnight as well be thought of as using the ~bstract~ons that have

been successful for hardware, regardless of how it is implemented. An applica￾tion that is sequential and ignores time rnight as well be thought of as using the

abstractions that have succeeded for software, regardless of how it is imple￾mented. The key problem becomes one of identifying the appropriate abstrac￾tions for representing the design. This book identifies abstractions that work well

for the joint design of embedded software and the hardware on which it runs.

The intellectual content in this book is high. While some of the methods it

describes are relatively simple, most are quite sophisticated. Yet examples are

given that concretely de strate how these concepts can be applied in practical

hardware architectures. over, there is very little overlap with other books on

parallel processing. The focus on application-specific processors and their use in

x FOREWORD

embedded systems leads to a rather different set of techniques. I believe that this

book defines a new discipline. It gives a systematic approach to problems that

engineers previously have been able to tackle only in an ad hoc manner.

Edwar~ A. Lee

Professor

~e~artment o~~lectrical Engineering

University of Cal~ornia at Berkeley

Berkeley, Cal~ornia

and Computer Sciences

Software implementation of c0mpute"intensive multimedia applications

such as video conferencing systems, set-top boxes, and wireless mobile terminals

and base stations is extremely attractive due to the flexibility, extensibility, and

potential portability of programmable implementations. However, the data rates

involved in many of these applications tend to be very high, resulting in relatively

few processor cycles available per input sample for a reasonable processor clock

rate. Employing multiple processors is usually the only means for achieving the

requisite compute cycles without moving to a dedicated ASIC solution. With the

levels of integration possible today, one can easily place four to six digital signal

processors on a single die; such an integrated multiprocessor strategy is a promis￾ing approach for tackling the complexities associated with future systems-on-a￾chip. However, it remains a significant challenge to develop software solutions

that can effectively exploit such multiprocessor implementation platforms.

Due to the great complexity of implementing multiprocessor software, and

the severe performance constraints of multimedia applications, the develop~nent

of automatic tools for mapping high level specifications of multimedia applica￾tions into efficient multiprocessor realizations has been an active research area

for the past several years. ~apping an application onto a multiprocessor system

involves three main operations: assigning tasks to processors, ordering tasks on

each processor, and determining the time at which each task begins execution.

These operations are collectively referred to as sc~e~~Zi~g the application on the

given architecture. A key aspect of the multiprocessor scheduling problem for

multimedia system implementation that differs from classical scheduling con￾texts is the central role of interprocessor communication - the efficient manage￾ment of data transfer between communicating tasks that are assigned to different

processors. Since the overall costs of interprocessor communication can have a

dramatic impact on execution speed and power consumption, effective handling

of interprocessor communicatio~ is crucial to the development of cost-effective

multiprocessor implementations.

This books reviews important research in three key areas related to multi￾processor implementation of multimedia systems, and this book also exposes

important synergies between efforts related to these areas. Our areas of focus are

the incorporation of interprocessor communication costs into multiprocessor

scheduling decisions; a modeling methodology, called the "synchronization

.. ~REFA~E

graph,” for multiprocessor system performance analysis; and the application of

the synchronization graph model to the development of hardware and software

timizations that can significantly reduce the inte~rocessor communication

erhead of a given schedule.

ore specifically, this book reviews, in a unified manner^ several impor￾iprocessor scheduling strategies that effectively inco~orate the consid￾eration of inte~rocessor communication costs, and highlights the variety of

techniques employed in these multiprocessor scheduling strategies to take inter￾processor communication into account. The book also reviews a body of research

performed by the authors on modeling implementations of multiprocessor sched￾ules, and on the use of these odel ling techni~ues to optimize interprocessor

communication costs. A unified framework is then presented for applying arbi￾trary scheduling strategies in conjunction with the application of alternative opti￾mization algorithms that address specific subproblems associated with

implementing a given schedule. We provide several examples of practical appli￾cations that demonstrate the relevance of the techniques desc~bed in this book.

are grateful to the Signal Processing Series Editor Professor K. 3. Ray

Liu (University of land, College Park) for his encouragement of this project,

and to Executive isition Editor B. J. Clark (Marcel Dekker, Inc.) for his

coordination of the effort. It was a privilege for both of us to be students of Pro￾fessor Edward A. Lee (University of California at erkeley). Edward provided a

truly inspiring research environmen~ during our d toral studies, and gave valu￾able feedback while we were developing many of the concepts that underlie

n this book. We also acknowledge helpful proofreading assistance

andrachoodan, Mukul ~handelia, and Vida Kianzad

~aryland at College Park); and enlightening discussions with

n and Dick Stevens (U. S. Naval Research Laboratory), and Praveen

(Angeles Design Systems). Financial support (for S. S. Bhatta￾development of this book was provided by the National Science

§un~ururujun §rira~

§hu~ru S. ~h~ttucha~yu