-
题名面向大图子图匹配的多GPU编程模型
被引量：2
- 1
-
-
作者
李岑浩
崔鹏杰
袁野
王国仁
-
机构
东北大学计算机科学与工程学院
北京理工大学计算机学院
-
出处
《计算机科学与探索》
CSCD
北大核心
2023年第7期1576-1585,共10页
-
基金
国家自然科学基金(61932004,62002054,61732003,61729201)
中央高校基本科研业务费专项资金(N181605012)。
-
文摘
子图匹配是复杂网络中进行数据挖掘的重要手段。近年来,基于图形处理器(GPU)的子图匹配算法已展现明显的速度优势。然而,由于大图数据的规模宏大以及子图匹配的大量中间结果,单块GPU的内存容量很快成为了处理大图子图匹配算法的主要瓶颈。因此,提出了一种面向大图子图匹配的多GPU编程模型。首先,提出了基于多GPU的子图匹配算法框架,实现了子图匹配算法在多GPU上的协同操作,解决了GPU大图子图匹配的图规模问题。其次,采用了一种基于查询图的动态调节技术来处理跨分区子图集,解决了图划分导致的跨分区子图匹配难题。最后,结合GPU单指令多线程(SIMT)架构特性,提出一种优先级调度策略保证GPU的内部负载均衡,并设计了共享内存的流水线机制优化多核并发的缓存争用。实验表明,多GPU编程模型能够在数十亿级别的数据集上得到正确的匹配结果,与最新的基于GPU的解决方案相比,该算法框架能够获得1.2~2.6倍的加速比。
-
关键词
图分析
多GPU
大图子图匹配
优先级调度
并行编程模型
-
Keywords
graph analysis
multi-GPU
subgraph matching in large graphs
priority scheduling
concurrent programming model
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
