Graph Canonization for Efficient Pattern Reuse in ReRAM-Based Graph Accelerators

Graph accelerators have emerged as a promising solution for processing large-scale sparse graphs by leveraging in-situ computation in ReRAM-based crossbars to improve computational efficiency. However, existing pattern-based designs suffer from exponential growth in unique subgraph patterns as crossbar size increases, severely limiting static engine utilization and overall system performance. This paper proposes a method that enables efficient pattern reuse in crossbar-based graph accelerators through two key contributions. First, we propose a degree-aware reordering algorithm that reduces the number of subgraphs for large crossbars. Second, we introduce a canonical pattern normalization algorithm that transforms subgraph patterns into canonical forms, minimizing the number of distinct patterns. Experimental results on representative real-world graphs demonstrate up to 9.4× speedup over a state-of-the-art pattern-based ReRAM accelerator.