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

David Nassimi, Milind Joshi, Andrew Sohn

Research output: Contribution to journalConference articlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)414-421
Number of pages8
JournalIEEE Symposium on Parallel and Distributed Processing - Proceedings
StatePublished - Dec 1 1995
EventProceedings of the 1995 7th IEEE Symposium on Parallel and Distributed Processing - San Antonio, TX, USA
Duration: Oct 25 1995Oct 28 1995

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'H-PBS: a hash-based scalable technique for parallel bidirectional search'. Together they form a unique fingerprint.

Cite this