PEBBL is a C++ class library implementing the underlying operations needed to support a wide variety of branch-and-bound algorithms in a message-passing parallel computing environment. Deriving application-speci c classes from PEBBL, one may create parallel branch-and-bound applications through a process focused on the unique aspects of the application, while relying on PEBBL for generic aspects of branch and bound, such as managing the active subproblem pool across multiple processors, load balancing, and termination detection. PEBBL is designed to provide highly scalable performance on large numbers of processor cores, using a distributed-memory programming model and MPI message passing. We describe the basics of PEBBL’s architecture and usage, with emphasis on the library’s key innovations and contributions, including the notion of branch and bound as a set of operators that manipulate subproblem state transitions. We also describe PEBBL’s special features, such as parallel checkpointing, support for specialized ramp-up procedures, and the ability to exhaustively enumerate speci ed sets of near-optimal solutions. Finally, we present an example application, the maximum monomial agreement (MMA) problem arising in machine learning applications. For suciently difficult problem instances, we show essentially linear speedup on over 6,000 processor cores. We also show how processor cache e ects can produce reproducibly superlinear speedups.
Citation
RUTCOR Research Report RRR 9-2013, Rutgers University, September 2013.