Share Email Print

Proceedings Paper

SIMD approach to IDA* search
Author(s): Gary Lyons; Dianne J. Cook
Format Member Price Non-Member Price
PDF $17.00 $21.00

Paper Abstract

Heuristic search is a fundamental component of artificial intelligence applications. Because search routines are frequently a computational bottleneck, numerous methods have been explored to increase the efficiency of search. While sequential search methods use exponential amounts of storage and yield exponential run times, parallel algorithms designed for MIMD machines significantly reduce the time spent in search. In this paper, we present a massively- parallel SIMD approach to search named MIDA* search. The components of MIDA* include a very fast distribution algorithm which biases the search to one side of the tree, and an incrementally-deepening depth-first search of all the processors in parallel. We show the results of applying MIDA* to instances of the fifteen puzzle problem. Results reveal an efficiency of 76% and a speedup of 8553% and 492% over serial and 16- processor MIMD algorithms, respectively.

Paper Details

Date Published: 1 March 1992
PDF: 11 pages
Proc. SPIE 1707, Applications of Artificial Intelligence X: Knowledge-Based Systems, (1 March 1992); doi: 10.1117/12.56879
Show Author Affiliations
Gary Lyons, Univ. of South Florida (United States)
Dianne J. Cook, Univ. of South Florida (United States)

Published in SPIE Proceedings Vol. 1707:
Applications of Artificial Intelligence X: Knowledge-Based Systems
Gautam Biswas, Editor(s)

© SPIE. Terms of Use
Back to Top
Sign in to read the full article
Create a free SPIE account to get access to
premium articles and original research
Forgot your username?