Parallel bidirectional A* search on a symmetry multiprocessor
Andrew Sohn · 2002
This report presents our experiences parallelizing and implementing search problems. We take the sequential A* search and parallelize it by combining with bidirectional search, called parallel bidirectional A* search (PBiA*S). To identify the effectiveness of the PBiA*S, we implement two search problems, the Eight Puzzle and the Tower of Hanoi, on a Symmetry multiprocessor. Execution results demonstrate that the PBiA*S can be an effective parallel search method as it gives two two 12-fold speedup over the unidirectional A* search for the two search problems.>