CoGraf: Fully Accelerating Graph Applications with Fine-Grained PIM

Processing-in-memory (PIM) puts compute inside DRAM to exploit its huge internal bandwidth, and fine-grained PIM (FGPIM) does so with standard DRAM commands so it works in real systems — but it only runs well on regular, sequential accesses, while graph algorithms chase edges to arbitrary vertices, an irregular pattern that forces costly DRAM row activations and needs conditional updates that clash with FGPIM's lockstep execution; this paper (Uppsala University and Huawei — Ali Semi Yenimol, David Black-Schaffer, and colleagues) presents CoGraf, the first FGPIM design to fully accelerate push-based graph applications by fixing both phases — a tuple-based cache that coalesces scattered updates plus multi-column instructions for the update phase, and bank-parallel predicated instructions for the conditional apply phase — reaching 4.4 to 9.8 times the speed of a non-PIM baseline while cutting DRAM energy by up to 94 percent.

The argument in one glance

Problem

Compute-in-memory is fast, but only for regular accesses — and graphs are irregular

Processing-in-memory (PIM) places compute units inside or next to DRAM so it can use the memory's enormous internal bandwidth and parallelism, instead of dragging data across the system to the CPU. A practical style, fine-grained PIM (FGPIM), uses the same commands and timing as standard DRAM, so it works with existing memory controllers: to process data, a normal DRAM row-activation command opens a row (1 to 8 kilobytes), and then an FGPIM command processes many 64-byte columns of that row in parallel, across many banks at once. This is wonderfully efficient — but only when the accesses are regular, marching sequentially through memory. Graph applications are the opposite. A graph algorithm follows edges from one vertex to arbitrary others, so its memory accesses are irregular and scattered. On FGPIM, that irregularity is expensive: each scattered access tends to open a fresh DRAM row, and row activations are costly, so the machinery meant to exploit bandwidth instead thrashes. Worse, vertex-centric push-based graph algorithms have two phases — an update phase that scatters updates along edges, and an apply phase that conditionally combines them — and the apply phase's conditional, per-vertex logic clashes with the lockstep, all-lanes-do-the-same execution that FGPIM relies on. So graphs, a hugely important workload, map poorly onto PIM.
What people did

Run graphs on PIM naively, or accelerate only one phase

The straightforward approaches fall short. One is to run graph algorithms on FGPIM as-is, issuing the irregular updates directly to memory. Another is to accelerate part of the computation — typically the update phase, where the bulk of the scattered traffic is — with PIM support, while leaving the rest to run conventionally.
Why it fell short

Irregular updates thrash DRAM, and the conditional apply phase resists parallel PIM

Running graphs naively on FGPIM squanders its advantage: because each irregular update opens a new DRAM row, the design pays a storm of expensive row activations and never reaches the bandwidth PIM promises. Accelerating only the update phase does not finish the job either, for two reasons. First, even the update phase needs help beyond raw PIM — the scattered updates must be grouped so they can be written together, or the row activations remain crippling. Second, and crucially, once the update phase is sped up, the apply phase becomes the new bottleneck, and the apply phase is hard for PIM precisely because it is conditional: only some vertices are updated, based on a per-vertex test, which does not fit the uniform, every-lane-the-same execution of FGPIM's parallel units. Because different graphs have different edge-to-vertex ratios, some are dominated by the update phase and others by the apply phase, so a partial solution that accelerates only one leaves large gains on the table. What is missing is a design that makes both the irregular update phase and the conditional apply phase run well on fine-grained PIM.
This paper's idea

Coalesce the scattered updates and predicate the conditional applies

