Divisible load scheduling on multi-level processor trees
| dc.contributor.advisor | Aubanel, Eric | |
| dc.contributor.author | Lord, Mark | |
| dc.date.accessioned | 2023-03-01T16:16:25Z | |
| dc.date.available | 2023-03-01T16:16:25Z | |
| dc.date.issued | 2011 | |
| dc.date.updated | 2016-12-13T00:00:00Z | |
| dc.description.abstract | Divisible 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.note | Degree 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.note | M.C.S., University of New Brunswick, Faculty of Computer Science, 2011. | |
| dc.format | text/xml | |
| dc.format.extent | viii, 89 pages | |
| dc.format.medium | electronic | |
| dc.identifier.oclc | (OCoLC)960871143 | |
| dc.identifier.other | Thesis 8661 | |
| dc.identifier.uri | https://unbscholar.lib.unb.ca/handle/1882/13216 | |
| dc.language.iso | en_CA | |
| dc.publisher | University of New Brunswick | |
| dc.rights | http://purl.org/coar/access_right/c_abf2 | |
| dc.subject.discipline | Computer Science | |
| dc.subject.lcsh | Computer algorithms. | |
| dc.subject.lcsh | Problem solving -- Data processing. | |
| dc.subject.lcsh | Computer scheduling. | |
| dc.subject.lcsh | Computer networks. | |
| dc.title | Divisible load scheduling on multi-level processor trees | |
| dc.type | master thesis | |
| thesis.degree.discipline | Computer Science | |
| thesis.degree.fullname | Master of Computer Science | |
| thesis.degree.grantor | University of New Brunswick | |
| thesis.degree.level | masters | |
| thesis.degree.name | M.C.S. |
Files
Original bundle
1 - 1 of 1