2nd Edition

Embedded Multiprocessors Scheduling and Synchronization, Second Edition

    380 Pages 130 B/W Illustrations
    by CRC Press

    384 Pages 130 B/W Illustrations
    by CRC Press

    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 (Gipc)

    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

    Biography

    Sundararajan Sriram, Shuvra S. Bhattacharyya

    "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