On the asymptotic optimality of a heuristic mapping algorithm

The mapping of large-scale resource allocation algorithms onto parallel computing architectures is considered. The mapping problem is viewed as one of assigning the nodes of a finite directed acyclic task graph representing the logical and data dependencies among the tasks constituting the algorithm on to the nodes of a finite undirected processor graph denoting the parallel computing architecture so that the completion time of the algorithm is minimized. Two algorithms for solving the mapping problem are presented. The first algorithm is a two-stage heuristic that determines the order of task allocation on the basis of the critical path method and then uses the greedy method to determine the task allocation. The second algorithm uses the idea of pairwise exchange on task allocation order to improve the performance of the greedy heuristic. Extensive computational experiments on hundreds of random graphs show that the heuristic algorithm provides optimal solutions when the ratio of computation time to communication time is very large or very small, and that the pairwise exchange algorithm provides uniformly good mapping for all values of the ratio. The asymptotic optimality of the greedy heuristic algorithm for fork-join task structures is established