Divisible load scheduling on multi-level processor trees

dc.contributor.advisorAubanel, Eric
dc.contributor.authorLord, Mark
dc.description.abstractDivisible Load Theory (DLT) is an effective tool for blueprinting data-intensive computational problems. Heuristic algorithms have been proposed in the past to solve for a DLS (Divisible Load Schedule) with result collection on heterogeneous star networks. However scheduling on heterogeneous multi-level trees with result collection is still an open problem. In this thesis, new heuristic algorithms for scheduling divisible loads on heterogeneous multi-level trees (single- and two-installment) including result collection are presented. Experiments are performed on both random networks and cluster networks. Results show that scheduling using multi-level trees produces lower solution times compared to the traditional star network in the majority of cases, however efficiency of resources in multi-level trees tends to be lower, i.e., more processors were used. Cluster results with multi-level trees are found to outperform the star when there are enough clusters available to provide good overlap of communication and computation. Experiments on random networks with varying levels of heterogeneity of resources show that multi-level trees outperform star networks in the majority of cases. Experiments were conducted comparing schedules with and without latency costs. The results from all schedules where latency was considered had signifiantly lower solution times and higher efficiency of resources. Overall, scheduling on single-installment multi-level trees in either clusters or random networks had the lowest solution times, but the star had highest efficiency of resources.
dc.description.copyright© Mark Lord, 2011
dc.description.noteDegree name on title page is mislabeled as "Master of Computer Science In the Graduate Academic Unit of in the Graduate Academic Unit of Computer Science". Also, pagination is wrong. The last page of the front matter (second page of List of Figures) is paginated with an Arabic number 1 (one) instead of a Roman number viii (eight). i.e. Page viii is labeled as page 1, page 1 is labeled as page 2, …, page 89 (last page) is labeled as page 90. Electronic Only. (UNB thesis number) Thesis 8661 (OCoLC) 960871143
dc.description.noteM.C.S., University of New Brunswick, Faculty of Computer Science, 2011.
dc.format.extentviii, 89 pages
dc.identifier.otherThesis 8661
dc.publisherUniversity of New Brunswick
dc.subject.disciplineComputer Science
dc.subject.lcshComputer algorithms.
dc.subject.lcshProblem solving -- Data processing.
dc.subject.lcshComputer scheduling.
dc.subject.lcshComputer networks.
dc.titleDivisible load scheduling on multi-level processor trees
dc.typemaster thesis
thesis.degree.disciplineComputer Science
thesis.degree.fullnameMaster of Computer Science
thesis.degree.grantorUniversity of New Brunswick


Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
2.41 MB
Adobe Portable Document Format