|
|
PBB
A framework for parallel implementation of branch-and-bound
algorithms in grid environments.
Ian Foster and Adriana Iamnitchi.
The idle computers on a local area, campus area, or even wide area
network represent a significant computational resource---one that is, however,
also unreliable, heterogeneous, and opportunistic. This type of
resource has been used effectively for embarrassingly parallel
problems but not for more tightly coupled problems. We describe an
algorithm that allows branch-and-bound problems to be solved in such
environments. In designing this algorithm, we faced two challenges:
(1) scalability, to effectively exploit the variably sized pools of
resources available, and (2) fault tolerance, to ensure the
reliability of services. We achieve scalability through a fully
decentralized algorithm, by using a membership protocol for managing
dynamically available resources. However, this fully decentralized
design makes achieving reliability even more challenging. We guarantee fault
tolerance in the sense that the loss of
up to all but one resource will not affect the quality of the
solution. For propagating information efficiently, we use epidemic
communication for both the membership protocol and the fault-tolerance
mechanism. We have developed a simulation framework that allows us
to evaluate design alternatives. Results obtained in this framework
suggest that our techniques can execute scalably and reliably.
More on PBB :
|
