Grid’BnB: A Parallel Branch and Bound Framework for Grids
説明
This article presents Grid'BnB, a parallel branch and bound framework for grids. Branch and bound (B&B) algorithms find optimal solutions of search problems and NP-hard optimization problems. Grid'BnB is a Java framework that helps programmers to distribute problems over grids by hiding distribution issues. It is built over a masterworker approach and provides a transparent communication system among tasks. This work also introduces a new mechanism to localize computational nodes on the deployed grid. With this mechanism, we can determine if two nodes are on the same cluster. This mechanism is used in Grid'BnB to reduce inter-cluster communications. We run experiments on a nationwide grid. With this test bed, we analyze the behavior of a communicant application deployed on a large-scale grid that solves the flow-shop problem.