Evaluation of a simple, scalable, parallel best-first search strategy
Evaluation of a simple, scalable, parallel best-first search strategy
复制标题
评估简单、可扩展、并行的最佳优先搜索策略
DOI：
10.1016/j.artint.2012.10.007
复制
发表时间：
2013
影响因子：
14.4
通讯作者：
Botea A
中科院分区：
文献类型：
--
作者：
Kishimoto A;Fukunaga A;Botea A
由商用处理器组成的大规模并行集群越来越多，从而能够使用巨大的处理能力和分布式 RAM 来解决硬搜索问题。我们研究了哈希分布式 A⁎（HDA⁎），这是一种并行最佳优先搜索的简单方法，它基于搜索状态的哈希函数在处理器之间异步分配和调度工作。我们使用这种方法在快速向下规划器的最佳顺序版本以及 24 谜题求解器中并行化 A⁎ 算法。 HDA⁎ 的扩展行为在共享内存、具有 8 个核心的多核机器、使用最多 64 个核心的商用机器集群以及使用最多 2400 个处理器的大规模高性能集群上进行了实验评估。我们证明这种方法具有良好的扩展性，可以有效利用大量分布式内存，以最佳方式解决需要 TB RAM 的问题。我们还将 HDA⁎ 与换位表驱动调度 (TDS)（一种基于哈希的 IDA⁎ 并行化）进行比较，并表明，在规划方面，HDA⁎ 显着优于 TDS。提出并评估了一种简单的混合算法，它将 HDA⁎ 和 TDS 结合起来，以利用两种算法的优势。
Large-scale, parallel clusters composed of commodity processors are increasingly available, enabling the use of vast processing capabilities and distributed RAM to solve hard search problems. We investigate Hash-Distributed A⁎(HDA⁎), a simple approach to parallel best-first search that asynchronously distributes and schedules work among processors based on a hash function of the search state. We use this approach to parallelize the A⁎algorithm in an optimal sequential version of the Fast Downward planner, as well as a 24-puzzle solver. The scaling behavior of HDA⁎is evaluated experimentally on a shared memory, multicore machine with 8 cores, a cluster of commodity machines using up to 64 cores, and large-scale high-performance clusters, using up to 2400 processors. We show that this approach scales well, allowing the effective utilization of large amounts of distributed memory to optimally solve problems which require terabytes of RAM. We also compare HDA⁎to Transposition-table Driven Scheduling (TDS), a hash-based parallelization of IDA⁎, and show that, in planning, HDA⁎significantly outperforms TDS. A simple hybrid which combines HDA⁎and TDS to exploit strengths of both algorithms is proposed and evaluated.