Grain size management in repetitive task graphs for multiprocessor computer scheduling

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 and communication costs. However, because of the NP-hard nature of the problem, these heuristics have become very complex. We are concerned with a specific instance of the problem, throughput scheduling, which aims to optimize the completion rate of repetitive programs, expressed as task graphs, for which the computational and communication needs of the tasks are known in advance. We propose a simpler approach for finding better schedules, which involves testing different grain size modified versions of the task graph to find the one that results in the highest throughput for the given scheduling algorithm. Our heuristic works by alternately fusing or fissioning selected tasks of the graph then evaluating the modified task graph by measuring the expected throughput of its resultant schedule. Because of the generality of this approach, it can be applied to any scheduling algorithm that does not already include grain size modification. We test the new heuristic using a simulation of the Navy's new standard digital signal processor, the AN/UYS-2, and using various task graphs and scheduling algorithms. We show that this practical approach to scheduling can increase throughput of the Largest Process Time first algorithm by at least 16 percent for our model computer configured with four, eight, or sixteen processors.

Grantor dc:publisher

Monterey, California. Naval Postgraduate School

Year dc:date.issued

1994

Author dc:creator

• Negelspach, Greg L.

Advisor dc:contributor.advisor

• Zaky, Amr

Statement dc: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.

Language dc:language.iso

en_US

Handle dc:identifier.uri

https://hdl.handle.net/10945/43005

OAI identifier oai:identifier

oai:calhoun.nps.edu:10945/43005