Accelerating graph analysis by in-memory computing

Many of the systems we use every day can be understood through relationships. A social network connects people, a financial system connects accounts through transactions, and a map connects intersections through roads. Computer scientists represent these relationships as graphs: collections of items and the connections between them.

Graphs are everywhere, but they present a particular challenge for computers. The difficulty usually lies in locating the data needed for the next step rather than in the computation itself. As a graph algorithm proceeds, the processor must repeatedly look up the neighbors of one item after another. These connections are typically scattered throughout memory, forcing the processor to move large amounts of data back and forth. As graphs grow to billions of connections, this data movement becomes a major source of both execution time and energy consumption.

Our research explores a different approach: bringing the computation closer to the data by computing directly inside memory.

The accelerator uses resistive memory, a technology in which information is stored as electrical resistance. These cells are arranged in dense arrays that can be read in parallel, with simple processing logic placed directly beside them. Mapping graph data onto these arrays allows the accelerator to work on many connections at once instead of repeatedly transferring them between memory and a separate processor. The result is an architecture that spends far less time and energy moving data, and correspondingly more of it on useful work.

This approach is particularly promising for applications that rely on very large graphs. For example, financial institutions can use graph analysis to identify suspicious relationships between accounts and transactions, while recommendation systems can use connections between users, products, and content to identify relevant recommendations. Similar techniques are also being explored in areas such as drug discovery and traffic prediction, where understanding relationships between large numbers of entities is essential.

Making graph processing more efficient

Building an accelerator around in-memory computing is only part of the challenge. To make this approach practical for large graphs, we also need to consider how the graph reaches the memory arrays, how often the arrays need to be reconfigured, and how the hardware can scale.

One part of our work focuses on how graph data is stored and prepared. Real-world graphs are sparse: each item is connected to only a small fraction of the possible connections. Graphs are therefore commonly stored in a compact format that keeps only the connections that actually exist. Many existing accelerators convert this compact representation into a full table before processing it in memory arrays. This conversion requires additional processing and produces a table that is largely empty. Our design instead carries the compact representation directly from main memory into the accelerator, allowing the processing units to work with the graph in its original form and avoiding this conversion step.

Another part of our work takes advantage of a different property of real-world graphs: repetition. The same small patterns of connections can appear many times within a graph. We use this repetition to reduce how often the resistive memory needs to be written. Frequently occurring patterns can be configured once and reused whenever the same pattern appears again, while patterns that are less common are handled dynamically. We also recognize patterns that are structurally identical even when their individual items have different labels. This allows more graph segments to share the same hardware configuration, reducing the number of writes to the memory and improving both energy efficiency and memory lifetime.

Together, these techniques allow the accelerator to spend more time processing the graph and less time preparing or reconfiguring it. Across real-world graph datasets and standard workloads such as shortest-path analysis and PageRank, our designs demonstrate substantial improvements in both performance and energy efficiency compared with previous in-memory graph accelerators.

Scaling up and staying reliable

As we continue developing these accelerators, we are looking beyond a single processing unit to the challenges of building larger and more reliable systems.

One direction is communication. As an accelerator grows, more processing units need to exchange data with one another. At larger scales, the communication network connecting these units can become an important part of the overall performance. We are exploring optical interconnects as a potential way to provide fast communication while keeping the cost and energy of data movement under control.

Another direction is reliability. Resistive memory cells can gradually change their stored values and may eventually fail after repeated use. This is particularly important for accelerators that rely on the memory arrays for computation. We are investigating hardware techniques that can detect and compensate for such faults, helping the accelerator continue to operate correctly as the memory ages.

These projects cover different stages of the same challenge: making graph processing more efficient from the moment the data enters the accelerator to the point where the computation is completed. By improving how graphs are represented, stored, processed, and communicated, and by making the underlying memory more resilient, we are working toward graph accelerators that can scale to larger workloads while remaining fast, energy-efficient, and reliable.

This work is carried out at LECS by Masoud Rahimi, supervised by Prof. Sébastien Le Beux.

Comments & corrections

If you have questions about this note, or you spot something we got wrong, please write to the author directly. We post addenda to articles when a correction is warranted.