Sinclair, David (1993) Load balancing in parallel and distributed systems. PhD thesis, Dublin City University.
Abstract
Two major barriers prevent the widespread, common usage of
parallel and distributed computing systems:
(1) A language which expresses parallelism without reference to the underlying hardware configuration.
(2) A user invisible method for effectively distributing the tasks that form the parallel/distributed program among the available processing nodes. This is known as the load balancing problem.
This thesis examines the load balancing problem. This problem of allocating n inter-communicating tasks among m processing nodes is formulated as a non-symmetric mathematical programming problem, which minimises the makespan, and is shown to be quadratic and discrete. A novel relaxation is developed which exploits the discrete nature of the problem, and this relaxed formulation is used to generate strong upper bounds.
Two novel heuristic algorithms are proposed. A static load
balancing algorithm, the Maximum (k-1) Sum algorithm, is developed for maximising the throughput of tasks in a parallel or distributed system. This algorithm is compared with recently published results. An on-line load balancing algorithm, the Pseudo-Dynamic Load Balancing algorithm, is developed from the mathematical analysis of the problem. This algorithm seeks to minimise the makespan of a program, and is compared with standard combinatorial optimisation techniques, such as Simulated Annealing and Tabu Search, as well as the upper bounds set by the relaxed non-symmetric mathematical formulation. Both of these new algorithms are shown to provide efficient allocations of n tasks among m processing nodes.
Finally the Pseudo-Dynamic Load Balancing algorithm is analysed to determine its worst case scheduling ratio, RPD, and the conditions under which this worst case occurs.
Metadata
Item Type: | Thesis (PhD) |
---|---|
Date of Award: | 1993 |
Refereed: | No |
Supervisor(s): | O'hEigeartaigh, Micheál and Ryan, Michael |
Uncontrolled Keywords: | Distributed systems; Parallel processing; Load balancing problem |
Subjects: | Computer Science > Computational complexity Computer Science > Algorithms |
DCU Faculties and Centres: | DCU Faculties and Schools > Faculty of Engineering and Computing > School of Computing |
Use License: | This item is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 3.0 License. View License |
ID Code: | 19423 |
Deposited On: | 02 Oct 2013 13:14 by Celine Campbell . Last Modified 09 Oct 2013 12:52 |
Documents
Full text available as:
Preview |
PDF
- Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
2MB |
Downloads
Downloads
Downloads per month over past year
Archive Staff Only: edit this record