We investigate the task allocation problem of allocating a parallel program
on parallel processors with non-uniform communication latencies. A branch-
and-bound algorithm with a dominance relation is proposed to obtain an opti
mal task assignment. The key observation on deriving the dominance relation
is that tasks can be clustered according to communication weights. The dom
inance relation is effective to prune the search space when the task cluste
ring boundary - a small cut - is met. The proposed algorithm is compared to
the A*-algorithm for task allocation. Experiment shows that our proposed a
lgorithm achieves a speed-up ranging from 1.02 to 1.68, depending on the de
gree of task clustering and parallelism. This shows the effectiveness of th
e proposed dominance relation. (C) 2001 Elsevier Science Inc. All rights re
served.