Glign: Taming Misaligned Graph Traversals in Concurrent Graph Processing

Running many graph queries at once — dozens of shortest-path or breadth-first searches from different starting points over one huge graph — should be cheap, because they all read the same enormous graph and could share it in the cache, but they do not, because each query's active wavefront is in a different region at any moment, so their memory accesses are MISALIGNED and running 64 together can thrash the cache worse than running them one by one; Glign (UC Riverside) fixes this by ALIGNING the traversals in time — processing each vertex for all queries at once whenever any query needs it (safe because these computations are monotonic), and, since a few "heavy" iterations near the graph's hubs dominate the cost, delaying the head-start queries so everyone's heavy iteration lands together — cutting cache misses by 93% and beating the best prior concurrent-graph systems by 3.6-4.7x.

The argument in one glance

Problem

Many graph searches at once should share the graph — but they miss each other

A common workload is running many graph queries on one graph at the same time — dozens of breadth-first searches or shortest-path computations, each from a different starting vertex. The graph itself is huge and is read by every query, so in principle they should cooperate: when one query pulls a chunk of the graph into the cache, the others could reuse it for free, sharing the expensive memory traffic. That is the whole promise of concurrent evaluation. In practice it collapses. Different queries start from different sources, so at any given moment each one is exploring a different region of the graph — their active wavefronts are in different places — and they touch almost none of the same data at the same time. Running 64 queries together can produce MORE cache misses than running them one after another, and it only gets worse as you add more queries.
What people did

Batch the queries together and let them share the graph

The established idea is to BATCH concurrent queries and process the shared graph once for the whole batch — systems like Ligra-C, Krill, and GraphM do this, co-scheduling many queries so they read the graph structure together instead of each fetching it separately. The intuition is sound: the graph is the big, reused thing, so run the queries side by side and amortize the graph accesses across all of them. Group the queries, iterate over the graph, and let the shared memory hierarchy do its job.
Why it fell short

Batching without alignment does not make the accesses coincide

Batching puts the queries in the same process, but it does nothing to make them touch the SAME vertices at the SAME time — and sharing in the cache only happens when the accesses coincide. Because each query has its own active frontier that marches through the graph from its own source, at iteration after iteration the batched queries are working on disjoint sets of vertices: query A is deep in one community while query B is just leaving another. So the graph data one query brings into the cache is evicted before another query needs it, and the reuse never materializes. The systems even maintain separate per-query frontiers, whose bookkeeping adds memory pressure (about 300 MB for 64 queries on one graph) on top of the wasted traffic. Batching amortizes the graph read only if the queries are ALIGNED — reading the same parts together — and nothing in prior systems aligns them, so the promised sharing largely fails to appear.
This paper's idea

Align the traversals in time so their accesses coincide

Glign (UC Riverside — Yin, Zhao, Gupta) makes the accesses coincide by ALIGNING the concurrent traversals along a shared timeline of global iterations, at three levels. INTRA-ITERATION: keep a single query-oblivious frontier for the whole batch — whenever any query activates a vertex, process that vertex for ALL queries at once, so every access is shared; this is correct because the queries' vertex functions are MONOTONIC, so activating a vertex early only does harmless extra work that converges to the same answer. INTER-ITERATION: since a few "heavy" iterations near the graph's high-degree hubs dominate the cost, align THOSE across queries by DELAYED START — postpone the queries that would otherwise race ahead, so every query's heavy iteration lands in the same global iteration. And ALIGNMENT-AWARE BATCHING groups queries whose heavy iterations arrive at similar times. Together they cut last-level-cache misses by 93% and beat the best prior systems (Krill, GraphM) by 3.6-4.7x.

Why this problem is worth solving

Concurrent graph queries are a real and growing workload — analytics services answer many users’ shortest-path or reachability questions over the same social or web graph at once — and the graph is the dominant cost, so making the queries share it is worth a large factor. The sharing they are supposed to get comes from

the reuse that concurrent queries can get on the graph structure. A graph’s topology (its vertices and edges) is large and is read identically by every query, regardless of that query’s source. So when one query loads a region of the graph into the cache to process it, that same region is in the cache and free to reuse for any other query that needs it at that moment. If the queries are processing overlapping regions, the expensive memory traffic of reading the graph is paid ONCE and amortized across the whole batch — this is why running queries concurrently should be far cheaper than running them one at a time

