Parallel multithreaded IDA* heuristic search: algorithm design and performance evaluation

Abstract

Due to the witnessed prevalence of the commercial multi-core microprocessors, parallel programming becomes a dire need for efficiently using all available hardware resources for one application. One of the parallel programming approaches is multithreading, which has been proved to play a great role in providing sequential computers with virtual parallelisation, yielding faster execution and easy communication. Such advantageous features are provided through creating a dynamic number of concurrent threads at run-time of an application. Based on these facts, this paper presents a parallel multithreaded approach for the well-known iterative deepening A* (IDA*) heuristic search algorithm using POSIX threads (Pthreads) and message-passing interface libraries running on 16 dual-core processors. The feasibility of the parallel multithreaded approach is investigated as an alternative for hosting applications requiring intensive graph search. The analytical evaluation and experimental results revealed the improved performance achieved by the proposed parallel multithreaded IDA* algorithm.

Keywords:

• heuristic search
• IDA* algorithm
• multithreaded IDA*
• parallel IDA*
• performance evaluation

Acknowledgements

The author would like to express his deep gratitude to the anonymous referees for their valuable comments and suggestions, which improved the paper.