• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
Advanced Search
Luan Hua, Zhou Mingquan, Fu Yan. Frequent Graph Mining on Multi-Core Processor[J]. Journal of Computer Research and Development, 2015, 52(12): 2844-2856. DOI: 10.7544/issn1000-1239.2015.20140598
Citation: Luan Hua, Zhou Mingquan, Fu Yan. Frequent Graph Mining on Multi-Core Processor[J]. Journal of Computer Research and Development, 2015, 52(12): 2844-2856. DOI: 10.7544/issn1000-1239.2015.20140598

Frequent Graph Mining on Multi-Core Processor

More Information
  • Published Date: November 30, 2015
  • 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.
  • Related Articles

    [1]Chen Zhiqiang, Zhou Hongwei, Feng Quanyou, Deng Rangyu. Design and Implementation of Configurable Cache Coherence Protocol for Multi-Core Processor[J]. Journal of Computer Research and Development, 2021, 58(6): 1166-1175. DOI: 10.7544/issn1000-1239.2021.20210174
    [2]Zhou Enqiang, Zhang Wei, Lu Yutong, Hou Hongjun, Dong Yong. A Cache Approach for Large Scale Data-Intensive Computing[J]. Journal of Computer Research and Development, 2015, 52(7): 1522-1530. DOI: 10.7544/issn1000-1239.2015.20148073
    [3]Wang Endong, Tang Shibin, Chen Jicheng, Wang Hongwei, Ni Fan, Zhao Yaqian. Directory Cache Design for Multi-Core Processor[J]. Journal of Computer Research and Development, 2015, 52(6): 1242-1253. DOI: 10.7544/issn1000-1239.2015.20150140
    [4]Zhang Suiyu, Han Jun, Lu Shiting, and Zeng Xiaoyang. Cache Based AES Attack Implementation and Its Theoretical Analysis[J]. Journal of Computer Research and Development, 2011, 48(6): 955-963.
    [5]Liu Yi, Zhang Xin, Li He, Qian Depei. A Heuristic Task Allocation Algorithm for Multi-Core Based Parallel Systems[J]. Journal of Computer Research and Development, 2009, 46(6): 1058-1064.
    [6]Chen Gang, Zhang Weiwen, and Wu Guoxin. Replacement Solutions for Streaming Cache on P2P Network[J]. Journal of Computer Research and Development, 2007, 44(11): 1857-1865.
    [7]Zhou Xuehai, Yu Jie, Li Xi, and Wand Zhigang. Research on Reliability Evaluation of Cache Based on Instruction Behavior[J]. Journal of Computer Research and Development, 2007, 44(4): 553-559.
    [8]Wu Jiajun, Feng Xiaobing, Zhang Zhaoqing. Data Prefetching Technique of Nonlinear Memory Access[J]. Journal of Computer Research and Development, 2007, 44(2): 355-360.
    [9]Huan Dandan, Li Zusong, Hu Weiwu, Liu Zhiyong. A Cache Adaptive Write Allocate Policy[J]. Journal of Computer Research and Development, 2007, 44(2): 348-354.
    [10]Yan Yuejin, Li Zhoujun, and Chen Huowang. A Depth-First Search Algorithm for Mining Maximal Frequent Itemsets[J]. Journal of Computer Research and Development, 2005, 42(3).

Catalog

    Article views (1171) PDF downloads (627) Cited by()

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return