. The entire value proposition of concurrent evaluation rests on this reuse actually happening.

But reuse only happens when the accesses coincide in time, and that is exactly what different queries fail to do, because of

the fact that a graph query works through the graph as an expanding FRONTIER — the set of vertices it is actively processing in the current iteration — that starts at the query’s source and grows outward hop by hop. Two queries from different sources have frontiers that start in different places and expand through different parts of the graph, so at any given iteration they are active on largely DISJOINT sets of vertices: one is exploring vertices near its source, the other near a completely different source. Since the cache holds only a small working set, the graph data one query brings in is evicted long before the other query, off in its own region, would have used it. The traversals are misaligned in time, so the sharing that concurrent execution promised does not occur — and the more queries you batch, the more different regions are being touched at once, the worse the contention gets

. That is why naive batching can be slower than sequential execution: it pays the coordination and memory-pressure costs of running everything together while getting none of the reuse benefit. The opportunity Glign seizes is that the traversals CAN be aligned — you can make the queries process the same vertices in the same iterations — turning misaligned batches that thrash the cache into aligned ones that genuinely share it.

What people did before, and where it broke

Sequential evaluation (one query at a time). Run each query to completion before the next. No sharing at all — every query re-reads the whole graph from memory — so the graph traffic is paid once per query, the baseline Glign improves on by 5.2x.
Two-level frontier batching (Ligra-C). Batch queries and track which are active per vertex. Real but modest gains (about 2.1x over sequential), because it still lets each query keep its own frontier and does not align WHICH vertices are active together.
Compiler-based concurrent systems (Krill). Co-schedule queries and share graph iteration. Only about 1.4x over sequential, and its misaligned frontiers can push last-level-cache misses to 15 billion where Glign has 1 billion — because it batches without aligning.
GPU-specialized concurrent BFS (iBFS). Hand-tuned to run many BFS on a GPU. Effective for its narrow case, but Glign’s aligned batching beats it 1.45-3.17x, and it does not generalize across query types the way alignment does.
The gap. Every prior system batched concurrent queries to share the graph but left their traversals misaligned, so the accesses did not coincide and the sharing largely failed. Glign aligns the traversals in time — intra-iteration, inter-iteration, and by affinity-aware batching — so the shared accesses actually happen.

How Glign works

Put the queries on a shared clock, align each vertex, align the heavy iterations, batch by affinity

Recognize sharing needs alignment, not just batching

Concurrent queries share the graph in cache only if they touch the same vertices at the same time. Prior systems batch queries but leave their frontiers misaligned, so the accesses never coincide. Glign's job is to ALIGN the traversals along a shared timeline so the reuse actually happens.
↓ →
Establish a shared timeline of global iterations new

Glign runs the whole batch under shared synchronization barriers — GLOBAL ITERATIONS — so all queries advance in lockstep and can be aligned against a common logical clock. This timeline is what lets Glign say "process this vertex now, for everyone" and "delay this query by two iterations."
↓ →
Intra-iteration: one query-oblivious frontier new

Instead of a separate frontier per query, Glign keeps ONE frontier for the batch: when any query activates a vertex v, v is processed for ALL queries at once, so the read of v and its edges is shared across the whole batch. This is correct because the vertex functions are MONOTONIC — activating a vertex earlier than strictly needed only does redundant work that still converges to the right value — and it also collapses per-query frontier memory from about 300 MB to 5 MB.
↓ →
Inter-iteration: find the heavy iterations new

Frontier sizes are highly skewed across iterations on power-law graphs: a few HEAVY iterations, when the traversal reaches the high-degree hub vertices and the frontier explodes, dominate the total cost. Aligning those heavy iterations across queries is where most of the sharing benefit lives — so Glign targets them specifically rather than trying to align the whole traversal.
↓ →
Delayed start: make the peaks coincide new

