ALGORITHMIC SKELETONS FOR BRANCH & BOUND

Michael Poldner, Herbert Kuchen

2006

Abstract

Algorithmic skeletons are predefined components for parallel programming. We will present a skeleton for branch & bound problems for MIMD machines with distributed memory. This skeleton is based on a distributed work pool. We discuss two variants, one with supply-driven work distribution and one with demanddriven work distribution. This approach is compared to a simple branch & bound skeleton with a centralized work pool, which has been used in a previous version of our skeleton library Muesli. Based on experimental results for two example applications, namely the n-puzzle and the traveling salesman problem, we show that the distributed work pool is clearly better and enables good runtimes and in particular scalability. Moreover, we discuss some implementation aspects such as termination detection as well as overlapping computation and communication.

Paper Citation

in Harvard Style

Poldner M. and Kuchen H. (2006). ALGORITHMIC SKELETONS FOR BRANCH & BOUND . In Proceedings of the First International Conference on Software and Data Technologies - Volume 1: ICSOFT, ISBN 978-972-8865-69-6, pages 291-300. DOI: 10.5220/0001315002910300

in Bibtex Style

@conference{icsoft06,
author={Michael Poldner and Herbert Kuchen},
title={ALGORITHMIC SKELETONS FOR BRANCH & BOUND},
booktitle={Proceedings of the First International Conference on Software and Data Technologies - Volume 1: ICSOFT,},
year={2006},
pages={291-300},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001315002910300},
isbn={978-972-8865-69-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Software and Data Technologies - Volume 1: ICSOFT,
TI - ALGORITHMIC SKELETONS FOR BRANCH & BOUND
SN - 978-972-8865-69-6
AU - Poldner M.
AU - Kuchen H.
PY - 2006
SP - 291
EP - 300
DO - 10.5220/0001315002910300