A dominance relation enhanced branch-and-bound task allocation

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.