Glign estimates when each query's heavy iteration will arrive by its least number of hops to the nearest high-degree vertex (precomputed with one reverse BFS from the hubs). Queries far from a hub start at iteration 0; queries close to a hub are DELAYED by the difference, so all the heavy iterations land in the same global iteration and share their expensive accesses.
↓ →
Batch by affinity, and lay out values for coalescing new

Glign groups into a batch the queries whose heavy iterations arrive at similar times — high AFFINITY, meaning their unified frontier is much smaller than the sum of individual frontiers (lots of overlap). It also stores each vertex's per-query values adjacently in memory, so processing a vertex for all queries is a single coalesced access.

Evaluated on BFS, SSSP, single-source widest/narrowest path, and Viterbi (all monotonic, single-source), with 512 source vertices each, over 5 power-law graphs (LiveJournal 4.8M vertices to Friendster 125M) and road networks, against Ligra-C, Krill, GraphM, and iBFS. One-time hub-profiling costs 0.20-3.84 seconds against query times of 4.47-53.40 seconds.

The idea

Sharing is only real if the accesses coincide — so align the work in time. The premise of concurrent graph processing is that queries share the graph in the cache, but a cache only helps when two accesses to the same data happen close together, and misaligned traversals put the queries in different regions at every moment, so the shared data is evicted before anyone reuses it. Glign’s foundational move is to make the accesses coincide by aligning the traversals along a shared timeline — processing the same vertex for all queries at once, and scheduling the queries so their expensive phases overlap. This is the same make-the-work-coincide-to-share-a-resource discipline the site sees when the task-parallel page multicasts one memory fetch to many consumers, or the sparse-tiling page co-tiles operands so their active regions align on-chip — sharing is not automatic from proximity; you have to arrange for the uses to line up. And it comes with the same cautionary edge those pages carry: batching without alignment is worse than nothing, because you pay the coordination cost and get no reuse.

Exploit monotonicity to make harmless redundant work buy alignment. The query-oblivious frontier processes a vertex for EVERY query in the batch whenever ANY query needs it — which does extra work, evaluating vertices for queries that did not strictly require them yet. That would be incorrect for a general computation, but these graph queries are MONOTONIC: a vertex’s value only ever moves in one direction (a BFS distance only decreases, a shortest path only shortens), so activating a vertex early cannot produce a wrong final answer — it just converges there sooner, through a little redundant computation. Glign trades that cheap redundancy for perfect intra-iteration alignment and a collapse of per-query frontier memory. This is the exploit-a-structural-property discipline the site rewards — the collectives page using a monotonicity property to prune its search provably, the better-than-worst-case pages relaxing exactness where the math forgives it — where a mathematical guarantee (monotone convergence) licenses an aggressive simplification that would otherwise be unsafe.

Align the part that dominates, not the whole thing. A graph traversal is wildly non-uniform: most iterations touch a handful of vertices, but a few HEAVY iterations — when the frontier hits the high-degree hubs and explodes — account for most of the cost and most of the potential sharing. So Glign does not try to align entire traversals; it aligns the heavy iterations, delaying head-start queries just enough that their peaks coincide. Concentrating the alignment effort on the cost-dominating phase is the tackle-the-skew, align-the- bottleneck discipline the site keeps meeting — the memory-allocation page solving its most-contended time phases first, the edge-inference and data-plane pages exploiting that a few heavy hitters dominate — and here it is doubly apt, because power-law graphs make the heavy iterations both the most expensive to compute and the most valuable to share, since that is when all the queries are pounding the same hub vertices.

From two searches that miss each other to two that share the cache

Running concurrent single-source traversals on one graph. Numbers from Glign's evaluation.

Step 1 of 5

Two searches, two regions, no sharing

Two breadth-first searches start from different source vertices. At iteration k, one is exploring the neighborhood around its source while the other is off in a distant part of the graph. Their active frontiers are disjoint, so the graph data one pulls into the cache is evicted before the other, in its own region, would need it. Despite reading the same graph, they share almost nothing.

a query's frontier expands hop by hop from its source, so different sources means different regions
the cache holds only a small working set, so misaligned accesses never overlap in it

Why it works

