TMiner: A Vertex-Based Task Scheduling Architecture for Graph Pattern Mining

Graph pattern mining discovers important patterns in graphs. It is both computation-and memory-intensive, characterized by numerous set operations and irregular memory access. Graph pattern mining inherently involves a large number of independent tasks, helping to alleviate its computational bottleneck through parallel processing. However, after exploiting parallelism, memory access will become the primary bottleneck. Existing parallelism strategies severely result in redundant and inefficient memory access, making the performance memory bounded. This paper proposes TMiner, a graph pattern mining architecture with optimized memory performance through a systematically designed software-hardware stack. TMiner fundamentally reduces redundant memory access of parallel graph pattern mining in three aspects. (1) TMiner leverages a task partitioning approach based on disjoint neighbor vertex set access, reducing redundant memory access between PEs. (2) TMiner utilizes the global neighbor vertex information to coalesce the access from different neighbor vertex subsets at compilation time, which not only reduces redundant memory access within a task but also improves the data locality. (3) TMiner adopts a data reuse-oriented task scheduling mechanism, which dynamically migrates and merges tasks with similar memory access patterns, reducing redundant memory access within a PE at runtime. A DIMM-based near-memory architecture that exploits the DRAM's internal bandwidth is elaborated for high-performance graph pattern mining, which incorporates the proposed memory access optimization techniques and an extended ISA. Compared with the state-of-the-art software and hardware baselines, TMiner significantly improves the performance.