PEBBL an objectoriented framework for scalable p

Authors: Jonathan Eckstein William E Hart Cynthia A Phillips

Publish Date: 2015/07/23

Volume: 7, Issue: 4, Pages: 429-469

PDF Link

Abstract

Parallel Enumeration and BranchandBound Library PEBBL is a C++ class library implementing the underlying operations needed to support a wide variety of branchandbound algorithms on MPIbased messagepassing distributedmemory parallel computing environments PEBBL can be customized to support applicationspecific operations while managing the generic aspects of branch and bound such as maintaining 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 We describe the basics of PEBBL’s architecture with emphasis on the features most critical to is high scalability including its flexible twolevel load balancing architecture and its support for a synchronously parallel rampup phase We also present an example application the maximum monomial agreement problem arising from certain machine learning applications For sufficiently difficult problem instances we show essentially linear speedup on over 6000 processor cores demonstrating a new state of the art in scalability for branchandbound implementations We also show how processor cache effects can lead to reproducibly superlinear speedupsThis work was performed in part at Sandia National Laboratories Sandia is a multiprogram laboratory operated by Sandia corporation a Lockheed Martin Company for the United States Department of Energy under Contract DEAC0494AL85000 This work was also supported in part by National Science Foundation Grant CCR9902092We thank Noam Goldberg for contributing the code to solve the MMA problem in serial using PEBBL We also thank John Siirola for his stewardship of PEBBL within the ACRO framework Jonathan Eckstein’s work on PEBBL was supported in part by NSF grant CCR9902092 Sandia National Laboratories is a multiprogram laboratory managed and operated by Sandia Corporation a wholly owned subsidiary of Lockheed Martin Corporation for the US Department of Energy’s National Nuclear Security Administration under contract DEAC0494AL85000

Keywords: