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.
Table of Contents:
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
