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

Abstract: 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 a 10-fold speedup on a 12-core machine.

Key words: frequent graph mining, multi-core processor, cache, parallel techniques, depth-first search (DFS)