Browse DORAS
Browse Theses
Latest Additions
Creative Commons License
Except where otherwise noted, content on this site is licensed for use under a:

Load balancing in parallel and distributed systems

Sinclair, David (1993) Load balancing in parallel and distributed systems. PhD thesis, Dublin City University.

Full text available as:

[img]PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


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.

Item Type:Thesis (PhD)
Date of Award:1993
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 14:14 by Celine Campbell. Last Modified 09 Oct 2013 13:52

Download statistics

Archive Staff Only: edit this record