This paper is published in Volume-6, Issue-4, 2020
Area
Computer Science
Author
Ishaan Jaffer
Org/Univ
Carnegie Mellon University, Pittsburgh, Pennsylvania, India
Pub. Date
07 July, 2020
Paper ID
V6I4-1183
Publisher
Keywords
Parallel Computing, A* Search, Search Algorithms, High-Performance Computing, Multi-core, CPU, GPU, Speedup, Threading, Parallel A* Search

Citationsacebook

IEEE
Ishaan Jaffer. Parallel A* search on a multi-core CPU, International Journal of Advance Research, Ideas and Innovations in Technology, www.IJARIIT.com.

APA
Ishaan Jaffer (2020). Parallel A* search on a multi-core CPU. International Journal of Advance Research, Ideas and Innovations in Technology, 6(4) www.IJARIIT.com.

MLA
Ishaan Jaffer. "Parallel A* search on a multi-core CPU." International Journal of Advance Research, Ideas and Innovations in Technology 6.4 (2020). www.IJARIIT.com.

Abstract

Multi-core central processing units (CPU) and the graphics processing unit (GPU) have become popular parallel computing platforms in recent years [1]. The GPU platform is commonly adopted in the research community as it has been to be superior to the traditional CPU. Straightforward implementations of Parallel algorithms on a GPU can easily achieve a speedup of ten times or more over the sequential algorithms. However, achieving significant speedup on a multi-core CPU (over the sequential algorithm) requires intelligently designed and well-optimized algorithms [3]. This paper discusses a parallel implementation of A* search which achieved 6.67x Speedup with a search space of 106 nodes, 3.14x speedup with 107 nodes, and 137.67x speedup with 108 nodes when run on the eight-core, 3.0 GHz Intel Core i7 processor. This paper also analyses different work partitioning strategies and how the performance of the parallel A* search algorithm scales.
Paper PDF