计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (12): 2844-2856.doi: 10.7544/issn1000-1239.2015.20140598
栾华,周明全,付艳
Luan Hua, Zhou Mingquan, Fu Yan
摘要: 多核处理器已经成为现代处理器的主流体系结构,频繁图挖掘(frequent graph mining)是一个具有很多应用领域的研究热点问题,充分利用多核处理器的能力加速频繁图挖掘过程具有研究意义和实用价值.提出一种基于深度优先遍历的并行挖掘模式,使用任务池维护工作负载,提高数据的时间局部性并减少大量的内存使用;设计缓存敏感的点边数组,连续排列线程的记录数据,减少原始图的数据量,降低缓存缺失率;为了减少锁的竞争,使用灵活的任务获取方法寻找工作任务,采用内存管理队列降低频繁的内存分配释放开销.在模拟数据和真实数据上进行了详细的实验研究和性能分析,结果表明提出的技术能够有效减少内存占用并降低缓存缺失,在具有12个核心的机器上可以达到10倍的加速比.
中图分类号: