Static-task scheduling incorporating precedence constraints and deadlines in a heterogeneous-computing environment / Michael D. Niedert.
Niedert, Michael D.
MetadataShow full item record
Distributed systems have grown in popularity due to the rapid increase in networking of personal computers. A mixture of computers consisting of different architectures can be more powerful, reliable, and scalable than a single supercomputer. The problem of optimally scheduling jobs on a cluster of heterogeneous machines to minimize the time at which the last machine finishes is NP-complete. Nonetheless, the choice of a heuristic algorithm greatly affects the speed of solution. This work evaluates a greedy algorithm, an A* algorithm, and a simulated annealing algorithm applied to the heterogeneous scheduling problem with deadline and dependency constraints. Tradeoffs of speed and schedule quality were noted between the algorithms. The greedy algorithm produced results quicker than the A* and simulated annealing algorithms, but with a lower schedule quality. Because of these offsetting performance criteria, an analysis was conducted to determine which algorithms should be used for which input cases.
Showing items related by title, author, creator and subject.
Armstrong, Robert Kyle (Monterey, California. Naval Postgraduate School, 1997-09);This thesis investigates, using in-line simulation, the effect of non-deterministic runtime distributions on the performance of SmartNet's schedule execution using the Opportunistic Load Balancing (OLB) Algorithm, the ...
Richard Freund; Taylor Kidd; Lantz Moore; Debbie Hensgen (1996);SmartNet is a scheduling framework for heterogeneous systems. Preliminary conservative simulation results for one of the optimization criteria, show a 1.21 improvement over Load Balancing and a 25.9 improvement over Limited ...
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 ...