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

发布时间：2018-01-03 04:44

本文关键词：多核处理器上的频繁图挖掘方法　出处：《计算机研究与发展》2015年12期 　论文类型：期刊论文

【摘要】：多核处理器已经成为现代处理器的主流体系结构,频繁图挖掘(frequent graph mining)是一个具有很多应用领域的研究热点问题,充分利用多核处理器的能力加速频繁图挖掘过程具有研究意义和实用价值.提出一种基于深度优先遍历的并行挖掘模式,使用任务池维护工作负载,提高数据的时间局部性并减少大量的内存使用;设计缓存敏感的点边数组,连续排列线程的记录数据,减少原始图的数据量,降低缓存缺失率;为了减少锁的竞争,使用灵活的任务获取方法寻找工作任务,采用内存管理队列降低频繁的内存分配释放开销.在模拟数据和真实数据上进行了详细的实验研究和性能分析,结果表明提出的技术能够有效减少内存占用并降低缓存缺失,在具有12个核心的机器上可以达到10倍的加速比.
[Abstract]:The multi-core processor architecture has become the mainstream of modern processors, frequent graph mining (frequent graph mining) is a research hotspot in the field of application has many problems, the ability to make full use of multi-core processors to accelerate frequent graph mining process has research significance and practical value. Based on the depth first traversal of the parallel data mining model, task the pool maintenance work load, improve data locality and reduce the amount of time the memory cache design; sensitive point boundary array, consecutive record data of the thread, reducing the original map data, reduce the cache miss rate; in order to reduce the lock competition, using flexible task acquisition method in search of work tasks, the use of memory the queue management reduces the memory allocation overhead. Frequent release in simulated and real data analyses and experimental research of node in detail. The results show that the proposed technology can effectively reduce memory footprint and reduce cache loss, and can reach a speed ratio of 10 times on the 12 core machines.

【作者单位】：北京师范大学信息科学与技术学院;
【基金】：国家自然科学基金项目(61402041,41301402)
【分类号】：TP332
【正文快照】： 频繁图挖掘(frequent graph mining)是数据挖掘领域的一个基本问题,目的是要找到在图集合中频繁出现(支持度大于阈值)的子图,广泛应用在化学生物、社交网络、计算机视觉、金融交易等方面.例如在化学生物领域,图自然可以用来表示分子结构,图的顶点表示原子,边代表化学键,通过挖

【相似文献】