A SIMD approach to parallel heuristic search

Serial search algorithms often exhibit exponential run times and may require an exponential amount of storage as well. Thus, the design of parallel search algorithms with limited memory is of obvious interest. This paper presents an efficient SIMD parallel algorithm, called IDPS (for iterative-deepening parallel search). At a broad level IDPS is a parallel version of IDA∗. While generically we have called our algorithm an IDPS, performance of four variants of it has been studied through experiments conducted on the well-known test-bed problem for search algorithms, namely the Fifteen Puzzle.