Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
DryadOpt: Branch-and-Bound on Distributed Data-Parallel Execution Engines

Mihai Budiu, Daniel Delling, and Renato F. Werneck

Abstract

We introduce DryadOpt, a library that enables massively parallel and distributed execution of optimization algorithms for solving hard problems. DryadOpt performs an exhaustive search of the solution space using branch-and-bound, by recursively splitting the original problem into many simpler subproblems. It uses both parallelism (at the core level) and distributed execution (at the machine level). DryadOpt provides a simple yet powerful interface to its users, who only need to implement sequential code to process individual subproblems (either by solving them in full or generating new subproblems). The parallelism and distribution are handled automatically by DryadOpt, and are invisible to the user. The distinctive feature of our system is that it is implemented on top of DryadLINQ, a distributed data-parallel execution engine similar to Hadoop and Map-Reduce. Despite the fact that these engines offer a constrained application model, with restricted communication atterns, our experiments show that careful design choices allow DryadOpt to scale linearly with the number of machines, with very little overhead.

Details

Publication typeInproceedings
Published in25th International Parallel and Distributed Processing Symposium (IPDPS'11)
PublisherIEEE
> Publications > DryadOpt: Branch-and-Bound on Distributed Data-Parallel Execution Engines