Heuristic algorithms for distributed processor scheduling with limited memory
Gonsalves, Timothy A.
Rao, G. S.
Master of Science
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.