HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses  >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/5626
Title: On optimal task assignment algorithms in distributed computing systems
Authors: Muhammad, Kafil
Issue Date: 1996
Abstract: 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.
Description: Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1996
xi, 54 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 1996 Muhamm
URI: http://hdl.handle.net/1783.1/5626
Appears in Collections:CSE Master Theses

Files in This Item:

File Description SizeFormat
th_redirect.html0KbHTMLView/Open

All items in this Repository are protected by copyright, with all rights reserved.