Efficient parallel execution of IDA on shared and distributed memory multiprocessors

Vikram A. Saletore, L. V. Kale

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publication6th Distributed Memory Computing Conference, DMCC 1991 - Proceedings
EditorsQuentin Stout, Michael Wolfe
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages355-361
Number of pages7
ISBN (Electronic)0818622903, 9780818622908
DOIs
StatePublished - 1991
Event6th Distributed Memory Computing Conference, DMCC 1991 - Portland, United States
Duration: Apr 28 1991May 1 1991

Publication series

Name6th Distributed Memory Computing Conference, DMCC 1991 - Proceedings

Conference

Conference6th Distributed Memory Computing Conference, DMCC 1991
CountryUnited States
CityPortland
Period4/28/915/1/91

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Software
  • Information Systems and Management

Fingerprint Dive into the research topics of 'Efficient parallel execution of IDA<sup>∗</sup> on shared and distributed memory multiprocessors'. Together they form a unique fingerprint.

Cite this