A Research Of Parallel A* Search Method On Multi-GPU

A* search is an important research topic in the field of artificial intelligence.With the passage of time and the advancement of computing device,the optimization of the A* algorithm has also continued.In recent years,graphics processing units(GPUs)have been widely used to accelerate large-scale computing tasks,such as machine learning.These applications mainly utilize the parallelization feature of GPU.The current GPU has also been used to accelerate A* search in parallel,but it is mainly executed on a single GPU.Although the execution efficiency of a single GPU can be higher than that of the CPU,the acceleration effect of A* search will cause a bottleneck.,because of the limitations of the device memory and computing performance.At the same time,the calculated data size will be limited accordingly.In this paper,in order to solve the current problems encountered on a single GPU,we propose an A* search algorithm based on a multi-GPU architecture.First,we focus on the partitioning strategy of graph data.Specifically,compared to single GPU computing nodes,there are multi-level heterogeneous memory systems for computing nodes under the multi-GPU architecture.Therefore,graph data needs to be divided to adapt to such computing architecture.Such as grid graphs,directed graphs,and permutation and combination problems,different partitioning methods and communication methods are used to adapt the algorithm to different data types.After the data is partitioned,the GPU device will execute according to the partitioned data,and use multiple priority queues for the open list to take advantage of the parallelization feature of the GPU to improve execution efficiency.At the same time,the parallel hashing of replacement is used to solve the problem of detecting duplicate nodes in the GPU.In the face of possible memory overflow caused by the exponential search space,the frontier search method is used to solve the problem and sacrifices the optimality of the algorithm.The main contributions of this paper are as follows:(1)This paper implements an A* search algorithm based on multi-GPU.According to the memory heterogeneous condition of multi-GPU computing nodes,different partitioning and communication methods are proposed for grid graphs,directed graphs,and permutation and combination problems.(2)According to the running characteristics of A* search,multiple priority queues are used on the GPU to take advantage of the parallelization feature,and the detecting duplicate nodes and memory overflow problem that may occur on the GPU use the parallel hashing of replacement and frontier search mechanism respectively.(3)This paper uses extensive experiments to verify the performance of the algorithm.We have selected three common applications for the A* algorithm to demonstrate our algorithm performance.As the experiment shows,compared with the single GPU architecture,our algorithm can achieve a good acceleration effect for largescale computing tasks in a multi-GPU environment.For example,compared to the current A* search algorithm based on single GPU,when the number of GPU devices reaches 4,our algorithm can achieve up to 2.5 × performance improvement.