CoGraf is the first fine-grained PIM design to fully accelerate vertex-centric push-based graph applications by accelerating both the update and the apply phase. For the update phase, it attacks the row-activation storm in two coordinated ways. It adds a tuple-based last-level cache (LLC) that can coalesce graph updates at different granularities — grouping updates destined for the same region so they are written to DRAM together instead of one scattered access at a time — and it introduces multi-DRAM-column-processing FGPIM instructions so that the coalesced group matches the row-level parallelism of the FGPIM, processing many columns per activation. Choosing the optimal coalescing granularity cuts DRAM row activations dramatically (around 93 percent), turning irregular scatter into efficient bulk writes. Once the update phase is fast, the apply phase becomes the bottleneck, so CoGraf accelerates it too: it proposes bank-parallel FGPIM instructions with predicates, where a predicate mask lets the parallel PIM units apply an update to a vertex only when its condition holds, so the conditional apply runs across many banks in parallel despite being data-dependent. Together these make both phases efficient on PIM. On push-based graph applications, CoGraf achieves an average region-of-interest speedup of 1.8 to 3 times over naive FGPIM and 4.4 to 9.8 times over a state-of-the-art non-PIM baseline (against high-bandwidth memory and DDR4 respectively), while reducing DRAM energy by 67 to 86 percent and 88 to 94 percent.

Why this problem is worth solving

Graph analytics is a workload where moving data, not computing, is the cost, which makes it a prime target for processing-in-memory — if only its irregularity could be tamed.

Many important workloads spend most of their time and energy not on arithmetic but on shuttling data between memory and the processor. Graph analytics is a classic example: for each vertex you touch, you read its neighbors and their values, which are tiny computations over huge amounts of scattered data. Processing-in-memory attacks this by putting compute inside or beside the DRAM, so the data is processed where it lives, exploiting the memory’s vast internal bandwidth and the parallelism of its many banks rather than funneling everything through a narrow external bus. The obstacle to PIM has always been practicality: exotic designs that require redesigning DRAM struggle to reach industry. Fine-grained PIM sidesteps this by using standard DRAM commands and timing — a normal row activation opens a row, and a PIM command then processes many 64-byte columns of it in parallel across banks — so it slots into existing memory controllers. This makes it a realistic path to PIM’s benefits, and it is extremely efficient for regular access streams. The catch is that its efficiency assumes regularity: it wins by processing lots of nicely-laid-out data per row activation. When the access pattern is irregular, that assumption breaks, which is exactly the situation for graphs. So making irregular graph workloads run well on this practical form of PIM would unlock large speed and energy gains on a workload that badly needs them.

The difficulty is that a graph algorithm stresses PIM in two different ways, and fixing one exposes the other.

Vertex-centric push-based graph algorithms proceed in two phases. In the update phase, each active vertex pushes a value along each of its outgoing edges to its neighbors, generating a scatter of updates to arbitrary memory locations. In the apply phase, each vertex sums the updates it received and conditionally updates its own state — conditionally, because typically only vertices that actually changed, or that pass some test, do work. Each phase is hostile to fine-grained PIM for a different reason. The update phase is irregular: because neighbors are scattered across memory, each update tends to force a new DRAM row activation, and row activations are among the most expensive DRAM operations, so the scatter drowns the design in activation cost rather than exploiting bandwidth. The apply phase is conditional: PIM’s processing units are parallel and lockstep, doing the same operation across many columns and banps at once, which is efficient for uniform work but awkward for per-vertex conditional updates where different vertices should do different things. And which phase dominates depends on the graph: dense graphs with many edges per vertex spend more in the update phase, sparse ones more in the apply phase. So any solution that fixes only one phase leaves the other as a bottleneck, and only accelerating both — the irregular scatter and the conditional combine — actually makes graph applications fast on PIM.

What people did before, and where it broke

Run graph algorithms on fine-grained PIM as-is. Issue the irregular updates directly to the PIM-enabled DRAM. Where it broke. Each scattered update opens a new DRAM row, so the design pays a storm of expensive row activations and never reaches the bandwidth PIM is supposed to deliver.
Accelerate only the update phase. Add PIM support for the scatter-heavy update phase and leave the rest conventional. Where it broke. Once the update phase is faster, the apply phase becomes the new bottleneck, so overall speedup is capped; and different graphs bottleneck on different phases, so a partial fix helps unevenly.
Use PIM without grouping the updates. Rely on raw PIM bandwidth for the update phase without coalescing. Where it broke. The scattered updates still trigger per-access row activations; without grouping them, the row-activation cost dominates.
Force conditional applies into lockstep PIM. Run the per-vertex conditional apply on PIM’s uniform parallel units. Where it broke. The apply phase is data-dependent — only some vertices update — which does not fit the every-lane-the-same execution model, so it runs inefficiently.
The gap. No fine-grained PIM design accelerated both the irregular update phase and the conditional apply phase of push-based graph applications, so PIM could not fully accelerate them.

