Parallel multithreaded IDA* heuristic search: algorithm design and performance evaluation
- 1 February 2011
- journal article
- research article
- Published by Taylor & Francis in International Journal of Parallel, Emergent and Distributed Systems
- Vol. 26 (1) , 61-82
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
This publication has 17 references indexed in Scilit:
- ISRL: intelligent search by reinforcement learning in unstructured peer-to-peer networksInternational Journal of Parallel, Emergent and Distributed Systems, 2008
- Threads cannot be implemented as a libraryACM SIGPLAN Notices, 2005
- Disjoint pattern database heuristicsArtificial Intelligence, 2002
- IMPROVED PARALLEL ALGORITHM FOR MAXIMAL MATCHING BASED ON DEPTH-FIRST-SEARCHParallel Algorithms and Applications, 2000
- Adaptive load balancing of irregular applications a case study: IDA* applied to the 15-puzzle problem1996
- BIDA∗: an improved perimeter search algorithmArtificial Intelligence, 1995
- A COST-OPTIMAL EREW BREADTH-FIRST ALGORITHM FOR ORDERED TREES, WITH APPLICATIONS∗Parallel Algorithms and Applications, 1995
- Single-agent parallel window searchIEEE Transactions on Pattern Analysis and Machine Intelligence, 1991
- Parallel depth first search. Part I. ImplementationInternational Journal of Parallel Programming, 1987
- Depth-first iterative-deepeningArtificial Intelligence, 1985