REUSE: Recurrent Subgraph Exploitation for ReRAM-Accelerated Graph Processing

Graph accelerators have emerged as a promising solution for accelerating the processing of large-scale sparse graphs by leveraging the in-situ computation capabilities of ReRAM crossbars. However, existing designs incur substantial memristor access overhead due to the large number of graph partitions, increasing execution time and energy consumption while reducing circuit lifetime. This paper presents REUSE, a ReRAM-based graph accelerator that exploits recurring subgraph patterns to minimize memristor write operations. REUSE identifies frequent patterns and maps them to static graph engines whose crossbar configurations are preserved throughout execution, while less frequent patterns are assigned to dynamic engines at runtime. To support efficient mapping, REUSE employs a lightweight host-side processing scheme that operates directly on the graph's coordinate list, avoiding costly dense matrix reconstruction. Patterns are then distributed across multiple crossbars within each graph engine to balance the workload and maximize utilization. Furthermore, we develop analytical execution-time and energy models and use them to explore key architectural parameters, including the allocation of static and dynamic graph engines. REUSE is evaluated on diverse real-world graph datasets using BFS, SSSP, and PageRank, with BFS as the common workload for comparison against four state-of-the-art ReRAM-based accelerators. It achieves average speedups of 6.9 × over SparseMEM, 4.2 × over RPBFS, and 2.5 × over TARe, and improves on GraphR by 76 ×. The corresponding energy-delay product reductions are 7.5 ×, 70 ×, and 4.9 × against the same three designs, and approximately five orders of magnitude against GraphR. Circuit lifetime is extended by 2 × over SparseMEM and by two orders of magnitude over GraphR.