Halis: A Hardware-Software Co-Designed Near-Cache Accelerator for Graph Pattern Mining

Abstract

Graph Pattern Mining (GPM) algorithms extract meaningful information within graph structures, making them fundamental building blocks for multiple application domains. However, their performance is bottlenecked by hard-to-predict divergence control, cache pollution, and low parallelism caused by index matching operations that dominate the execution time. To address these challenges, this paper introduces Halis, a hardware-software co-designed Near-Cache Accelerator for GPM workloads on commercial multi-core CPUs. By executing index matching operations near the Last-Level Cache (LLC), Halis reduces data movement and cache pollution in upper cache levels while minimizing divergence control and enhancing parallelism. To achieve this, Halis repurposes underutilized Content Addressable Memories (CAMs) in hardware data prefetchers, taking advantage of their efficient lookup capabilities for GPM workloads. Furthermore, Halis includes virtual memory support, ensuring compatibility with commodity operating systems. Designed as a decoupled programmable accelerator, it operates via memory-mapped registers. Our evaluation demonstrates that Halis outperforms software and hardware approaches by 26.9x and 2.4x respectively, while incurring a negligible area overhead of 0.05% over the CPU baseline.