Home > Papers

 
 
A Research of Parallel A* Search Method on Multi-GPU
YAO Yapeng,Jianhua Sun *,Jianhua Sun *
College of Computer Science and Electronic Engineering, Hunan University, Changsha 410082
*Correspondence author
#Submitted by
Subject:
Funding: National Natural Science Foundation of China(No.Grant No.61772183)
Opened online:19 May 2020
Accepted by: none
Citation: YAO Yapeng,Jianhua Sun,Jianhua Sun.A Research of Parallel A* Search Method on Multi-GPU[OL]. [19 May 2020] http://en.paper.edu.cn/en_releasepaper/content/4752062
 
 
\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.
 
 
 

For this paper

  • PDF (0B)
  • ● Revision 0   
  • ● Print this paper
  • ● Recommend this paper to a friend
  • ● Add to my favorite list

    Saved Papers

    Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags

Add yours

Related Papers

Statistics

PDF Downloaded 29
Bookmarked 0
Recommend 0
Comments Array
Submit your papers