Show simple item record

dc.contributor.authorGonsalves, Timothy
dc.creatorGonsalves, Timothy 2007-10-31T00:44:29Z 2007-10-31T00:44:29Z 1978-06-20 2003-10-22
dc.description Tech Report
dc.description.abstract 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.
dc.language.iso eng
dc.subjectdistributed systems
dc.title Results on Distributed Processor Scheduling with Limited Memory
dc.type Report
dc.citation.bibtexName techreport
dc.citation.journalTitle Rice University ECE Technical Report 2003-10-22
dc.subject.keyworddistributed systems
dc.citation.issueNumber 7805
dc.type.dcmi Text
dc.type.dcmi Text
dc.identifier.citation T. Gonsalves, "Results on Distributed Processor Scheduling with Limited Memory," Rice University ECE Technical Report, no. 7805, 1978.

Files in this item


This item appears in the following Collection(s)

  • ECE Publications [1302]
    Publications by Rice University Electrical and Computer Engineering faculty and graduate students

Show simple item record