A comparison of task scheduling algorithms on multicomputers Public Deposited

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

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • For many years, the von Neumann bottleneck has imposed speed limits on the execution of a program. Because of their sequential nature, von Neumann computers can only execute a single instruction at a time. Instructions that are side-effect free and can be executed in parallel must wait. In an effort to overcome this bottleneck, multicomputers have been developed and implemented. These multicomputers are a new class of computers based on multiple processors. With multiple processors available, instructions can be processed in parallel. However, now interprocessor communication (IPC) delays must be taken into account. A program that is run on several processors may take longer to execute than if it were run on a single processor. The focus of the speed limits has now changed. The new focus now hinges on the efficient partitioning of a program and allocation of those partitions to processors. Several algorithms have been developed to solve the problem of partitioning and scheduling. Three algorithms were studied under uniform conditions to determine the efficiencies of each. They were Internalization, Balanced Layered Allocation Scheme (BLAS) and Dynamic Level Scheduling (DLS). Simulation studies indicate that BLAS performs the best overall. These algorithms based their communications costs on a simplified IPC cost model. A more realistic message grouping IPC model was developed to test the accuracy of the algorithms which are based on the simplified model. These simulation studies indicated that the simplified model was a fairly accurate gauge of a more realistic system.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Language
Digitization Specifications
  • PDF derivative scanned at 300 ppi (256 B&W), using Capture Perfect 3.0, on a Canon DR-9080C. CVista PdfCompressor 3.1 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Made available in DSpace on 2008-09-16T13:24:07Z (GMT). No. of bitstreams: 1 Shin_Chae_Y_1994.pdf: 297295 bytes, checksum: 90bb3a23196e2ec6f680cb6d68ba08d8 (MD5)
  • description.provenance : Submitted by Anna Opoien (aoscanner@gmail.com) on 2008-09-11T18:20:06Z No. of bitstreams: 1 Shin_Chae_Y_1994.pdf: 297295 bytes, checksum: 90bb3a23196e2ec6f680cb6d68ba08d8 (MD5)
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2008-09-16T13:24:07Z (GMT) No. of bitstreams: 1 Shin_Chae_Y_1994.pdf: 297295 bytes, checksum: 90bb3a23196e2ec6f680cb6d68ba08d8 (MD5)
  • description.provenance : Approved for entry into archive by Linda Kathman(linda.kathman@oregonstate.edu) on 2008-09-16T13:22:18Z (GMT) No. of bitstreams: 1 Shin_Chae_Y_1994.pdf: 297295 bytes, checksum: 90bb3a23196e2ec6f680cb6d68ba08d8 (MD5)

Relationships

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

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items