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

Refereed:

No

Supervisor(s):

O'hEigeartaigh, Micheál and Ryan, Michael

Uncontrolled Keywords:

Distributed systems; Parallel processing; Load balancing problem