@inproceedings{42ae81960d4844689d4db716efacb3e9,
title = "Efficient parallel execution of IDA∗ on shared and distributed memory multiprocessors",
abstract = "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 behaviour - 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 utilisation. 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.",
author = "Saletore, {Vikram A.} and Kale, {L. V.}",
note = "Publisher Copyright: {\textcopyright} 1991 IEEE.; 6th Distributed Memory Computing Conference, DMCC 1991 ; Conference date: 28-04-1991 Through 01-05-1991",
year = "1991",
doi = "10.1109/DMCC.1991.633162",
language = "English (US)",
series = "6th Distributed Memory Computing Conference, DMCC 1991 - Proceedings",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "355--361",
editor = "Quentin Stout and Michael Wolfe",
booktitle = "6th Distributed Memory Computing Conference, DMCC 1991 - Proceedings",
address = "United States",
}