Results on Distributed Processor Scheduling with Limited Memory
distributed systems; processors; scheduling
This paper is a study of 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. This motivates the development of two polynomial-time heuristic algorithms for the problem. For the class of constant degree graphs it is shown that the heuristics can be useful scheduling tools. 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. finally asymptotic upper and lower bounds on the expected cost of the optimum assignment are derived for the class of constant degree graphs.
MetadataShow full item record
- ECE Publications