Parallel bidirectional heuristic search on the EM-4 multiprocessor

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.