Concurrent queries share the graph in cache only if they touch the same data at the same time → Glign aligns the traversals along a shared timeline so the accesses coincide → the reuse that batching promised finally happens.
Separate per-query frontiers keep the queries misaligned and cost memory → one query-oblivious frontier processes each vertex for all queries at once → every access is shared and frontier memory drops from ~300 MB to ~5 MB.
Processing a vertex for queries that did not yet need it would be wrong in general → but the vertex functions are monotonic, so early activation only converges sooner → the aggressive sharing is provably correct.
A few heavy iterations near the hubs dominate cost and sharing potential → delayed start makes those heavy iterations coincide across queries → the alignment effort is spent exactly where it pays most.
Queries whose heavy iterations arrive far apart share little → affinity-aware batching co-runs queries whose peaks align, with values laid out for coalesced access → 3.6-4.7x over prior systems and 93% fewer cache misses.

What it costs

Monotonic, single-source queries only. The query-oblivious frontier is correct only for monotonic vertex functions, and Glign targets single-source traversals (BFS, shortest/widest/narrowest path, Viterbi); non-monotonic or whole-graph algorithms like PageRank and clustering do not fit.
Power-law graphs, not road networks. The heavy-iteration idea relies on a skewed frontier distribution; road networks have shallow diameters and no sharp frontier peaks, so inter-iteration alignment yields little there.
Preprocessing latency. The hop-to-hub profiling is a one-time reverse BFS that is amortized but adds upfront cost (3.84 seconds on the Twitter graph) before queries can be aligned.
Synchronous only, with a greedy heuristic. Glign’s alignment needs shared barriers, so it is incompatible with asynchronous evaluation, and its delayed-start heuristic finds the optimal two-query alignment only 33.6% of the time (within 2 iterations 95.4% of the time), reaching 1.41x against an optimal 1.50x.
Homogeneous batches and bounded lookahead. Mixed-type query batches show little improvement, the batching window limits how far ahead it can look (risking indefinite postponement without a threshold), and optimal alignment was only studied for pairs, so many-query optimality is unknown.

The evaluation

BFS, SSSP, single-source widest and narrowest path, and Viterbi (all monotonic, single-source), 512 sources per type, over 5 power-law graphs (LiveJournal 4.8M vertices to Friendster 125M) plus road networks, against sequential Ligra, Ligra-C, Krill, GraphM, and the GPU system iBFS, measuring speedup, last-level-cache misses, and per-technique contributions.

Running many graph queries on one graph

Property	Sequential (one at a time)	Naive batching (Krill, Ligra-C)	Glign (aligned)
Shares graph accesses?
Frontiers aligned?	n/a
Cache misses (LiveJournal BFS)	Baseline
Heavy iterations aligned?	n/a
Speedup	Reference

Glign converts the misaligned batches that thrash the cache (sometimes worse than sequential) into aligned ones that genuinely share the graph, by making the accesses coincide — one query-oblivious frontier for intra-iteration sharing, delayed start to align the cost-dominating heavy iterations, and affinity-aware batching — for 3.6-4.7x over the best prior systems and a 93% cut in cache misses.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Glign’s alignment rests on assumptions that bound where it applies. The query-oblivious frontier is correct only for MONOTONIC vertex functions, and the system targets single-source traversals, so non-monotonic or whole-graph algorithms (PageRank, clustering) are out of scope. The heavy-iteration alignment assumes a skewed, power-law frontier distribution, so road networks with shallow diameters see little inter-iteration benefit. The hop-to-hub profiling adds a one-time preprocessing cost, the alignment requires synchronous barriers (ruling out asynchronous evaluation), and the delayed-start heuristic is greedy — optimal on only about a third of two-query cases though usually close — with homogeneous batches favored and many-query optimality unstudied. None of this dulls the core insight — that concurrent graph queries share the graph in cache only when their accesses COINCIDE, which batching alone does not ensure, so the fix is to align the traversals in time: process each vertex for all queries at once (safe under monotonicity), delay head-start queries so the cost-dominating heavy iterations near the hubs land together, and batch queries whose peaks align — turning cache-thrashing concurrency into genuine sharing, for a 93% cut in cache misses and multiples over prior systems.

Background

Make the accesses coincide, exploit monotonicity, and align the part that dominates

