Massively Parallel A* Search on a GPU
Authors: Yichao Zhou, Jianyang Zeng
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Our experiments have demonstrated that the GPU-accelerated A* search is efficient in solving multiple real-world search tasks, including combinatorial optimization problems, pathfinding and game solving. Compared to the traditional sequential CPU-based A* implementation, our GPU-based A* algorithm can achieve a significant speedup by up to 45x on largescale search problems.5 Evaluation In this section, we compared the performance of our parallel GPU-based A* search algorithm against that of the traditional CPU-based sequential A* search algorithm. |
| Researcher Affiliation | Academia | Institute for Interdisciplinary Information Sciences Tsinghua University, Beijing, P. R. China |
| Pseudocode | Yes | Algorithm 1 describes the framework of our algorithm using parallel priority queues and Figure 1 provides the data flow of the open list. For each state s in the open list or closed list, s.node stands for the last node in the path represented by s, s.f and s.g store the values of f(s) and g(s), respectively, and s.prev stores the pointer to the previous state that expanded s, which is used to regenerate a path from a given state. |
| Open Source Code | No | Zhou, Y., and Zeng, J. 2014. Massively parallel A* search on a GPU: Appendix. Available at http://iiis.tsinghua.edu.cn/%7Ecompbio/papers/aaai2015apx.pdf. |
| Open Datasets | Yes | The heuristic function we used here is called the disjoint pattern database (Korf and Felner 2002)... |
| Dataset Splits | No | For 15-puzzles, the test data were randomly generated. For 24-puzzles, we manually created several test data sets by moving the tiles from the target state to control the number of steps below a current value so that both CPU- and GPU-based A* search algorithms can generate the optimal solutions within available memory for fair comparisons. |
| Hardware Specification | Yes | The CPU used in our experiments was Intel Xeon E5-1620 3.6GHz with 16GB global memory. The graphic card (GPU) that we used was a single NVIDIA Tesla K20c with 4.8GB off-chip global memory and 2496 CUDA cores. |
| Software Dependencies | No | Researchers from NVIDIA Corporation described an efficient GPU implementation for multi-agent A* search, i.e., finding the shortest paths between multiple pairs of nodes in parallel in a sparse graph, based on the CUDA programming environment (Bleiweiss 2008; Pan, Lauterbach, and Manocha 2010). |
| Experiment Setup | Yes | In these experiments, we evaluate GA* with different numbers of parallel priority queues, which were chosen to be multiple folds of the number of GPU cores to fully exploit the underlying thread-scheduling mechanism of a GPU platform. |