How CoGraf works

Making both graph phases efficient on fine-grained PIM

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Bring the computation into memory, and make an irregular workload fit it. CoGraf’s premise is processing-in-memory: compute where the data lives to exploit DRAM bandwidth, and its whole contribution is bending an irregular workload to fit that model. Taking a hard, previously-unsupported workload and extending commodity DRAM processing-in-memory to handle it is the same undertaking the work on expanding the applicability of commodity DRAM processing-in-memory for deep learning covered elsewhere on this site pursues, widening what practical PIM can accelerate. CoGraf does this for graph applications, whose irregular, conditional structure had kept them off fine-grained PIM.

Tame irregular graph traversals by reorganizing their accesses. The update phase is hard because following edges produces scattered accesses; CoGraf’s answer is to coalesce those updates so the irregular scatter becomes efficient bulk writes. Restructuring the irregular memory accesses of a graph traversal so they align with what the hardware handles efficiently is the same principle the work on taming misaligned graph traversals in concurrent graph processing covered elsewhere on this site is built on, reshaping irregular graph accesses to reduce their cost. CoGraf reshapes them at the last-level cache and matches them to the PIM’s row-level parallelism.

Coalesce sparse, scattered work to match the hardware’s access granularity. At the heart of the update-phase fix is choosing the right granularity to group scattered updates, so each DRAM row activation does maximal useful work instead of servicing one stray access. Orchestrating sparse, irregular data accesses at a carefully chosen granularity so the hardware’s wide accesses are used fully, rather than wasted on scattered elements, is the same idea the work on accelerating sparse data orchestration via dynamic reflexive tiling covered elsewhere on this site develops, tuning the access granularity to the data. CoGraf applies this to graph updates and a DRAM row’s structure, which is why its coalescing cuts row activations so sharply.

Following a graph iteration through CoGraf

Running one push-based iteration on fine-grained PIM

A trace, drawn from the paper, of how CoGraf accelerates both phases of a graph iteration.

Step 1 of 5

The update phase scatters updates along edges

Each active vertex pushes a value to each of its neighbors. Because neighbors are scattered across memory, these are irregular writes; on naive PIM, each would open a fresh, costly DRAM row.

This scatter is where naive fine-grained PIM drowns in row activations.

Why it works

Coalescing turns scatter into bulk writes. Irregular updates each open a costly DRAM row → but grouping updates to the same region in a tuple-based cache lets them be written together → so the number of expensive row activations drops sharply (about 93 percent).
Matching coalescing to row parallelism uses PIM bandwidth. A coalesced group only helps if the PIM can consume it at once → but multi-column instructions process many columns per activation → so the group maps onto the row-level parallelism and the update phase runs at PIM speed.
Fixing the update phase reveals, and then needs, the apply phase. Once updates are cheap, the conditional apply dominates → so a complete solution must also accelerate it → and CoGraf does, rather than stopping at a partial win.
Predicates make conditional work fit lockstep PIM. The apply is data-dependent, which clashes with uniform parallel execution → but a predicate mask enables only the lanes whose vertex meets the condition → so the conditional apply runs bank-parallel instead of serially.
Accelerating both phases pays off across graph types. Dense graphs bottleneck on updates, sparse ones on applies → so accelerating only one helps unevenly → but doing both yields large, consistent gains (up to 9.8 times over a non-PIM baseline) and big energy savings.

What it costs (trade-offs and scope)

