Scalable Global and Local Hashing Strategies for Duplicate Pruning in Parallel A* Graph Search
Scalable Global and Local Hashing Strategies for Duplicate Pruning in Parallel A* Graph Search
复制标题
并行 A* 图搜索中重复修剪的可扩展全局和局部哈希策略
DOI：
10.1109/71.598348
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
S. Dutt
中科院分区：
文献类型：
--
作者：
N. Mahapatra;S. Dutt
对于A*算法的许多应用，状态空间是一个图而不是树。这对于并行A*算法的含义是，如果不修剪处理器间的重复，不同的处理器可能会执行大量的重复工作。本文研究了在分布式内存机器上实现的并行A*图搜索算法中的重复剪枝问题。重复修剪的常用方法使用哈希函数将特定处理器与搜索空间的每个不同节点相关联，在不同处理器中产生的重复节点被传输到该处理器并因此被修剪。这种方法有两个主要缺点。首先，负载平衡完全由哈希函数决定。其次，重复剪枝的节点传输是全局的；这可能导致热点和较慢的消息传递。为了克服这些问题，我们提出了两种不同的重复修剪策略：1)为了实现良好的负载平衡，我们将重复修剪任务与负载平衡解耦，通过对前者使用哈希函数，对后者使用负载平衡方案。2)提出了一种新的搜索空间分区方案，该方案将搜索空间的不相交部分分配给超立方体中不相交的子立方体（或目标体系结构中不相交的处理器组），从而只需要子立方体内部或相邻子立方体之间的通信就可以实现重复修剪。从而大大降低了消息延迟和热点概率。在nCUBE2超立方体多计算机上实现上述重复修剪方案，以解决旅行商问题（TSP）。对于均匀分布的城际成本，我们的策略在1024个处理器上的加速比以前不删除任何重复的方法提高了13%到35%，比以前的纯哈希方案提高了13%到25%。对于正态分布的数据，相应的数字是135%和10到155%。最后，我们根据等效率度量分析了并行A*算法在k-ary n-cube网络上的可扩展性，并表明它们分别具有/spl Theta/(P log P)和/spl Theta/(Pkn/sup 2/)的等效率下界和上界。
For many applications of the A* algorithm, the state space is a graph rather than a tree. The implication of this for parallel A* algorithms is that different processors may perform significant duplicated work if interprocessor duplicates are not pruned. In this paper, we consider the problem of duplicate pruning in parallel A* graph-search algorithms implemented on distributed-memory machines. A commonly used method for duplicate pruning uses a hash function to associate with each distinct node of the search space a particular processor to which duplicate nodes arising in different processors are transmitted and thereby pruned. This approach has two major drawbacks. First, load balance is determined solely by the hash function. Second, node transmissions for duplicate pruning are global; this can lead to hot spots and slower message delivery. To overcome these problems, we propose two different duplicate pruning strategies: 1) To achieve good load balance, we decouple the task of duplicate pruning from load balancing, by using a hash function for the former and a load balancing scheme for the latter. 2) A novel search-space partitioning scheme that allocates disjoint parts of the search space to disjoint subcubes in a hypercube (or disjoint processor groups in the target architecture), so that duplicate pruning is achieved with only intrasubcube or adjacent intersubcube communication. Thus message latency and hot-spot probability are greatly reduced. The above duplicate pruning schemes were implemented on an nCUBE2 hypercube multicomputer to solve the Traveling Salesman Problem (TSP). For uniformly distributed intercity costs, our strategies yield a speedup improvement of 13 to 35 percent on 1,024-processors over previous methods that do not prune any duplicates, and 13 to 25 percent over the previous hashing-only scheme. For normally distributed data the corresponding figures are 135 percent and 10 to 155 percent. Finally, we analyze the scalability of our parallel A* algorithms on k-ary n-cube networks in terms of the isoefficiency metric, and show that they have isoefficiency lower and upper bounds of /spl Theta/(P log P) and /spl Theta/(Pkn/sup 2/), respectively.