A dominance relation enhanced branch-and-bound task allocation

Yung Cheng Ma*, Chung-Ping Chung

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

5 Scopus citations

Abstract

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 optimal task assignment. The key observation on deriving the dominance relation is that tasks can be clustered according to communication weights. The dominance relation is effective to prune the search space when the task clustering boundary - a small cut - is met. The proposed algorithm is compared to the A*-algorithm for task allocation. Experiment shows that our proposed algorithm achieves a speed-up ranging from 1.02 to 1.68, depending on the degree of task clustering and parallelism. This shows the effectiveness of the proposed dominance relation.

Original languageEnglish
Pages (from-to)125-134
Number of pages10
JournalJournal of Systems and Software
Volume58
Issue number2
DOIs
StatePublished - 1 Sep 2001

Keywords

  • Branch-and-bound algorithm
  • Dominance relation
  • Task allocation

Fingerprint Dive into the research topics of 'A dominance relation enhanced branch-and-bound task allocation'. Together they form a unique fingerprint.

Cite this