A SIMD Approach to Parallel Heuristic Search
A SIMD Approach to Parallel Heuristic Search
复制标题
并行启发式搜索的 SIMD 方法
DOI：
10.1016/0004-3702(93)90003-t
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
C. J. Daniels
中科院分区：
文献类型：
--
作者：
A. Mahanti;C. J. Daniels
串行搜索算法通常表现出指数级的运行时间，也可能需要指数级的存储量。因此，设计具有有限内存的并行搜索算法是很有意义的。本文提出了一种高效的SIMD并行算法，称为IDPS（迭代深化并行搜索）。在广义上，IDPS是IDA *的平行版本。虽然我们通常将我们的算法称为IDPS，但通过在搜索算法的著名测试台问题（即15谜题）上进行的实验，我们研究了它的四个变体的性能。在实验中，采用两种不同的静态负载均衡方案收集数据。在第一种方案下，对于4K、8K和16K处理器，获得了大约3.4的非标准化平均效率。在第二种方案下，8K和16K处理器的非归一化平均效率分别为0.92和0.76，归一化平均效率分别为0.70和0.63。我们表明（如前面所示，仅针对MIMD机器），对于可接受的搜索，对于较大规模的问题可以获得较高的平均加速。我们相信这项研究将增强使用并行启发式搜索算法解决人工智能问题。
Serial search algorithms often exhibit exponential run times and may require an exponential amount of storage as well. Thus, the design of parallel search algorithms with limited memory is of obvious interest. This paper presents an efficient SIMD parallel algorithm, called IDPS (for iterative-deepening parallel search). At a broad level IDPS is a parallel version of IDA∗. While generically we have called our algorithm an IDPS, performance of four variants of it has been studied through experiments conducted on the well-known test-bed problem for search algorithms, namely the Fifteen Puzzle. During the experiments, data were gathered under two different static load balancing schemes. Under the first scheme, an unnormalized average efficiency of approximately 3 4 was obtained for 4K, 8K, and 16K processors. Under the second scheme, unnormalized average efficiencies of 0.92 and 0.76, and normalized average efficiencies of 0.70 and 0.63 were obtained for 8K and 16K processors, respectively. We show (as shown previously only for MIMD machines) that for admissible search, high average speedup can be obtained for problems of significant size. We believe that this research will enhance AI problem solving using parallel heuristic search algorithms.