Distributed Cube and Conquer with Paracooba
Distributed Cube and Conquer with Paracooba
复制标题
DOI：
10.1007/978-3-030-51825-7_9
复制
发表时间：
2020-06-26
期刊：
影响因子：
--
通讯作者：
Biere A
中科院分区：
文献类型：
--
作者：
Heisinger M;Fleury M;Biere A
Cube and conquer是目前并行求解组合难题最有效的方法。它将搜索分为两个阶段。首先，前瞻求解器将问题分成许多子问题，称为立方体，然后由增量CDCL求解器并行求解。在这篇工具论文中，我们提出了第一个完全集成的自动分布式立方体和征服求解器Paracooba，目标是集群和云计算。以前的工作仅限于多核并行或依赖于解决过程的手动编排。我们的方法使用一个主每个问题来初始化解决过程，并自动发现和释放计算节点，通过弹性资源使用。多个问题可以在共享计算节点上并行解决，由基于自定义对等的负载平衡协议控制。实验表明，我们的方法的可扩展性。
Cube and conquer is currently the most effective approach to solve hard combinatorial problems in parallel. It organizes the search in two phases. First, a look-ahead solver splits the problem into many sub-problems, called cubes, which are then solved in parallel by incremental CDCL solvers. In this tool paper we present the first fully integrated and automatic distributed cube-and-conquer solver Paracooba targeting cluster and cloud computing. Previous work was limited to multi-core parallelism or relied on manual orchestration of the solving process. Our approach uses one master per problem to initialize the solving process and automatically discovers and releases compute nodes through elastic resource usage. Multiple problems can be solved in parallel on shared compute nodes, controlled by a custom peer-to-peer based load-balancing protocol. Experiments show the scalability of our approach.
登录
查看更多内容
DOI：
10.3233/978-1-58603-929-5-131
发表时间：
2009-01-01
期刊：
HANDBOOK OF SATISFIABILITY
影响因子：
--
作者：
Marques-Silva, Joao;Lynce, Ines;Malik, Sharad
通讯作者：
Malik, Sharad
影响因子：
1.4
作者：
Blochinger, W;Sinz, C;Küchlin, W
通讯作者：
Küchlin, W
DOI：
10.1007/11499107_5
发表时间：
2005-01-01
期刊：
THEORY AND APPLICATIONS OF SATISFIABILITY TESTING, PROCEEDINGS
影响因子：
--
作者：
Eén, N;Biere, A
通讯作者：
Biere, A
DOI：
10.3233/978-1-58603-929-5-457
发表时间：
2009-01-01
期刊：
HANDBOOK OF SATISFIABILITY
影响因子：
--
作者：
Biere, Armin
通讯作者：
Biere, Armin
影响因子：
14.4
作者：
Konev, Boris;Lisitsa, Alexei
通讯作者：
Lisitsa, Alexei