Task partitioning and scheduling on arbitrary parallel processing systems Public Deposited

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

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • Parallel programming is the major stumbling block preventing the parallel processing industry from quickly satisfying the demand for parallel computer software. This research is aimed at solving some of the problems of software development for parallel computers. ELGDF is a graphical language for designing parallel programs. The goal of ELGDF is two-fold: 1) to provide a program design notation and computer-aided software engineering tool, and 2) to provide a software description notation for use by automated schedulers and performance analyzers. ELGDF is implemented as a graphical editor called Parallax. We extend previous results for optimally scheduling parallel program tasks on a finite number of parallel processors. We introduce a new scheduling heuristic (MH) that schedules program modules represented as nodes in a precedence task graph with communication onto arbitrary machine topology taking contention into consideration. We presents results for scheduling simulated task graphs on ring, star, mesh, hypercube, and fully connected networks using MH. We also present Task Grapher, a tool for studying optimal parallel program task scheduling on arbitrarily interconnected parallel processors. Given a parallel program represented as a precedence-constrained task graph, and an interconnect topology of a target machine, Task Grapher produces the following displays: 1) Gantt Chart Schedule, 2) Speed-up Line Graph, 3) Critical Path In Task Graph, 4) Processor Utilization Chart, 5) Processor Efficiency Chart, 6) Dynamic Activity Display. Task Grapher currently incorporates seven scheduling heuristics. Finally, we introduce a new loop unrolling method for scheduling nested loops onto arbitrary target machines. We use local neighborhood search and simulated annealing methods to find: 1) the best unrolling vector, and 2) a Gantt chart that indicates the allocation and the order of the tasks in the post-unrolled loop on the available processing elements.
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 ScandAll PRO 1.8.1 on a Fi-6770A in PDF format. CVista PdfCompressor 5.0 was used for pdf compression and textual OCR.
Replaces
Additional Information
  • description.provenance : Submitted by Kaylee Patterson (kdpscanner@gmail.com) on 2013-04-22T19:52:58Z No. of bitstreams: 1 El-RewiniHesham1990.pdf: 2196170 bytes, checksum: 5a05f3cea92571a08a890bbd8455c712 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-04-25T16:10:07Z (GMT) No. of bitstreams: 1 El-RewiniHesham1990.pdf: 2196170 bytes, checksum: 5a05f3cea92571a08a890bbd8455c712 (MD5)
  • description.provenance : Approved for entry into archive by Patricia Black(patricia.black@oregonstate.edu) on 2013-04-30T15:49:28Z (GMT) No. of bitstreams: 1 El-RewiniHesham1990.pdf: 2196170 bytes, checksum: 5a05f3cea92571a08a890bbd8455c712 (MD5)
  • description.provenance : Made available in DSpace on 2013-04-30T15:49:28Z (GMT). No. of bitstreams: 1 El-RewiniHesham1990.pdf: 2196170 bytes, checksum: 5a05f3cea92571a08a890bbd8455c712 (MD5) Previous issue date: 1989-11-21

Relationships

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

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items