Menu
This paper studies the problem of allocating interacting program modules, of a distributed program, to the heterogeneous processors in a distributed computer system. The interacting program/task modules are represented by an undirected task graph, whose vertices denote task modules and edges denote interactions between modules. We are given the execution cost of a task module on each processor, the communication cost between two task modules if they are placed on different processors, and the interference cost between two task modules if they are placed on the same processor. The objective of our problem is to assign task modules to the processors such that the total of the above three costs incurred by the program on the system is minimized. The above task assignment problem is known to be NP-hard for a three processor system, but its complexity for a two processor system remained open. In this paper we prove that the problem remains NP-hard for a two processor system even when (1) task graph is planar and has maximum degree \(3\) or (2) task graph is bipartite. We then present three heuristics, based on simulated annealing, tabu search, and stochastic probe approaches respectively. We present an experimental analysis of these three heuristics, and compare their performance with the only known heuristic method in the literature. Our experiments demonstrate that our heuristics provide major improvements.