Grafu: Unleashing the Full Potential of Future Value Computation for Out-of-core Synchronous Graph Processing

When a graph is too big for memory, processing it means streaming the edges off disk once per iteration, and the disk is the bottleneck — so there is a trick where you notice that a vertex whose incoming edges have all been processed already knows its next-iteration value, letting you do next iteration's work on edges you have in hand and skip them later; Grafu (Chinese University of Hong Kong with UT Dallas) points out that the previous system captured only about a third of the possible saving, and that simply alternating the direction you sweep the graph on every other pass captures nearly all of it, because the edges you could not do going forward are exactly the ones you can do coming back.

Why this problem is worth solving

The economics here are what make out-of-core processing interesting rather than merely a fallback.

What makes the saving possible is a rule that looks like a restriction.

What people did before, and where it broke

• Stream the edges once per iteration and accept the cost. The baseline system this work extends partitions vertices into ranges and edges into a grid indexed by source and destination range, then processes the grid column by column. It is efficient and supports skipping chunks that contain no active edges. Where it broke. Every iteration reads every active edge again, and nothing is reused across iterations.
• Work ahead, but give up the lockstep guarantee. Several systems get large savings by letting each vertex use the newest value available rather than the previous round’s. Where it broke. That only works for algorithms whose values move monotonically, such as shortest paths. Algorithms like PageRank genuinely require the round-by-round guarantee, and giving it up also makes an algorithm’s behaviour much harder for a user to analyse.
• Work ahead while keeping the guarantee, and reorder the graph to get more of it. The system this paper is really arguing with does exactly this, and adds a reordering that renumbers vertices to increase the number of edges eligible for the trick. Where it broke. Three ways, all measured. The traffic saving reaches 34.4% against a ceiling of 50%. The reordering has no effect at all on undirected graphs, because it sorts vertices by the ratio of out-degree to in-degree and those are equal for every vertex when edges go both ways. And the memory buffer needed to enable the trick is left unaddressed.
• Work further ahead than one iteration. If computing next round’s value early is good, computing two rounds ahead should be better. Where it broke. The paper measures the returns and finds they saturate almost immediately — going beyond one iteration ahead adds almost nothing, while the implementation must start tracking how far ahead every individual edge has been taken.
• The gap. Everyone had treated the sweep direction as fixed and asked how to make more edges eligible within it. Nobody had asked what happens if the direction alternates, which turns out to make the eligibility sets on consecutive passes exact complements.

How Grafu reads the graph once per two iterations

The idea

The direction of the sweep decides which edges can be worked ahead on, and nobody had tried alternating it. This is the observation the paper turns on, and it is the kind that seems inevitable afterwards. An edge is eligible only if its source vertex finished receiving updates earlier in the pass than the sweep reaches the edge. Walk the grid in a fixed direction and that condition selects one triangular half of it, every time, which is why prior work topped out around a third of the ceiling and spent effort renumbering vertices to shift more mass into that half. Reverse the direction on the next pass and the condition selects the other half — precisely the edges skipped last time. So the two passes tile the graph exactly: read everything once in the first iteration, then half per iteration forever after. Realising that the order in which work is traversed determines how much of it can be shared, rather than treating the order as fixed and optimising within it, is the same insight as the misaligned graph traversal work covered elsewhere on this site.

Put the barrier where the dependency is, not where the loop boundary is. The correctness requirement is that a vertex range’s next-round values exist before any edge leaving it is worked ahead on. The obvious way to guarantee that is to stop every thread at the end of each column, which is correct and expensive, since everyone waits for the slowest. But a thread moving into the next column only genuinely depends on that conversion when it reaches the specific chunk whose source is the range just completed. Everything before it is safe. So Grafu places the barrier immediately before that chunk instead, lets early finishers run ahead into the safe work, and removes the barrier outright once the conversion happens — worth 10.6% on its own. Removing synchronisation that a dependency argument proves unnecessary, rather than synchronising at whatever boundary is syntactically convenient, is the same reasoning as the causal-ordering data structure work covered elsewhere on this site.

One chunk resists the whole scheme, so change the layout until it barely exists. Edges whose source and destination fall in the same vertex range are a genuine circularity: working ahead on them needs that range’s next value, which needs those very edges processed normally first. The existing workaround is to hold that chunk entirely in memory and process it twice, which costs memory that an out-of-core system does not have — on some graphs, gigabytes. Grafu attacks the layout instead. If no edge connected two vertices in the same range, the chunk would be empty, which is graph colouring; since colouring is intractable and the number of ranges is fixed by the user anyway, Grafu relaxes it to minimising same-range pairs given a fixed palette and solves it greedily, cutting the buffer by hundreds to thousands of times. Reassigning which data lands in which partition so that the awkward case becomes rare is the same move as the near-data processing work covered elsewhere on this site.

Walking two iterations through the elevator

This is the situation prior work lives in permanently. Edges from a lower-numbered range to a higher one are eligible; the rest are not. That is one triangle of the grid, which is why a fixed sweep direction leaves roughly half the ceiling unclaimed no matter how much cleverness is applied within it.

Why it works

