2nd Edition
Embedded Multiprocessors Scheduling and Synchronization, Second Edition
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
