Towards Generic Scalable Parallel Combinatorial Search
Towards Generic Scalable Parallel Combinatorial Search
复制标题
DOI：
10.1145/3115936.3115942
复制
发表时间：
2017-07
期刊：
影响因子：
--
通讯作者：
B. Archibald;Patrick Maier;Robert J. Stewart;P. Trinder;J. Beule
中科院分区：
文献类型：
--
作者：
B. Archibald;Patrick Maier;Robert J. Stewart;P. Trinder;J. Beule
数学中的组合搜索问题，例如在有限的几何形状中，众所周知。最新的回溯搜索算法很容易花几个月的时间才能解决一个问题。显然，需要平行的组合搜索算法扩展到数百个核心及以后。但是，由于它们对搜索顺序的敏感性以及它们形状不规则的搜索树，因此回溯组合搜索的挑战是平行的。此外，将平行搜索扩展到数百个核心通常需要高度专业的平行编程专业知识。本文提出了一个通用可扩展框架，用于解决硬组合问题。关键元素是分布式内存任务并行性（以实现规模），窃取工作（以应对不规则性）以及用于组合搜索的通用算法骨骼（以减少所需的并行性专业知识）。我们概述了两个实现：基于算法骨架和使用手动编码应用程序的原型C ++树搜索库（CTSL），一个成熟的Haskell树搜索库（HTSL）。在最大集团问题和有限几何形状中的问题上进行的实验，在H（4，22）中进行的搜索扩散表明（1）CTSL在顺序运行上始终优于HTSL，并且（2）两个库尺度缩放到200个核心，例如。加速搜索分别为81（HTSL）和60（CTSL）。这证明了我们通用框架将并行组合搜索扩展到大型分布式存储平台的潜力。
Combinatorial search problems in mathematics, e.g. in finite geometry, are notoriously hard; a state-of-the-art backtracking search algorithm can easily take months to solve a single problem. There is clearly demand for parallel combinatorial search algorithms scaling to hundreds of cores and beyond. However, backtracking combinatorial searches are challenging to parallelise due to their sensitivity to search order and due to the their irregularly shaped search trees. Moreover, scaling parallel search to hundreds of cores generally requires highly specialist parallel programming expertise. This paper proposes a generic scalable framework for solving hard combinatorial problems. Key elements are distributed memory task parallelism (to achieve scale), work stealing (to cope with irregularity), and generic algorithmic skeletons for combinatorial search (to reduce the parallelism expertise required). We outline two implementations: a mature Haskell Tree Search Library (HTSL) based around algorithmic skeletons and a prototype C++ Tree Search Library (CTSL) that uses hand coded applications. Experiments on maximum clique problems and on a problem in finite geometry, the search for spreads in H(4, 22), show that (1) CTSL consistently outperforms HTSL on sequential runs, and (2) both libraries scale to 200 cores, e.g. speeding up spreads search by a factor of 81 (HTSL) and 60 (CTSL), respectively. This demonstrates the potential of our generic framework for scaling parallel combinatorial search to large distributed memory platforms.