It adds hardware to the cache and the PIM instruction set. CoGraf requires a tuple-based last-level cache that can coalesce at multiple granularities, plus new multi-column and bank-parallel predicated FGPIM instructions; these are real additions to the cache and memory subsystem, not a software-only change.
The coalescing granularity must be chosen well. The row-activation savings come from picking the optimal coalescing granularity for the workload; too coarse or too fine a choice would leave benefit on the table, so the design depends on getting that tuning right.
It targets vertex-centric push-based graph applications on FGPIM. The design is built around the push-based update-and-apply structure and the fine-grained PIM model; other graph paradigms (for example pull-based), other PIM styles, or non-graph irregular workloads would need their own adaptation.
Gains depend on the graph and the baseline. The reported speedups (1.8 to 3 times over naive FGPIM, 4.4 to 9.8 times over a non-PIM baseline) and energy savings vary with the memory technology compared against (high-bandwidth memory versus DDR4) and with graph structure, since edge-to-vertex ratio shifts which phase dominates.
PIM still faces practical adoption hurdles. Fine-grained PIM is designed to be compatible with standard DRAM interfaces, which helps, but processing-in-memory as a whole must still clear manufacturing and integration barriers before such gains are realized in shipping systems.

The evaluation

Running push-based graph applications in memory

Property	Non-PIM baseline	Naive fine-grained PIM	CoGraf
Update phase (irregular scatter)
Apply phase (conditional combine)
DRAM row activations
Speedup (region of interest)
DRAM energy

A comparison of running push-based graph applications. CoGraf is the first fine-grained PIM design to accelerate both the update phase (via tuple-based cache coalescing and multi-column instructions) and the conditional apply phase (via bank-parallel predicated instructions), reaching 1.8 to 3 times over naive FGPIM and 4.4 to 9.8 times over a non-PIM baseline (versus HBM2 and DDR4), with DRAM energy reduced by 67 to 94 percent.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s full text (the authors’ repository copy of the ASPLOS 2026 paper). The mechanism described is the paper’s: CoGraf is the first fine-grained PIM (FGPIM) design to fully accelerate vertex-centric push-based graph applications by accelerating both the update phase (computing vertex updates) and the apply phase (summing up the updates). For the update phase, it uses a tuple-based last-level cache that can coalesce graph updates at different granularities and multi-DRAM-column-processing FGPIM instructions to match the cache coalescing to the FGPIM’s row-level parallelism, with optimal-granularity coalescing reducing DRAM row activations substantially (around 93 percent). Once the update phase is accelerated, the apply phase becomes the bottleneck, so CoGraf adds bank-parallel FGPIM instructions with predicates to accelerate the conditional updates. The paper reports an average region-of-interest speedup of 1.8 times / 3 times over naive FGPIM and 4.4 times / 9.8 times over a state-of-the-art non-PIM baseline (against HBM2 and DDR4 respectively), and DRAM energy reductions of 67 percent / 86 percent and 88 percent / 94 percent, arguing for the importance of accelerating both phases. Exact microarchitecture, the coalescing and predication details, the benchmarks, and full results should be read from the paper.

Background

Why irregular workloads keep testing the limits of near-memory computing

It helps to see CoGraf within a long effort to bring computation to the data. The gap between how fast processors can compute and how fast memory can feed them has widened for decades, so a large fraction of a modern system’s time and energy goes into moving data rather than transforming it. Processing-in-memory and its near-memory relatives answer this by computing where the data lives, and they shine on workloads that stream through memory regularly, like dense linear algebra. The persistent hard case is irregularity: graphs, sparse matrices, and pointer-chasing structures scatter their accesses unpredictably, which is exactly where memory bandwidth is most precious and hardest to use well, because irregular accesses waste the wide, aligned transfers that memory and PIM are built around. Progress on these workloads has therefore come from cleverly reorganizing the accesses — grouping, coalescing, and matching them to the hardware’s natural granularity — and from making the hardware flexible enough to handle data-dependent, conditional work. The broader movement to push computation toward the data to overcome the data-movement wall is the same terrain the work on exploiting near-data processing for scalable inference covered elsewhere on this site occupies, keeping compute close to the memory that feeds it. CoGraf shows that with the right cache coalescing and predicated instructions, even the notoriously irregular and conditional structure of graph algorithms can be made to run efficiently on practical, standard-interface processing-in-memory.

