Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5626

On optimal task assignment algorithms in distributed computing systems

Authors Muhammad, Kafil
Issue Date 1996
Summary In a distributed system of networked heterogeneous processors, an efficient assignment of communicating tasks of an application to processors is imperative for achieving fast turnaround time. The assignment problem is known to be NP-hard, except in a few special cases. Without making strict assumptions, the assignment algorithm for a close-to-optimal solution can be computationally intensive. While the literature is full of a plethora of heuristic techniques that can yield sub-optimal solutions in a reasonable amount of time, we aim to develop in this study techniques for optimal solutions under the most relaxed assumptions. The basis of our research is the best-first search technique known as A* from the area of Artificial Intelligence. It guarantees optimal solution, but is not feasible for problems of practically large size due to its high time and space complexity. We propose a number of algorithms based around the A* technique which are considerably faster but still yield optimal solutions. The first is a parallel algorithm that exhibits a reasonable speedup. Parallelizing the assignment algorithm is a natural way to lower the time complexity, and we believe our algorithm to be novel in using this approach. Second, we propose a clustering based pre-processing algorithm that merges the high affinity tasks together. This reduces the problem size which in turn reduces the state-space for the assignment algorithm. For even faster solutions, we propose three heuristics which do not guarantee optimal solutions but provide near-optimal solutions. The latter two approaches can also be parallelized using the proposed parallel formulation.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1996
Subjects
Language English
Format Thesis
Access
Files in this item:
File Description Size Format
th_redirect.html 345 B HTML