SCALABLE GLOBAL AND LOCAL HASHING STRATEGIES FOR DUPLICATE PRUNING INPARALLEL A-ASTERISK GRAPH SEARCH

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 conside r the problem of duplicate pruning in parallel A graph-search algorit hms implemented on distributed-memory machines. A commonly used method for duplicate pruning uses a hash function to associate with each dis tinct node of the search space a particular processor to which duplica te nodes arising in different processors are transmitted and thereby p runed. This approach has two major drawbacks. First, load balance is d etermined solely by the hash function. Second, node transmissions for duplicate pruning are global; this can lead to hot spots and slower me ssage delivery. To overcome these problems, we propose two different d uplicate pruning strategies: 1) To achieve good load balance, we decou ple 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 par ts of the search space to disjoint subcubes in a hypercube (or disjoin t processor groups in the target architecture), so that duplicate prun ing is achieved with only intrasubcube or adjacent intersubcube commun ication, Thus message latency and hot-spot probability are greatly red uced. The above duplicate pruning schemes were implemented on an nCUBE 2 hypercube multicomputer to solve the Traveling Salesman Problem [TSP ). For uniformly distributed intercity costs, our strategies yield a s peedup improvement of 13 to 35 percent on 1.024-processors over previo us methods that do not prune any duplicates, and 13 to 25 percent over the previous hashing-only scheme. For normally distributed data the c orresponding figures are 135 percent and 10 to 155 percent. Finally, w e analyze the scalability of our parallel A algorithms on k-ary n-cub e networks in terms of the isoefficiency metric, and show that they ha ve isoefficiency lower and upper bounds of -(P log P) and -(Pkn(2)), r espectively.