CRISP: Triangle Counting Acceleration via Content Addressable Memory-Integrated 3D-Stacked Memory

Triangle Counting is a fundamental problem in graph analysis, which usually needs to traverse the graph and perform set-intersections of neighbor sets. However, existing approaches suffer from heavy off-chip memory access and set-intersection overhead, which are both memory-bound and computation-bound. Fortunately, the emerging 3D-stacked computation-in-memory (CIM) architecture can reduce off-chip memory access, and the content addressable memory (CAM) can achieve parallel comparison. However, existing solutions have not effectively combined the high bandwidth of 3D-stacked memory with the high computational capabilities of CAM arrays. Besides, there exist many fruitless searches in the triangle counting process. Thus, we propose CRISP, a software-hardware co-design architecture to address these issues. At the level of software design, a new storage format named Two-Pointer CSR is proposed to eliminate fruitless searches during the set-intersection process. At the level of hardware design, CRISP integrates a novel Presence-Bits based Content Addressable Memory (PB-CAM) near the memory bank of 3D-stacked memory to fully exploit the high internal bandwidth. Through the presence bits comparison, the PB-CAM can effectively reduce both the off-chip memory access and set-intersection operations. Experimental results show that compared with previous state-of-the-art near-DIMM and HBM-PIM triangle counting accelerators, CRISP achieves speedups of 5.7× and 1.8 respectively.