Accession Number : ADA288575

Title :   Grain Size Management in Repetitive Task Graphas for Multiprocessor Computer Scheduling.

Descriptive Note : Master's thesis,

Corporate Author : NAVAL POSTGRADUATE SCHOOL MONTEREY CA

Personal Author(s) : Negelspach, Greg L.

PDF Url : ADA288575

Report Date : SEP 1994

Pagination or Media Count : 56

Abstract : 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.

Descriptors :   ALGORITHMS, REQUIREMENTS, SIMULATION, OPTIMIZATION, COMPUTATIONS, MANAGEMENT, MODELS, COMPUTERS, MODIFICATION, GRAPHS, THESES, GRAIN SIZE, TIME, COSTS, SCHEDULING, BALANCE, THROUGHPUT, HEURISTIC METHODS, MULTIPROCESSORS, COMMUNICATION AND RADIO SYSTEMS, PARALLEL ORIENTATION.

Subject Categories : Military Forces and Organizations

Distribution Statement : APPROVED FOR PUBLIC RELEASE