Static task scheduling and grain packing in parallel processing systems Public Deposited

http://ir.library.oregonstate.edu/concern/graduate_thesis_or_dissertations/6t053k38h

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • We extend previous results for optimally scheduling concurrent program modules, called tasks, on a fixed, finite number of parallel processors in two fundamental ways: (1) we introduce a new heuristic which considers the time delay imposed by message transmission among concurrently running tasks; and (2) we introduce a second heuristic which maximizes program execution speed by duplicating tasks. Simulation results are given which suggest an order of magnitude improvement in program execution speed over previous scheduling heuristics. The first solution, called ISH, (insertion scheduling heuristic) provides only a small improvement over current solutions but has a smaller time complexity than DSH, 0(N²). DSH (duplication scheduling heuristic), is an 0(N⁴) heuristic that (1) gives up to an order of magnitude improvement in performance, (2) solves the max-min problem of parallel processor scheduling by duplicating selected scheduled tasks on some PEs, and (3) gives monotonically growing improvements as the number of PEs is increased. The max-min problem is caused by the trade-off between maximum parallelism versus minimum communication delay. The DSH is also applied in "Grain Packing", which is a new way to define the grain size for a user program on a specific parallel processing system. Instead of defining the grain size before scheduling, grain packing uses the fine grain scheduling to construct larger grains. In this way all available parallelism is considered as well as the communication delay.
Resource Type
Date Available
Date Copyright
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Academic Affiliation
Non-Academic Affiliation
Subject
Rights Statement
Peer Reviewed
Language
Digitization Specifications
  • File scanned at 300 ppi (Monochrome) using ScandAll PRO 1.8.1 on a Fi-6670 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-05-31T20:16:24Z (GMT) No. of bitstreams: 1 KruatrachueBoontee1988.pdf: 971294 bytes, checksum: f60b31fd66b74c4a1f935e41e4a11b4b (MD5)
  • description.provenance : Submitted by Katy Davis (kdscannerosu@gmail.com) on 2013-05-31T19:03:36Z No. of bitstreams: 1 KruatrachueBoontee1988.pdf: 971294 bytes, checksum: f60b31fd66b74c4a1f935e41e4a11b4b (MD5)
  • description.provenance : Made available in DSpace on 2013-07-15T18:29:36Z (GMT). No. of bitstreams: 1 KruatrachueBoontee1988.pdf: 971294 bytes, checksum: f60b31fd66b74c4a1f935e41e4a11b4b (MD5) Previous issue date: 1987-06-10
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-07-15T18:29:36Z (GMT) No. of bitstreams: 1 KruatrachueBoontee1988.pdf: 971294 bytes, checksum: f60b31fd66b74c4a1f935e41e4a11b4b (MD5)

Relationships

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

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items