.png){kind=icon}
返回
Efficient parallel A* search on multi-GPU system
.png){kind=icon}
PRE
AI
DOI：10.1016/j.future.2021.04.011.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
A* search is a best-first search algorithm that is widely used in pathfinding and graph traversal. To meet the ever-increasing demand of performance, various high-performance architectures (e.g., multi-core CPU and GPU) have been explored to accelerate the A* search. However, the current GPU based A* search approaches are merely designed based on single-GPU architecture. Nowadays, the amount of data grows at an exponential rate, making it inefficient or even infeasible for the current A* to process the data sets entirely on a single GPU. In this paper, we propose DA*, a parallel A* search algorithm based on the multi-GPU architecture. DA* enables the efficient acceleration of the A* algorithm using multiple GPUs with effective graph partitioning and data communication strategies. To make the most of the parallelism of multi-GPU architecture, in the state extension phase, we adopt the method of multiple priority queues for the open list, which allows multiple states being calculated in parallel. In addition, we use the parallel hashing of replacement and frontier search mechanism to address node duplication detection and memory bottlenecks respectively. The evaluation shows that DA* is effective and efficient in accelerating A* based computational tasks on the multi-GPU system. Compared to the state-of-the-art A* search algorithm based on a single GPU, our algorithm can achieve up to 3x performance speedup with four GPUs. (C) 2021 Elsevier B.V. All rights reserved.
Keyword:
A* search
GPU
Multi-GPU
Graph partition
Parallelism
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
F
IF:
6.1
论文数:
6.9K
被引数:
2.3W
机构
引用论文
.png){kind=icon}
Does it take older adults longer than younger adults to perceptually segregate a speech target from a background masker?在感知上将语音目标与背景掩蔽器隔离开来是否需要老年人比年轻人更长的时间？
PREAI
分享收藏分享收藏GFlink: An In-Memory Computing Architecture on Heterogeneous CPU-GPU Clusters for Big DataGFlink: 面向大数据的cpu-gpu异构集群内存计算架构
PREAI
分享收藏
Performance Optimization Using Partitioned SpMV on GPUs and Multicore CPUs在gpu和多核cpu上使用分区SpMV进行性能优化
PREAI
分享收藏
查看更多内容