Declustering: a new multiprocessor scheduling technique
Authors:
- 1 June 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 4 (6) , 625-637
Abstract
The authors present a new compile-time scheduling heuristic called declustering, which schedules acyclic precedence graphs that fit the synchronous data flow (SDF) model onto multiprocessor architectures. This technique accounts for interprocessor communication (IPC) overheads and considers interconnection constraints in the architecture so that shared resource contention can be avoided. The algorithm initially invokes a new clustering method that uses graph-analysis techniques to isolate parallelism instances. When constructing an initial set of clusters, this procedure explicitly addresses the tradeoff between exploiting parallelism and incurring communication cost. By hierarchically combining these clusters and then systematically decomposing this hierarchy, the declustering method exposes parallelism instances in order of importance and attains a cluster granularity that fits the characteristics of the architecture. It is shown that declustering retains the clustering advantage of avoiding IPC, yet overcomes the inflexibility associated with traditional clustering approaches.< >Keywords
This publication has 8 references indexed in Scilit:
- Gabriel: a design environment for DSPIEEE Micro, 1990
- Clustering task graphs for message passing architectures1990
- Towards an Architecture-Independent Analysis of Parallel AlgorithmsSIAM Journal on Computing, 1990
- Static Scheduling of Synchronous Data Flow Programs for Digital Signal ProcessingIEEE Transactions on Computers, 1987
- Heuristic Models of Task Assignment Scheduling in Distributed SystemsComputer, 1982
- Task Allocation in Distributed Data ProcessingComputer, 1980
- Multiprocessor Scheduling with the Aid of Network Flow AlgorithmsIEEE Transactions on Software Engineering, 1977
- A comparison of list schedules for parallel processing systemsCommunications of the ACM, 1974