Login (DCU Staff Only)
Login (DCU Staff Only)

DORAS | DCU Research Repository

Explore open access research and scholarly works from DCU

Advanced Search

Load balancing in parallel and distributed systems

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:

[thumbnail of David_Sinclair_PhD_20130723133247.pdf]
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