摘要
多核处理器已经成为现代处理器的主流体系结构,频繁图挖掘(frequent graph mining)是一个具有很多应用领域的研究热点问题,充分利用多核处理器的能力加速频繁图挖掘过程具有研究意义和实用价值.提出一种基于深度优先遍历的并行挖掘模式,使用任务池维护工作负载,提高数据的时间局部性并减少大量的内存使用;设计缓存敏感的点边数组,连续排列线程的记录数据,减少原始图的数据量,降低缓存缺失率;为了减少锁的竞争,使用灵活的任务获取方法寻找工作任务,采用内存管理队列降低频繁的内存分配释放开销.在模拟数据和真实数据上进行了详细的实验研究和性能分析,结果表明提出的技术能够有效减少内存占用并降低缓存缺失,在具有12个核心的机器上可以达到10倍的加速比.
Multi-core processors have become the mainstream of modern processor architecture.Frequent graph mining is a popular problem that has practical applications in many domains.Accelerating the mining process of frequent graphs by taking full advantage of multi-core processors has research significance and practical values.A parallel mining strategy based on depth-first search（DFS）is proposed and a task pool is used to maintain the workload.Compared with the method that utilizes breadth-first search,data temporal locality performance can be improved and a large amount of memory is saved.Cache conscious node-edge arrays in which record data of a thread are arranged continuously are designed to decrease the data size to represent original graphs and cache miss ratio.False sharing that severely degrades performance is mostly eliminated.In order to reduce lock contentions,a flexible method is explored to look for work tasks and memory management queues are utilized to reduce the overhead due to frequent memory allocation and free operations.A detailed performance study and analysis is conducted on both synthetic data and real data sets.The results show that the proposed techniques can efficiently lower memory usage and cache misses and achieve a10-fold speedup on a 12-core machine.
出处
《计算机研究与发展》
EI
CSCD
北大核心
2015年第12期2844-2856,共13页
Journal of Computer Research and Development
基金
国家自然科学基金项目(61402041
41301402)
关键词
频繁图挖掘
多核处理器
缓存
并行技术
深度优先遍历
frequent graph mining
multi-core processor
cache
parallel techniques
depth-first search（DFS）
