面向大图子图匹配的多GPU编程模型

摘要：

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

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

所属期刊栏目：17

分类号：TP311(计算技术、计算机技术)

资助基金：国家自然科学基金;国家自然科学基金;国家自然科学基金;国家自然科学基金;中央高校基本科研业务费专项

在线出版日期：2023-07-18（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1576-1585