Live Webcast 15th Annual Charm++ Workshop

Iterative Deepening A* (IDA*) is an algorithm for finding an optimal solution to state-space search problems in a memory efficient manner. Previous schemes for parallel execution of IDA* exhibit anomalous behavior - i.e. multiple runs of the algorithm for the same problem instance may produce speedups widely varying between sublinear and superlinear; moreover, addition of processors may lead to a slowdown. Further, IDA*'s multiple iterations cause the parallelism to increase and decrease in waves, leading to low processor utilization. In this paper we present techniques that effectively parallelize IDA* so as to produce consistent and monotonically increasing speedups with the addition of processors. The techniques employ a combination of scheduling strategies based on bit-vector priorities. A secondary advantage of our scheme is its memory usage is not proportional to the number of processors, unlike the previous schemes. Performance data obtained on shared and distributed memory multiprocessors show that we achieve our objectives.