• The two sweep directions partition the edges exactly. Eligibility depends on whether a source range was completed before the edge is reached → forward selects edges going up the numbering and backward selects those going down → the two sets are complements, so after the first pass every loaded edge is used for two iterations.
• The ceiling is set by arithmetic, not by cleverness. Working ahead one iteration means loading everything once and half of it next time → that is a 50% reduction against loading it twice → so 47.4% is not a tuning result but a claim to have taken essentially all of what the technique offers.
• The dependency is narrower than the loop boundary. Only the chunk whose source range is the one just being converted actually needs to wait → placing the barrier there lets early-finishing threads proceed into the safe chunks → 10.6% recovered, and the gap between traffic saving and time saving narrows from 10 points to under 5.
• The awkward chunk is a property of the numbering, not the graph. Same-range edges force an in-memory buffer, but which vertices share a range is chosen by preprocessing → assigning identifiers so neighbours land in different ranges shrinks the buffer → hundreds to thousands of times less extra memory than the alternative.
• Independence from layout is itself the result. Prior work depends on a reordering that shifts edge mass into one triangle → alternating direction claims both triangles regardless → so performance is flat across reorderings and partition counts, which is what lets the memory-minimising layout be chosen freely.

What it costs (trade-offs and scope)

• One of the three contributions is not specific to this system. The relaxed barrier improves the prior system by 8.5% when applied to it, which the authors report and frame as generality. It is a fair framing and it does mean that part of the headline gap closes on its own.
• The margin over the prior system depends heavily on graph type. Against undirected graphs the improvement is 28.5% in traffic; against directed ones it is 13.6%. The reason is that the prior system’s reordering is defined by the ratio of out-degree to in-degree, which is identically one for every vertex in an undirected graph, so it does nothing there. A good share of the advantage on half the datasets comes from the baseline’s optimisation being inapplicable.
• Working ahead more than one iteration is abandoned, with measurement. The returns saturate almost immediately, and tracking how far each individual edge has been advanced is described as extremely complex. So the ceiling really is 50% for this family of techniques, not a step on a ladder.
• The scope is narrower than graph processing generally. Bi-directional graphs, and algorithms whose combining operation is commutative and associative. The authors state both assumptions and defer relaxing them.
• In the low-memory regime, two of the three ideas are switched off. When vertex data itself does not fit, the relaxed barrier is unsuitable and disabled, and working ahead on the awkward chunk is disabled to avoid its buffer. What remains is the sweep order plus a per-chunk barrier — which still wins by 35.5% over the prior system, but it is a different configuration than the headline.
• The colouring is a heuristic for a relaxed version of an intractable problem. Graph colouring is NP-complete, so Grafu solves a different problem — minimise same-colour adjacent pairs given a fixed palette — with a greedy rule and ties broken at random. It works well and carries no guarantee.
• The storage device is slow, which flatters traffic reduction. A single SATA drive at 550 MB/s sequential read. On faster storage the same traffic saving would translate into less time saving, since the balance between reading and computing would shift.
• The headline maximum is well above the average. Up to 1.55 times faster than the prior system, against averages of 23.0% in execution time and 21.4% in traffic.
• Twenty iterations, fixed. Every algorithm is run for a fixed count rather than to convergence, which is a reasonable normalisation and does mean the first-iteration penalty is amortised over a generous number of rounds.

The evaluation

Check yourself

Sources

The paper is “Grafu: Unleashing the Full Potential of Future Value Computation for Out-of-core Synchronous Graph Processing” by Tsun-Yu Yang, Cale England, Yi Li, Bingzhe Li and Ming-Chang Yang, published at ASPLOS 2024 Volume 2, pages 467-481, DOI 10.1145/3620665.3640409. The authors are at the Chinese University of Hong Kong, Oklahoma State University and the University of Texas at Dallas.

This explainer is written from the full text, read through a proxy of the ACM Digital Library copy. Everything above comes from the paper’s own sections 2 through 4: the description of grid-based edge partitioning and the distinction between semi-external and fully-external processing; the derivation of the 50% ceiling for working one iteration ahead and the measurement showing returns saturate beyond that; the motivating comparison putting the prior system at 34.4% traffic reduction and 24.2% execution time improvement against the baseline, with the explanation that barriers account for the gap; the elevator execution order with its worked three-partition example and the argument that forward and backward passes claim complementary triangles; the programming interface with its three user-supplied functions and its forward and backward entry points; the treatment of same-range chunks via an in-memory buffer processed twice; the conditional barrier placed at the chunk carrying the real dependency and removed on conversion; the greedy colouring reordering, its reduction from graph colouring, its complexity, and its measured preprocessing time against the prior reordering; the fully-external configuration with per-chunk barriers, page pinning, and the conditional barrier disabled; the evaluation over five algorithms and four billion-scale graphs at twenty iterations each on a single SATA SSD; the overall results of 47.4% traffic and 42.9% time against the baseline, 21.4% and 23.0% against the prior system, the 10.6% attributed to the conditional barrier and the 8.5% it gives the prior system, the split between 28.5% on undirected graphs and 13.6% on directed ones with its explanation in the prior reordering degree ratio; the memory tables showing the extra buffer reduced by orders of magnitude; and the fully-external results improving the prior system by 35.5%.