This Is AuburnElectronic Theses and Dissertations

Show simple item record

Algorithms for Task Scheduling in Heterogeneous Computing Environments


Metadata FieldValueLanguage
dc.contributor.advisorBaskiyar, Sanjeev
dc.contributor.advisorCarlisle, Homeren_US
dc.contributor.advisorWang, Yuen_US
dc.contributor.authorSai, Rangaen_US
dc.date.accessioned2008-09-09T21:20:45Z
dc.date.available2008-09-09T21:20:45Z
dc.date.issued2006-12-15en_US
dc.identifier.urihttp://hdl.handle.net/10415/631
dc.description.abstractCurrent heterogeneous meta-computing systems, such as computational clusters and grids offer a low cost alternative to supercomputers. In addition they are highly scalable and flexible. They consist of a host of diverse computational devices which collaborate via a high speed network and may execute high-performance applications. Many high-performance applications are an aggregate of modules. Efficient scheduling of such applications on meta-computing systems is critical to meeting deadlines. In this dissertation, we introduce three new algorithms, the Heterogeneous Critical Node First (HCNF) algorithm, the Heterogeneous Largest Task First (HLTF) algorithm and the Earliest Finish Time with Dispatch Time (EFT-DT) algorithm. HCNF is used to schedule parallel applications of forms represented by directed acyclic graphs onto networks of workstations to minimize their finish times. We compared the performance of HCNF with those of the Heterogeneous Earliest Finish Time (HEFT) and Scalable Task Duplication based Scheduling (STDS) algorithms. In terms of Schedule Length Ratio (SLR) and speedup, HCNF outperformed HEFT on average by 13% and 18% respectively. HCNF outperformed STDS in terms of SLR and speedup on an average by 8% and 12% respectively. The HLTF algorithm is used to schedule a set of independent tasks onto a network of heterogeneous processors to minimize finish time. We compared the performance of HLTF with that of the Sufferage algorithm. In terms of makespan, HLTF outperformed Sufferage on average by 4.5 %, with a tenth run-time. The EFT-DT algorithm schedules a set of independent tasks onto a network of heterogeneous processors to minimize finish time when considering dispatch times of tasks. We compared the performance of EFT-DT with that of a First in First out (FIFO) schedule. In terms of minimizing makespan, on average EFT-DT outperformed FIFO by 30%.en_US
dc.language.isoen_USen_US
dc.subjectComputer Science and Software Engineeringen_US
dc.titleAlgorithms for Task Scheduling in Heterogeneous Computing Environmentsen_US
dc.typeDissertationen_US
dc.embargo.lengthNO_RESTRICTIONen_US
dc.embargo.statusNOT_EMBARGOEDen_US

Files in this item

Show simple item record