HEURISTIC ALGORITHMS FOR TASK ASSIGNMENT IN DISTRIBUTED SYSTEMS

The problem of static 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 each task should be assigned, is addressed. The author proposes a family of heusristic algorithms for H. S. Stone's (1977) classic model of communicating tasks whose goal is the minimization of the total execution and communication costs incurred by an assignment. This model is augmented to include interference costs which reflect the degree of incompatibility betweenn two tasks. Whereas high communication costs serve as a force of 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 procesors. The inclusion of interference costs in the model yields assignments with greater concurrency, thus overcoming the tendency of Stone's model to assign all tasks to one or a few processors. Simulation results show that the algorithms perform well and, in particular, that the highly efficient simple greedy algorithm performs almost as well as more complex heuristic algorithms.