Heuristic Algorithms for Task Assignment in Distributed Systems
Virginia Lo
Committee:
Technical Report(Apr 1987)
Keywords:

In this paper we investigate the problem of task assignment in distributed computing systems, i.e., given a set of k communicating tasks to be executed on a distributed system of n processors, to which processor should each task be assigned? We propose a family of heuristic algorithms for Stone's classic model of communicating tasks which considers the execution cost of each task on each processor and the communication costs between tasks. We augment this model to include interference costs which reflect the degree of imcompatibility between two tasks. Whereas high communication costs serve as a force af attraction between tasks, causing them to be assigned to the same processor, interference costs serve as a force of repulsion between tasks, causing them to be distributed over many processors. Simulation results show that our algorithms perform well and in particular, that the highly efficient Simple Greedy Algorithm performs almost as well as more complex heuristic algorithms. When we consider task assignment to be an initial placement of tasks subject to subsequent refinedment by dynamic task migration algorithms, efficient algorithms such as Simple Greedy are attractive candidates for practical distributed systems. If task assignment modules make a permanent assignment of tasks to processors, the increased overhead of a more complex heuristic is justified for the improvement in the assignment.