Grain size management in repetitive task graphs for multiprocessor computer scheduling
Negelspach, Greg L.
MetadataShow full item record
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.
Approved for public release, distribution unlimited
Showing items related by title, author, creator and subject.
Quigg, John Howard (Monterey, California. Naval Postgraduate School, 1993-09);Directed Acyclic Graph Scheduling is a technique used to implement the real-time execution of Digital Signal Processing applications on multiple- processor data-flow machines that support variable-grained parallelism. The ...
Usefulness of compile-time restructuring of large grain data flow programs in throughput-critical applications Cross, David M. (Monterey, California. Naval Postgraduate School, 1993-09);In this thesis, Large Grain Data Flow (LGDF) representation of parallelism is applied to throughout-critical applications that process periodically arriving data. The applications are represented by directed acyclic graphs ...
A periodic scheduling heuristic for mapping iterative task graphs onto distributed memory multiprocessors Kasinger, Charles D. (Monterey, California. Naval Postgraduate School, 1994-09);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 ...