H-PBS: a hash-based scalable technique for parallel bidirectional search

We introduce a very simple and efficient hash-based algorithm for parallel bidirectional search. Hashing is used in a novel way to continuously provide every processor with a good cross section of the search front. This hashing serves multiple purposes of achieving load-balancing, selecting nodes for expansion, eliminating duplicate nodes, and detecting termination. Our asynchronous multiprocessor algorithm is shown to perform remarkably well, with linear or superlinear speedups, and scale well for large problem sizes and massive parallelism. The algorithm is architecture-independent and may be implemented on various distributed-memory multiprocessors. The performance is fairly independent of the communication latency, and takes advantage of a relatively fast communication throughput. We verify the performance of the proposed algorithm by using the popular 15-puzzle search problem and implementing it on an 80-processor distributed-memory multiprocessor, EM-4. We use hundred randomly generated problem instances of the 15-puzzle, with optimal path-lengths in the range 40-66. In spite of the limited memory capacity of this parallel machine, our implementation solves 99 of the problem instances, with solution path-lengths very close to optimal, speed-ups (in the number of nodes and execution times) close to linear, and in some cases superlinear, and on the average in 3-4 seconds.