Generic Exact Combinatorial Search at HPC Scale
Generic Exact Combinatorial Search at HPC Scale
复制标题
HPC 规模的通用精确组合搜索
DOI：
10.1007/s10766-022-00744-3
复制
发表时间：
2022
影响因子：
1.5
通讯作者：
MacGregor R
中科院分区：
文献类型：
--
作者：
MacGregor R
精确的组合搜索对于广泛的重要应用是必不可少的，并且有许多大问题需要快速解决。由于多种因素的组合，并行化搜索极具挑战性，例如搜索是不确定的，动态修剪会改变工作负载，并且搜索任务具有非常不同的运行时间。YewPar是一个C++/HPX框架，它通过提供一系列复杂的搜索框架来推广并行搜索，本文展示了通用的高性能组合搜索，即使用YewPar可以很容易地为HPC并行化各种精确的组合搜索。我们提出了一个新的机制，分析的关键方面的YewPar并行组合搜索，并证明其价值。我们展出，第一次，在HPC规模的通用精确组合搜索。我们将YewPar与最先进的顺序C++和C++/OpenMP实现进行比较。我们证明了在HPC系统上部署YewPar可以大大减少大型问题的运行时间，例如从几天到100秒。对于枚举搜索，我们实现的最大相对加速是接近线性的，最多可达195（6825）个计算节点（工人），对于优化搜索，最多可达128（4480）个（修剪减少了工作量），对于决策搜索，最多可达64（2240）个计算节点（工人）。
Exact combinatorial search is essential to a wide range of important applications, and there are many large problems that need to be solved quickly. Searches are extremely challenging to parallelise due to a combination of factors, e.g. searches are non-deterministic, dynamic pruning changes the workload, and search tasks have very different runtimes. YewPar is a C++/HPX framework that generalises parallel search by providing a range of sophisticated search skeletons.This paper demonstratesgenerichigh performance combinatorial search, i.e. that a variety of exact combinatorial searches can be easily parallelised for HPC using YewPar. We present a new mechanism for profiling key aspects of YewPar parallel combinatorial search, and demonstrate its value. We exhibit, for the first time, generic exact combinatorial searches at HPC scale. We baseline YewPar against state-of-the-art sequential C++ and C++/OpenMP implementations. We demonstrate that deploying YewPar on an HPC system can dramatically reduce the runtime of large problems, e.g. from days to just 100s. The maximum relative speedups we achieve for an enumeration search are near-linear up to 195(6825) compute-nodes(workers), super-linear for an optimisation search on up to 128(4480) (pruning reduces the workload), and sub-linear for decision searches on up to 64(2240) compute-nodes(workers).
登录
查看更多内容
影响因子：
2
作者：
J. Fromentin;F. Hivert
通讯作者：
F. Hivert
使用 TASKWORK 的弹性并行树搜索应用程序的开发和操作
DOI：
10.1007/978-3-030-49432-2_3
发表时间：
2019
期刊：
Bioscience, Biotechnology, and Biochemistry
影响因子：
--
作者：
Stefan Kehrer;Wolfgang Blochinger
通讯作者：
Wolfgang Blochinger
DOI：
10.1007/978-3-030-51372-6_19
发表时间：
2020-05-31
期刊：
Graph Transformation
影响因子：
--
作者：
McCreesh C;Prosser P;Trimble J
通讯作者：
Trimble J
Bob：并行机上精确组合优化方法的框架
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
François Galea;B. L. Cun
通讯作者：
B. L. Cun
MALLBA：用于组合优化的骨架库（研究笔记）
影响因子：
1.6
作者：
E. Alba;F. Almeida;M. Blesa;J. Cabeza;C. Cotta;M. Díaz;I. Dorta;J. Gabarró;C. León;J. Luna;Luz Marina Moreno;C. Pablos;Jordi Petit;Angélica Rojas;F. Xhafa
通讯作者：
F. Xhafa