Show simple item record

dc.contributor.authorGonsalves, Timothy
dc.creatorGonsalves, Timothy
dc.date.accessioned 2007-10-31T00:44:29Z
dc.date.available 2007-10-31T00:44:29Z
dc.date.issued 1978-06-20
dc.date.submitted 2003-10-22
dc.identifier.urihttps://hdl.handle.net/1911/19896
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
processors
scheduling
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
dc.date.modified 2003-10-22
dc.subject.keyworddistributed systems
processors
scheduling
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

Thumbnail

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