多核处理器上的频繁图挖掘方法

摘要：

多核处理器已经成为现代处理器的主流体系结构，频繁图挖掘（frequent graph mining ）是一个具有很多应用领域的研究热点问题，充分利用多核处理器的能力加速频繁图挖掘过程具有研究意义和实用价值。提出一种基于深度优先遍历的并行挖掘模式，使用任务池维护工作负载，提高数据的时间局部性并减少大量的内存使用；设计缓存敏感的点边数组，连续排列线程的记录数据，减少原始图的数据量，降低缓存缺失率；为了减少锁的竞争，使用灵活的任务获取方法寻找工作任务，采用内存管理队列降低频繁的内存分配释放开销。在模拟数据和真实数据上进行了详细的实验研究和性能分析，结果表明提出的技术能够有效减少内存占用并降低缓存缺失，在具有12个核心的机器上可以达到10倍的加速比。

关键词：频繁图挖掘、多核处理器、缓存、并行技术、深度优先遍历

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

资助基金：国家自然科学基金项目61402041，41301402

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

页数：共13页

页码：2844-2856