Parallel bidirectional heuristic search on the EM-4 multiprocessor

Andrew Sohn, Mitsuhisa Sato, Shuichi Sakai, Yuetsu Kodama, Yoshinori Yamaguchi

Research output: Contribution to journalConference articlepeer-review

1 Scopus citations


Solving search problems takes a large amount of computational resources both in terms of execution time and memory usage. This report presents experimental results of Parallel Bidirectional Heuristic Search (PBiHS) on the 80-processor EM-4 multithreaded data-flow multiprocessor. The PBiHS searches from two directions in parallel while search in each direction is also performed in parallel. Important data structures are distributed to all processors to help reduce the execution time of realistic problem sizes down to a few seconds or less. We implement two search problems, the Eight Puzzle and the Tower of Hanoi, and execute on the target multiprocessor. Execution results demonstrate that the Parallel Bidirectional Heuristic Search, (1) can solve the tree depth 20-40 of the Eight-Puzzle and the 3-9 disks of the Tower of Hanoi in an optimal or near optimal number of iterations in less than two seconds, (2) is highly scalable as it gives over 40-fold speedup on 80 processors, and (3) yields on the average 10-fold improvement over unidirectional search for the 8-Puzzle while generating a far less number of nodes.

Original languageEnglish (US)
Pages (from-to)100-107
Number of pages8
JournalIEEE Symposium on Parallel and Distributed Processing - Proceedings
StatePublished - 1994
EventProceeedings of the 6th IEEE Symposium on Parallel and Distributed Processing - Dallas, TX, USA
Duration: Oct 26 1994Oct 29 1994

All Science Journal Classification (ASJC) codes

  • General Engineering


Dive into the research topics of 'Parallel bidirectional heuristic search on the EM-4 multiprocessor'. Together they form a unique fingerprint.

Cite this