|
\justifying The A* algorithm is an important research direction in the field of artificial intelligence. At the same time, Graphics processing unit (GPU) is also continuously applied in various research fields. Therefore, this paper proposes a parallel A* search algorithm based on multi-GPU, exploring the implementation of A* search algorithm on multi-GPU architecture, so that it can be efficiently executed. Due to the influence of GPU on-chip memory and computing power, when the data scale reaches a certain scale, A* search based on single GPU will occur performance bottlenecks which seriously affects execution efficiency. Based on the heterogeneous memory structure of the multi-GPU architecture, this paper designs different partitioning methods for the two data sets, such as grid graphs and sliding puzzles, commonly used in A* search, and uses a multi-priority queue to improve GPU parallelism. The method adopted in this paper has achieved good results in the problem of 8-connected graphs and sliding puzzles. Through a series of comparative experiments, this paper verifies the effectiveness of the proposed method and is superior to the current A* search methods. |
|
Keywords:Concurrency computation, A* search, Multi-GPU architecture, Partition strategy. |
|