Task Assignment in Parallel Processor Systems
Sathiamoorthy Manoharan
Ph. D.
University of Edinburgh
This thesis studies the problem of assigning programs onto parallel processor systems. It develops a generic simulation environment to model parallel systems and uses this environment to assess various assignment techniques.
Graphs are used in modelling programs, and based on these program models, a taxonomy for assignment schemes is proposed. Assignment schemes are broadly classified into schemes dealing with dependency graphs and schemes dealing with interaction graphs. Desirable properties for efficient assignments under different program models are discussed.
In contrast to the assignment of an interaction graph, an assignment of a dependency graph, in general, can be proved to be close to the optimal assignment. Moreover, the explicit temporal information made available by dependency graphs helps in establishing better assignment heuristics. The thesis thus focuses on the assignment of dependency graphs.
Most of the published schemes for assigning dependency graphs are work-greedy. Their heuristics is based on satisfying the following rule of thumb: keeping the processors busy will lead to a 'good' assignment. These schemes do not let a processor idle if there is a task the processor could execute. New analytical results bounding the performance of work-greedy assignment schemes are derived. It is shown that, when communication costs cannot be ignored, work-greedy assignment schemes may not perform well. An alternative assignment scheme which has a time-complexity lower than those of the work-greedy schemes is proposed.
A generic object-oriented simulation platform is developed in order to conduct experiments on the performance of assignment schemes. The simulation platform, called Genesis, is generic in the sense that it can model the key parameters that describe a parallel system: the architecture, the program, the assignment scheme and the message routing strategy. Genesis uses as its basis a sound architectural representation scheme developed in the thesis.
The thesis reports results from a number of experiments assessing the performance of assignment schemes using Genesis. The comparison results indicate that the new assignment scheme proposed in this thesis is a promising alternative to the work-greedy assignment schemes. The proposed scheme has a time-complexity less than those of the work-greedy schemes and achieves an average performance better than, or comparable to, those of the work-greedy schemes.
To generate an assignment, some parameters describing the program model will be required. In many cases, accurate estimation of these parameters is hard. It is thought that inaccuracies in the estimation would lead to poor assignments. The thesis investigates this speculation and presents experimental evidence that shows such inaccuracies do not greatly affect the quality of the assignments.
To my supervisors Nigel Topham and Roland Ibbett for their time and helpful advices; to Peter Thanisch for our fruitful discussions and his many useful comments; to David Skillicorn for his help throughout the development of Genesis; to Roy Campbell for object-orienting me; to Tom Waring and Leslie Goldberg for their advice, suggestions and encouragement; and to everyone who helped me with my work.
To the Department of Computer Science for providing me with an interesting work environment.
I was supported by a University of Edinburgh Postgraduate Studentship and an Overseas Research Students Award.
This thesis was composed by myself. The work and the results reported herein are my own except where otherwise stated.
Some of the material in this thesis has already been published in: