Heuristic algorithms for distributed processor scheduling with limited memory

This thesis studies a heuristic approach to scheduling •on a 2-processor distributed system when one processor has a limited memory. A program is assumed to consist of a set of sequentially executing modules and is represented by Stone's graph model. It is desired to assign these modules to the processors so as to minimize interprocessor communication while taking advantage of specific capabilities of the two processors. This optimization problem is NP-complete. It is shown that the corresponding 'absolute approximation' problem is as hard. For the classes of constant degree and constant connectivity graphs statistics are presented to support the conjecture of Rao, Stone and Hu that use of the 'inclusive-cuts graph' can appreciably simplify this scheduling problem. Asymptotic upper and lower bounds on the expected cost of the optimum assignment are derived for the class of constant degree graphs. These results motivate the development and assist the evaluation of two polynomial-time heuristic algorithms for 2-processor scheduling with limited memory. For constant degree graphs it is shown that the heuristics can be useful scheduling tools. It is also shown that use of the inclusive-cuts graph can lead to an improvement in performance, but at the expense of additional scheduling overhead. An ancillary result proved is a relationship between scheduling with limited memory and scheduling when one processor is multiprogrammed and has a variable load factor. Some implications of this relationship are discussed.

Name thesis:degree_name

Master of Science

Level thesis:degree_level

Masters

Discipline thesis:degree_discipline

Engineering

Grantor

Rice University

Year dc:date.issued

1979

Author dc:creator

• Gonsalves, Timothy A.

Advisor dc:contributor.advisor

• Rao, G. S.

Statement dc:rights

• Copyright is held by the author, unless otherwise indicated. Permission to reuse, publish, or reproduce the work beyond the bounds of fair use or other exemptions to copyright law must be obtained from the copyright holder.

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1911/104536

OAI identifier oai:identifier

oai:repository.rice.edu:1911/104536