A periodic scheduling heuristic for mapping iterative task graphs onto distributed memory multiprocessors
Abstract
This thesis investigates the problem of statically assigning the tasks of applications represented by repetitive task graphs (such as sonar or radar signal processing) to the processors of a distributed memory multiprocessor system with the objective of maximizing graph instance throughput. The repetitive nature of these task graphs allows for pipelining and the overlapping of successive graph instances, suggesting a departure from classical directed acyclic graph scheduling techniques. To investigate such a claim, a version of the Mapping Heuristic (MH) [ELR 90] is extended for use with iterative applications. Then a new heuristic, Periodic Scheduling (PS), is developed to capitalize on the repetitive nature of these task graphs by overlapping successive graph instances. The PS heuristic assigns tasks to processors in such a way so as to minimize the maximal utilization of the processors and the communications links between them. This maximal utilization figure dictates the interval between successive instances of the task graph. We conduct experiments in which the graph instance throughput of PS is compared to that of MH across a broad range of processor topologies, utilizing several communications/computation ratios. It is shown that, compared to MH, the PS heuristic improves the throughput perfonnance between two and 50 percent Particularly noteworthy improvement is noted on systems with high average inter-node communications costs.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Grain size management in repetitive task graphs for multiprocessor computer scheduling
Negelspach, Greg L. (Monterey, California. Naval Postgraduate School, 1994-09);Optimal scheduling of parallel programs onto multiprocessor computers is an exponentially hard problem. Because of this, most scheduling algorithms in use today rely on heuristics to determine the best balance of computation ... -
A tool for efficient execution and development of repetitive task graphs on a distributed memory multiprocessor
Koman, Charles Brian (Monterey, California. Naval Postgraduate School, 1995-09);The major problem addressed by this research is the development of one or more scheduling heuristics suitable for applications which involve repetitive execution of task graphs on a distributed memory multiprocessor, and ... -
Allocation of periodic tasks with precedences on transputer-based systems
Falcao, Marco A. G. (Monterey, California. Naval Postgraduate School, 1992-09);Task allocation is an important component of the process of mapping modules of application programs to multicomputers. A scheme for static allocation of periodic tasks with precedences to processors is developed considering ...