(untitled) (International Journal of Engineering and Computer Science, 2017)
Parallel processing is adopted with the aim to run multiple independent program tasks simultaneously on multiple CPUs with the objective of minimizing the execution time of the whole program. In this research, parallel A* is implemented on a shared-memory multiprocessor system. Experimental results are compared with the sequential A* to find an optimum or near-optimum path between two points in a grid map. The most prominent drawback of the A* algorithm is the long execution time since it examines each of the neighbor nodes, beginning at the start node going through to the goal node. Therefore, having different threads running simultaneously to find the path from each neighbor of start node to goal node is expected to reduce the computation time dramatically. Different parameters are used to assess the performance of the parallel version of the A* algorithm; namely, the execution time, the speedup, the scalability, and the efficiency. The experiments are conducted with different number of threads. Interesting results are given with respect to the previously mentioned four metrics. Keywords: Parallel A*, Shared-memory multiprocessors, Path finding.