Contents

• Introduction

• Documentation

• Request Library

• Publications

• Contact, Comments, and Questions

University of Paderborn	Research Group Prof.Dr.B.Monien

Introduction

Each parallel running process of the Branch-and-Bound application maintains the point of view of the sequential algorithm. The library overtakes the management of the subproblems, which are created during execution of the Branch-and-Bound algorithm. Load balancers provided by the library take care of a balanced distribution of the subproblems.

The quality of the load balancing strategy is essential for the parallel performance of a sequential efficient Branch-and-Bound algorithm. The user of the library is able to implement own load balancing strategies instead of using the application-independent load balancing algorithms included in the library.

Thus, on the first hand the library can be used for the automatic parallelization of sequential Branch-and-Bound algorithms. On the other hand it can be used for implementing and testing load balancing strategies while the loads are provided by a particular Branch-and-Bound application.

The library is designed to run on any distributed memory multicomputer architecture using the given message passing functions and is written in C.

The library is available for the following software environments and computing platforms at the moment:

• Distributed Memory Multicomputer Architecture
  • PVM / PowerPVM
    • SOLARIS OS
    • SUN 4 OS
    • GCel 1024
    • GC/PP-64
    • CC-48

  • PARIX
    • GCel 1024
    • GC/PP-64
    • CC-48

• Shared Memory Multicomputer Architecture
  • SUN 4 OS
  • LINUX OS

• Single Computer Architectures
  • SOLARIS OS
  • SUN 4 OS
  • LINUX OS

To request a library version skip to section Request Library. For a detailed description of the library see the subsections of section Documentation, especially the User Manual of PPBB-Lib.

Back to list of contents

Documentation

• User Manual (Version 2.0)

• Getting Started

• Library Versions
  • Sequential
  • Shared Memory
  • PVM
  • PowerPVM
  • PARIX

• Load Balancers
  • Standard Load Balancer
  • Random Allocation
  • Prioritized Random Allocation
  • Adaptive Contracting Within Neighborhood
  • Prioritized Adaptive Contracting Within Neighborhood
  • Local Averaging: Diffusion
  • Local Averaging: Dimension-Exchange

• Applications
  • Test Application
  • Flow Shop with Multiple Processors
  • Set Partitioning

Back to list of contents

Download PPBB-Lib

• PPBB-LIB.tar.gz
• PPBB-SRC-SEQ.tar.gz

Publications

• Chengzhong Xu; Stefan Tschöke & Burkhard Monien:
  Performance Evaluation of Load Distribution Strategies in Parallel Branch and Bound Computations
  Proc. of the 7th IEEE Symposium on Parallel and Distributed Processing, SPDP'95,
  pp. 402-405, 1995.
  

• Stefan Tschöke, Norbert Holthöfer:
  A New Parallel Approach to the Constrained Two-Dimensional Cutting Stock Problem
  Proc. of the Second International Workshop, IRREGULAR '95;
  Parallel Algorithms for Irregularly Structured Problems, LNCS 980,
  pp. 285-300, 1995.
  

Back to list of contents

Contact, Comments, and Questions

Address:

PPBB-Library

c/o Norbert Sensen

University of Paderborn

Dept. of Computer Science

Fuerstenallee 11

33102 Paderborn, Germany

Phone +49 +5251 60-6728

Fax +49 +5251 60-6697

E-mail:

ppbb-lib@uni-paderborn.de

Back to list of contents