Embedded Multiprocessors: Scheduling and Synchronization (Hardcover, 2)

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