Accelerating Graph Connected Component Computation with Emerging Processing-In-Memory Architecture

Abstract

Computing the connected component of a graph is a basic graph computing problem, which has numerous applications like graph partitioning and pattern recognition. Existing methods for computing connected component suffer from memory wall problem because of the frequent data transmission between CPU and memory. To overcome this challenge, in this paper, we propose to accelerate connected component computation with the emerging processing-in-Memory (PIM) architecture through an algorithm-architecture co-design manner. The innovation lies in computing connected component with bitwise logical operations (such as AND and OR), and the customized data flow management methods to accelerate computation and reduce energy consumption. As a proof-of-concept, experimental results with computational Spin-Transfer Torque Magnetic RAM (STT-MRAM) arrays demonstrate on average 19.8× and 12.4× speedups compared with the CPU and GPU implementations, and a 35.4× energy efficiency improvement over the CPU implementation. Moreover, we investigate the potential associations between graph computing and bitwise Boolean logic, which could help design more general in-memory graph computing accelerators in the future.