Analysis of macro-dataflow dynamic scheduling on nonuniform memory access architectures
Author:
- M. Al-MouhamedMAM. Al-Mouhamed
- 1 January 1993
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 4 (8) , 875-888
Abstract
The author studies dynamic scheduling of computational tasks with communication costsusing nonuniform memory access architecture. The computing model assumes that datatransfer can be partitioned into parallel and sequential parts with respect to the taskexecution. A scheduling heuristic, called least-communication (LC), together with atwo-level scheduler is proposed in an attempt to minimize the finish time. The LC selectsthe task that removes the largest amount of remaining data transfer, if no such tasks areavailable the task that has been ready to run at the earliest is selected first. The timecomplexity of LC is O(n/sub 2/). Testing the finish time of LC and first-come first-servedscheduling (FCFS) shows that LC is useful for tasks having moderate granularity andwhose computation and communication requirements vary widely for different data sets.Keywords
This publication has 19 references indexed in Scilit:
- Architectures for Statically Scheduled Dataflow1991
- Lower bound on the number of processors and time for scheduling precedence graphs with communication costsIEEE Transactions on Software Engineering, 1990
- Analysis and evaluation of heuristic methods for static task schedulingJournal of Parallel and Distributed Computing, 1990
- Multiprocessor system for realtime robotics applicationsMicroprocessors and Microsystems, 1990
- Scheduling parallel program tasks onto arbitrary target machinesJournal of Parallel and Distributed Computing, 1990
- Automatic determination of grain size for efficient parallel processingCommunications of the ACM, 1989
- Scheduling Precedence Graphs in Systems with Interprocessor Communication TimesSIAM Journal on Computing, 1989
- Practical Multiprocessor Scheduling Algorithms for Efficient Parallel ProcessingIEEE Transactions on Computers, 1984
- Bounds on the Number of Processors and Time for Multiprocessor Optimal SchedulesIEEE Transactions on Computers, 1973
- Optimal Scheduling Strategies in a Multiprocessor SystemIEEE Transactions on Computers, 1972