If you remember only three things

1. Processing-in-memory (PIM) computes inside DRAM to exploit its internal bandwidth, and fine-grained PIM (FGPIM) stays practical by using standard DRAM commands — a row activation opens a row, then a PIM command processes many 64-byte columns in parallel. But it is efficient only for regular accesses. Graph applications follow edges to arbitrary vertices, so their irregular accesses each open a costly DRAM row, and their vertex-centric push-based form has two phases (an irregular update phase and a conditional apply phase) that clash with PIM's lockstep parallel execution, so prior PIM approaches accelerated graphs only partially.
2. CoGraf is the first FGPIM design to fully accelerate both phases. For the update phase it adds a tuple-based last-level cache that coalesces scattered updates at a chosen granularity, plus multi-DRAM-column-processing instructions that match the coalesced group to the PIM's row-level parallelism — cutting DRAM row activations by about 93 percent. Once updates are fast, the conditional apply phase becomes the bottleneck, so CoGraf adds bank-parallel FGPIM instructions with predicates, where a mask lets each lane apply an update only when its vertex's condition holds, running the data-dependent apply in parallel.
3. On push-based graph applications, CoGraf reaches an average region-of-interest speedup of 1.8 to 3 times over naive FGPIM and 4.4 to 9.8 times over a state-of-the-art non-PIM baseline (versus high-bandwidth memory and DDR4), cutting DRAM energy by 67 to 94 percent — showing the importance of accelerating both phases, since dense graphs bottleneck on updates and sparse ones on applies. The trade-offs: it adds cache and PIM-instruction hardware, depends on choosing the coalescing granularity well, and targets vertex-centric push-based graphs on FGPIM.

Check yourself

Check your understanding

1. Why do graph applications run poorly on fine-grained processing-in-memory?
2. How does CoGraf accelerate the update phase?
3. After the update phase is accelerated, what becomes the bottleneck, and how does CoGraf handle it?
4. Predict: two graphs are processed — one very dense (many edges per vertex) and one very sparse (few edges per vertex). Why does the paper argue a complete solution must accelerate both phases?

Sources

The paper is “CoGraf: Fully Accelerating Graph Applications with Fine-Grained PIM” by Ali Semi Yenimol, Anirban Nag, Chang Hyun Park, and David Black-Schaffer (Uppsala University and Huawei Technologies), published at ASPLOS 2026, DOI 10.1145/3779212.3790142. It is licensed CC BY.

This explainer is written from the paper’s full text (the authors’ repository copy). Processing-in-memory (PIM) delivers high performance by using internal DRAM bandwidth and parallelism, but graph applications are hard to adapt to PIM due to their irregular access patterns. CoGraf is the first fine-grained PIM (FGPIM) design that fully accelerates vertex-centric push-based graph applications by accelerating both their update (computing vertex updates) and apply (summing up the updates) phases. For the update phase, it designs a tuple-based last-level cache that can coalesce at different granularities to group graph updates together, and proposes multi-DRAM-column-processing FGPIM instructions to match the cache coalescing to the row-level parallelism of the FGPIM, with the optimal coalescing granularity reducing DRAM row activations substantially (around 93 percent). With this acceleration, the apply phase becomes the bottleneck, so CoGraf proposes bank-parallel FGPIM instructions with predicates to allow FGPIM to accelerate the conditional updates as well. It achieves an average region-of-interest speedup of 1.8 times / 3 times compared to naive FGPIM and 4.4 times / 9.8 times compared to a state-of-the-art non-PIM baseline (against HBM2 and DDR4 respectively), and DRAM energy reductions of 67 percent / 86 percent and 88 percent / 94 percent, demonstrating the importance of a complete solution that accelerates both phases. No numbers beyond the paper’s own have been introduced; exact microarchitecture, mechanism details, and full results should be confirmed in the paper.