计算机科学与探索

作者：李岑浩, 崔鹏杰, 袁野, 王国仁

单位：1. 东北大学 计算机科学与工程学院，沈阳 1100002. 北京理工大学 计算机学院，北京 100081

关键词：图分析,多GPU,大图子图匹配,优先级调度,并行编程模型

子图匹配是复杂网络中进行数据挖掘的重要手段。近年来，基于图形处理器（GPU）的子图匹配算法已展现明显的速度优势。然而，由于大图数据的规模宏大以及子图匹配的大量中间结果，单块GPU的内存容量很快成为了处理大图子图匹配算法的主要瓶颈。因此，提出了一种面向大图子图匹配的多GPU编程模型。首先，提出了基于多GPU的子图匹配算法框架，实现了子图匹配算法在多GPU上的协同操作，解决了GPU大图子图匹配的图规模问题。其次，采用了一种基于查询图的动态调节技术来处理跨分区子图集，解决了图划分导致的跨分区子图匹配难题。最后，结合GPU单指令多线程（SIMT）架构特性，提出一种优先级调度策略保证GPU的内部负载均衡，并设计了共享内存的流水线机制优化多核并发的缓存争用。实验表明，多GPU编程模型能够在数十亿级别的数据集上得到正确的匹配结果，与最新的基于GPU的解决方案相比，该算法框架能够获得1.2~2.6倍的加速比。

来源：2023年第7期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2023年第7期