A*搜索是人工智能领域中的一项重要研究方向。随着时间的推移和计算设备的进步，对于A*算法的优化也在不断进行。近些年来，图形处理单元(GPUs)已经被广泛的用于加速大规模的计算任务，例如机器学习等。这些应用主要是利用了GPU的并行化特点。当前也已经有相关的研究利用GPU的并行特点来加速A*算法，但是主要是在单GPU上进行执行。虽然单GPU相较于CPU上的执行效率可以实现较高的提升，但是由于设备内存以及计算性能的限制，导致了加速效果会出现瓶颈。同时，计算的数据规模也会受到相应的限制。
　　在本文中，为了解决当前单GPU上遇到的问题，本文提出了一种基于多GPU架构的A*搜索算法。首先关注于图数据的分区策略。具体来说，就是相较于单GPU的计算节点，多GPU架构下的计算节点存在多级的异构内存体系，因此，需要将图数据进行划分以适应这样的计算架构。文中针对网格图，有向图和排列组合类问题，采用了不同的分区方式以及通信方式，以使算法适应不同的数据类型。在数据分区之后，GPU设备将依据被分到的分区数据进行执行，并对open队列采用多个优先队列的方式来利用GPU的并行化特点，提升执行效率。同时，针对GPU中的重复结点查找问题，采用了ParallelHashingofReplacement的方法来解决。而面对可能存在的指数级别搜索空间导致的内存溢出问题，采用FrontierSearch的方式，牺牲算法的最优性来解决。本文的主要贡献如下：
　　(1)本文实现了一种基于多GPU的A*搜索算法。依据多GPU计算节点存在的异构内存情况，针对网格图，有向图和排列组合类问题分别提出了不同的分区和通信方式。
　　(2)针对A*搜索的运行特点，在GPU上采用了多个优先队列的方式来利用并行化特点，并针对GPU上可能出现的重复结点查找和内存溢出问题，分别采用了ParallelHashingofReplacement和FrontierSearch机制。
　　(3)本文使用了广泛的实验来验证算法性能，并且选取了A*算法常用的三种应用场景，用于展示算法的性能。正如实验展示的效果，相较于单GPU架构，在多GPU环境下，对大规模的计算任务可以实现不错的加速效果。例如，相较于当前基于单GPU的A*搜索算法，当GPU的设备数达到4时，可以实现最高2.5×的性能提升。