Glign sits in the site’s graph-processing cluster, near the graph-mining and GNN-operator pages, and rhymes with several ideas covered elsewhere on this site. Its founding move is that sharing a resource is only real if the uses coincide, so it aligns concurrent traversals in time to make the cache reuse actually happen — the same make-the-work-coincide-to-share discipline the task-parallel page uses when it multicasts one memory fetch to many consumers and the sparse-tiling page uses when it co-tiles operands so their active regions meet on-chip; and it carries the same warning those pages imply and this one proves outright, that naive concurrency without alignment is worse than nothing, a counterintuitive-negative the FHE-compiler page (vectorization slowing FHE) and the tiered-memory page (monitoring slowing the workload) also report. Its cleverest mechanism exploits a structural property to license an aggressive simplification: because the queries are MONOTONIC, processing a vertex for all of them early is harmless, so a single query-oblivious frontier replaces per-query ones — the exploit-a-mathematical-guarantee move the PCIe-collectives page uses when a monotonicity property makes its search prune provably and the better-than-worst-case pages use when they relax exactness where the math forgives. And its inter-iteration alignment concentrates on the heavy iterations near the hubs, the tackle-the-skew, align-the- bottleneck discipline the memory-allocation page shows solving its most-contended phases first and the data-plane and edge-inference pages show exploiting that a few heavy hitters dominate — doubly apt here, since on power-law graphs the heavy iteration is at once the most expensive to compute and the most valuable to share, being exactly when every query is pounding the same hub vertices.

If you remember only three things

1. Running many single-source graph queries (BFS, shortest path) on one graph at once should be cheap because they all read the same huge graph and could share it in the cache — but queries from different sources have active frontiers in different regions at every iteration, so their accesses are MISALIGNED, the shared data is evicted before reuse, and naive batching (Ligra-C, Krill, GraphM) can miss the cache MORE than sequential execution, worsening as the batch grows; batching amortizes the graph read only if the queries are aligned, and prior systems batch without aligning.
2. Glign aligns the traversals along a shared timeline of global iterations at three levels: INTRA-iteration, one query-oblivious frontier processes each vertex for ALL queries whenever any needs it (correct because the vertex functions are MONOTONIC, so early activation only does harmless work that still converges, also collapsing frontier memory from ~300 MB to ~5 MB); INTER-iteration, since a few heavy iterations near the high-degree hubs dominate cost, DELAYED START postpones head-start queries — by their hops to the nearest hub, precomputed with one reverse BFS — so all the heavy iterations coincide; and AFFINITY-AWARE BATCHING co-runs queries whose peaks align, with per-query values laid out for coalesced access.
3. The result cuts last-level-cache misses 93% (15 billion to 1 billion on LiveJournal BFS) and beats Krill by 3.6x and GraphM by 4.7x on average (up to 9.4x, and 5.2x over sequential), with intra-iteration, inter-iteration, and batching each contributing — its honest limits being monotonic single-source queries only, power-law graphs (road networks gain little), synchronous evaluation, and a greedy heuristic optimal on about a third of two-query cases. The durable lessons: sharing a resource is only real if the uses coincide, so align the work in time; exploit a structural property (monotonicity) to license an aggressive simplification; and concentrate alignment on the skewed part that dominates the cost.

Check yourself

Check your understanding

1. Batching concurrent graph queries is supposed to let them share the graph in the cache, yet the paper shows 64 batched queries can miss the cache MORE than running them one at a time. Predict why batching alone fails.
2. Glign's query-oblivious frontier processes a vertex for EVERY query in the batch whenever ANY query activates it — doing work for queries that did not yet need it. Predict why this is correct rather than a source of wrong answers.
3. Glign does not try to align entire traversals; it specifically aligns the "heavy iterations" near the graph's high-degree hubs, via delayed start. Predict why concentrating alignment on those iterations is the right focus.
4. To align the heavy iterations, Glign must know when each query will reach the hubs, which it estimates by each source's hops to the nearest high-degree vertex, precomputed with one reverse BFS. Predict why this cheap estimate is worth computing.

Sources

ACM DL: Glign: Taming Misaligned Graph Traversals in Concurrent Graph Processing — ASPLOS 2023 (full text read via the ACM PDF; no arXiv preprint).