New parallel algorithm for recursive best first search on a GPU

Abstract

Parallel programming has emerged preeminence as an efficient paradigm for designing and solving complex problems. In recent years, the usage of Graphics Processing Units (GPUs) with parallel approaches has scaled up the computational speed of the traditional CPU-based algorithms. Therefore, developing a parallel adaptation of the fundamental algorithms has become essential to harness the advantages of modern multi-core processors. This thesis describes the first variant, which exploits parallelism from a well-known Artificial Intelligence (AI) searching algorithm (Recursive Best First Search, RBFS) using GPU. It proposes a methodology to convert a sequential RBFS algorithm to a parallel algorithm that provides enhanced solutions. Furthermore, the proposed algorithm has been studied thoroughly in centralized and distributed optimization contexts. The performance analysis on sliding puzzles illustrates the superiority gained by using GPU, resulting in excelled performances and scalability. The proposed parallel GPU-based RBFS can achieve significant computational speed-up for large-scale search problems compared to the traditional sequential CPU-based RBFS. Moreover, different approaches of GPU programming have been considered, showing the impact of using a na¨ıve framework (Aparapi) for Java based implementation and CUDA based implementation using Python. In addition, the proposed model will be effective in any non-GPU based parallel system as it is not solely focused to enhance performance on GPU based architecture.