Program allocation for hypercube based dataflow systems Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/rx913t625

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • The dataflow model of computation differs from the traditional control-flow model of computation in that it does not utilize a program counter to sequence instructions in a program. Instead, the execution of instructions is based solely on the availability of their operands. Thus, an instruction is executed in a dataflow computer when all of its operands are available. This asynchronous nature of the dataflow model of computation allows the exploitation of fine-grain parallelism inherent in programs. Although the dataflow model of computation exploits parallelism, the problem of optimally allocating a program to processors belongs to the class of NP-complete problems. Therefore, one of the major issues facing designers of dataflow multiprocessors is the proper allocation of programs to processors. The problem of program allocation lies in maximizing parallelism while minimizing interprocessor communication costs. The culmination of research in the area of program allocation has produced the proposed method called the Balanced Layered Allocation Scheme that utilizes heuristic rules to strike a balance between computation time and communication costs in dataflow multiprocessors. Specifically, the proposed allocation scheme utilizes Critical Path and Longest Directed Path heuristics when allocating instructions to processors. Simulation studies indicate that the proposed scheme is effective in reducing the overall execution time of a program by considering the effects of communication costs on computation times.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using Capture Perfect 3.0 on a Canon DR-9050C in PDF format. CVista PdfCompressor 4.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-01-06T23:48:50Z (GMT) No. of bitstreams: 1 FreytagVincentR1993.pdf: 3700672 bytes, checksum: 90372d54349631212a54825eef746dbd (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-02-12T16:33:01Z (GMT) No. of bitstreams: 1 FreytagVincentR1993.pdf: 3700672 bytes, checksum: 90372d54349631212a54825eef746dbd (MD5)
  • description.provenance : Submitted by Kirsten Clark (kcscannerosu@gmail.com) on 2013-01-03T22:01:04Z No. of bitstreams: 1 FreytagVincentR1993.pdf: 3700672 bytes, checksum: 90372d54349631212a54825eef746dbd (MD5)
  • description.provenance : Made available in DSpace on 2013-02-12T16:33:01Z (GMT). No. of bitstreams: 1 FreytagVincentR1993.pdf: 3700672 bytes, checksum: 90372d54349631212a54825eef746dbd (MD5) Previous issue date: 1993-03-18

Relationships

In Administrative Set:
Last modified: 08/20/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items