Kim Joo Man, Yoon Suk Han, Lee Cheol Hoon

The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 5, No. 11, pp. 2823-2834, Nov. 1998
10.3745/KIPSTE.1998.5.11.2823,   PDF Download:

Abstract

This paper deals with the problem of one-to-one mapping of 2^n task modules of a parallel program to an n-dimensional hypercube multicomputer so as to minimize to total communication cost during the execution of the task. The problem of finding an optimal mapping has been proven to be NP-complete. We first propose a graph modification technique which transfers the mapping problem in a hypercube multicomputer into the problem of finding a set of maximum cutsets on a given task graph. Using the graph modification technique, we then propose a repeated mapping scheme which efficiently finds a one-to-one mapping of task modules to a hypercube multicomputer by repeatedly applying an existing bipartitioning algorithm on the modified graph. The repeated mapping scheme is shown to be highly effective on a number of test task graphs, it increasingly outperforms the greedy and recursive mapping algorithms as the number of processors increase. The proposed algorithm is shown to be very effective for regular graphs, such as hypercube-isomorphic of 'almost' isomorphic graphs and meshes; it finds optimal mappings on almost all the regular task graphs considered.

Statistics
Cite this article