Overlay-Centric Load Balancing: Applications to UTS and B&B
Loading...
Date
2012-09-24
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
To deal with dynamic load balancing in large scale distributed systems, we propose to organize computing resources following a logical peer-to-peer overlay and to distribute the load according to the so-defined overlay. We use a tree as a logical structure connecting distributed nodes and we balance the load according to the size of induced subtrees. We conduct extensive experiments involving up to 1000 computing cores and provide a throughout analysis of different properties of our generic approach for two different applications, namely, the standard Unbalanced Tree Search and the more challenging parallel Branch-and-Bound algorithm. Substantial improvements are reported in comparison with the classical random work stealing and two finely tuned application specific strategies taken from the literature.
Description
Keywords
Branch and Bound, P2P, Load Balancing, Hierarchical Master Worker