Graduate Thesis Or Dissertation
 

A comparison of task scheduling algorithms on multicomputers

Public Deposited

Contenu téléchargeable

Télécharger le fichier PDF
https://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/ww72bf178

Descriptions

Attribute NameValues
Creator
Abstract
  • 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
Déclaration de droits
Publisher
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

Des relations

Parents:

This work has no parents.

Dans Collection:

Articles

La vignette Titre Date de téléchargement Visibilité actes
file details Shin_Chae_Y_1994.pdf 2017-08-08 Public Télécharger