• Focuses on multiprocessor implementations of signal processing applications specified as dataflow graphs
• Describes unique techniques for optimizing communication and synchronization
• Integrates arbitrary scheduling strategies with alternative optimization algorithms to address specific subproblems associated with implementing a given schedule
• Provides several examples of practical applications that demonstrate the relevance of the techniques described

Techniques for Optimizing Multiprocessor Implementations of Signal Processing Applications

An indispensable component of the information age, signal processing is embedded in a variety of consumer devices, including cell phones and digital television, as well as in communication infrastructure, such as media servers and cellular base stations. Multiple programmable processors, along with custom hardware running in parallel, are needed to achieve the computation throughput required of such applications.

Reviews important research in key areas related to the multiprocessor implementation of multimedia systems
Embedded Multiprocessors: Scheduling and Synchronization, Second Edition presents architectures and design methodologies for parallel systems in embedded digital signal processing (DSP) applications. It discusses application modeling techniques for multimedia systems, the incorporation of interprocessor communication costs into multiprocessor scheduling decisions, and a modeling methodology (the synchronization graph) for multiprocessor system performance analysis. The book also applies the synchronization graph model to develop hardware and software optimizations that can significantly reduce the interprocessor communication overhead of a given schedule.

Chronicles recent activity dealing with single-chip multiprocessors and dataflow models
This edition updates the background material on existing embedded multiprocessors, including single-chip multiprocessors. It also summarizes the new research on dataflow models for signal processing that has been carried out since the publication of the first edition.

Harness the power of multiprocessors
This book explores the optimization of interprocessor communication and synchronization in embedded multiprocessor systems. It shows you how to design multiprocessor computer systems that are streamlined for multimedia applications.

INTRODUCTION

Multiprocessor DSP systems

Application-specific multiprocessors

Exploitation of parallelism

Dataflow modeling for DSP design

Utility of dataflow for DSP

Overview

APPLICATION-SPECIFIC MULTIPROCESSORS

Parallel architecture classifications

Exploiting instruction-level parallelism

Dataflow DSP architectures

Systolic and wavefront arrays

Multiprocessor DSP architectures

Single-chip multiprocessors

Reconfigurable computing

Architectures that exploit predictable IPC

Summary

BACKGROUND TERMINOLOGY AND NOTATION

Graph data structures

Dataflow graphs

Computation graphs

Petri Nets

Synchronous dataflow

Analytical properties of SDF graphs

Converting a general SDF graph into a homogeneous SDF graph

Acyclic precedence expansion graph

Application graph

Synchronous languages

HSDFG concepts and notations

Complexity of algorithms

Shortest and longest paths in graphs

Solving difference constraints using shortest paths

Maximum cycle mean

Summary

DSP-ORIENTED DATAFLOW MODELS OF COMPUTATION

Scalable synchronous dataflow

Cyclostatic dataflow

Multidimensional synchronous dataflow

Parameterized dataflow

Reactive process networks

Integrating dataflow and state machine models

Controlled dataflow actors

Summary

MULTIPROCESSOR SCHEDULING MODELS

Task-level parallelism and data parallelism

Static versus dynamic scheduling strategies

Fully static schedules

Self-timed schedules

Dynamic schedules

Quasistatic schedules

Schedule notation

Unfolding HSDF graphs

Execution time estimates and static schedules

Summary

IPC-CONSCIOUS SCHEDULING ALGORITHMS

Problem description

Stone’s assignment algorithm

List scheduling algorithms

Clustering algorithms

Integrated scheduling algorithms

Pipelined scheduling

Summary

THE ORDERED-TRANSACTIONS STRATEGY

The ordered-transactions strategy

Shared bus architecture

Interprocessor communication mechanisms

Using the ordered-transactions approach

Design of an ordered memory access multiprocessor

Design details of a prototype

Hardware and software implementation

Ordered I/O and parameter control

Application examples

Summary

ANALYSIS OF THE ORDERED-TRANSACTIONS STRATEGY

Interprocessor communication graph (G_ipc)

Execution time estimates

Ordering constraints viewed as added edges

Periodicity

Optimal order

Effects of changes in execution times

Effects of interprocessor communication costs

Summary

EXTENDING THE OMA ARCHITECTURE

Scheduling BDF graphs

Parallel implementation on shared memory machines

Data-dependent iteration

Summary

SYNCHRONIZATION IN SELF-TIMED SYSTEMS

The barrier MIMD technique

Redundant synchronization removal in noniterative dataflow

Analysis of self-timed execution

Strongly connected components and buffer size bounds

Synchronization model

A synchronization cost metric

Removing redundant synchronizations

Making the synchronization graph strongly connected

Insertion of delays

Summary

RESYNCHRONIZATION

Definition of resynchronization

Properties of resynchronization

Relationship to set covering

Intractability of resynchronization

Heuristic solutions

Chainable synchronization graphs

Resynchronization of constraint graphs for relative scheduling

Summary

LATENCY-CONSTRAINED RESYNCHRONIZATION

Elimination of synchronization edges

Latency-constrained resynchronization (LCR)

Intractability of LCR

Two-processor systems

A heuristic for general synchronization graphs

Summary

INTEGRATED SYNCHRONIZATION OPTIMIZATION

Computing buffer sizes

A framework for self-timed implementation

Summary

FUTURE RESEARCH DIRECTIONS

BIBLIOGRAPHY

INDEX

"While some of the methods [this book] describes are relatively simple, most are quite sophisticated. Yet examples are given that concretely demonstrate how these concepts can be applied in practical hardware architectures. Moreover, there is very little overlap with other books on parallel processing. The focus on application-specific processors and their use in 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."
—Edward A. Lee, University of California, Berkeley, USA