Static task allocation for heterogeneous distributed computing systems

In this paper, we investigate the problem of static task allocation of concurrent programs for heterogeneous distributed computing systems, i.e, given a set of n concurrent communicating processes and a two processor distributed computing system, in which each processor may have certain resources not available with the other processor (i.e., unique resources), to which processor should each module be assigned so as to maximize the throughput? Our problem is a variant of the task allocation problem considered by Stone2 in that we consider concurrent execution of the processes comprising the task. Also we explicitly consider the resource usage costs for each module thereby resulting in a more realistic model of the distributed system. This task allocation problem is NP-hard and hence, we provide an efficient heuristic algorithm for obtaining satisfactory suboptimal solution to it in a reasonable amount of computation time. Our algorithm works by constructing an augmented task graph and taking a load balanced mincut on it and has a time complexity of O((n+m)2) where m is the total number of unique resources in the two processor system.