TASK ASSIGNMENT AND TRANSACTION CLUSTERING HEURISTICS FOR DISTRIBUTEDSYSTEMS

In this paper, we present and discuss the task assignment problem for distributed systems. We also show how this problem is very similar to that of clustering transactions for load balancing purposes and for th eir efficient execution in a distributed environment. The formalizatio n of these problems in terms of a graph-theoretic representation of a distributed program, or of a set of related transactions, is given. Th e cost function which needs to be minimized by an assignment of tasks to processors or of transactions to clusters is detailed, and we surve y related work, as well as work on the dynamic load balancing problem. Since the task assignment problem is NP-hard, we present three novel heuristic algorithms that we have tested for solving it and compare th em to the well-known greedy heuristic. These novel heuristics use neur al networks, genetic algorithms, and simulated annealing. Both the res ulting performance and the computational cost for these algorithms are evaluated on a large number of randomly generated program graphs of d ifferent sizes. (C) Elsevier Science Inc. 1997