FINGERS: exploiting fine-grained parallelism in graph mining accelerators

Graph mining — finding every triangle, clique, or motif hidden in a huge graph — runs as a search tree per vertex, extended by set-intersection and set-subtraction on neighbor lists, and existing accelerators only parallelize the COARSE way, giving each processing element a whole different tree; but that leaves the hardware starved, because a single tiny set-intersect unit sits idle whenever a neighbor list misses the cache, and a few sky-high-degree vertices become stragglers; FINGERS (Tsinghua) instead finds three new axes of FINE-grained parallelism inside one tree's work — across the tree's branches, across the independent candidate sets updated from one added vertex, and across segments of a single set operation — and packs 24 cheap intersect units into each processing element to exploit them, running 6.2x faster per element and 2.8x faster at equal area than the state-of-the-art coarse-grained accelerator.

The argument in one glance

Problem

Finding every triangle and clique in a huge graph is brutally expensive

Graph mining searches a large graph for every subgraph that matches a small user-defined PATTERN — every triangle, every 4-clique, every motif or diamond — which powers analytics in social networks, biology, and chemistry. Pattern-aware algorithms do this by growing a SEARCH TREE from each vertex: start with one vertex, and at each level use SET INTERSECTION and SET SUBTRACTION on neighbor lists to compute the candidate vertices that could extend the partial match, branching on each. The work is enormous — an exponential search whose inner loop is dominated by set operations over neighbor lists — so it is a natural target for a dedicated hardware accelerator.
What people did

Build an accelerator with many PEs, each running its own search tree

The state-of-the-art accelerator, FlexMiner, does the obvious thing: put many processing elements (PEs) on a chip connected by a network, and have a global scheduler assign the search tree rooted at each vertex to a PE. Different trees are independent, so this COARSE-grained parallelism scales cleanly — thousands of vertices, thousands of independent trees, spread across the PEs. Each PE walks its tree depth-first, doing the set operations, and more PEs means more trees in flight.
Why it fell short

Coarse parallelism alone leaves the hardware starved and imbalanced

Handing each PE a whole tree wastes the hardware three ways. STALLS: a PE doing strict depth-first traversal has exactly one thing to do next, so when the neighbor list it needs misses the cache, it stalls on the long memory access with no other work to fill the gap. WASTED AREA: a PE spends most of its silicon on traversal-scheduling control and caching, while the actual set-operation compute unit is tiny — a FlexMiner PE is 0.18 square millimeters but a set-intersect unit needs under 0.01 — so the chip is mostly overhead wrapped around one small compute engine. IMBALANCE: real graphs follow a power law, so the trees rooted at a few very-high-degree vertices take vastly longer than the rest and become stragglers that bottleneck the whole run. Coarse parallelism cannot fix any of these, because they all live INSIDE a single tree.
This paper's idea

Find three new axes of parallelism inside one search tree

FINGERS (Tsinghua — Chen, Tian, Gao) keeps the coarse across-trees parallelism but discovers FINE-grained parallelism within a single tree's work, at three levels. BRANCH level: process independent branches of the tree in parallel instead of strict depth-first, so a PE always has other branches to run while a stalled one prefetches. SET level: extending one vertex updates several independent candidate sets — all from the SAME neighbor list — which can be computed together, streaming that list into cache once. SEGMENT level: split an individual set operation into fixed-length segments processed in parallel, cracking open the huge neighbor lists of high-degree vertices that caused the imbalance. Because a set-intersect unit is so cheap, each PE packs 24 of them to exploit all three. The result: 6.2x faster per PE and 2.8x faster at equal chip area than FlexMiner.

Why this problem is worth solving

Graph mining is a heavy hammer used everywhere from fraud detection to drug discovery, and its cost is dominated by a specific inner computation that hardware can accelerate — if it can keep the hardware busy. The core loop is

the way pattern-aware graph mining explores matches. To find all subgraphs matching a pattern, the algorithm grows a search tree from each starting vertex: at each level it has a set of CANDIDATE vertices that could extend the current partial match, and to advance it picks one candidate, adds it, and computes the candidate sets for the next level by INTERSECTING and SUBTRACTING neighbor lists — the intersection finds vertices connected to the right existing vertices, the subtraction removes ones that would violate the pattern or double-count. These set operations over neighbor lists are the overwhelming majority of the work, and they are what an accelerator’s compute units actually do. The trouble is that they are memory-bound (neighbor lists are large and scattered) and data-dependent (which candidate you pick determines the next sets)

, so the challenge is less raw compute than keeping the compute units fed and busy despite the memory stalls and the irregular, skewed structure of real graphs.

The existing accelerator got the coarse parallelism right and the utilization wrong. Assigning a whole search tree to each PE is clean and scalable, but it leaves each PE unable to hide its own stalls, because within a strict depth-first walk there is only ever one next step. And it collides head-on with the

the property of nearly all real-world graphs that a few vertices have enormous numbers of connections (neighbors) while most have very few — degrees follow a power law rather than being uniform. A social network has a handful of celebrities with millions of followers and billions of ordinary users with a few dozen. For graph mining this is punishing: the search tree rooted at a super-high-degree vertex has gigantic neighbor lists and an explosion of candidate combinations, so it takes orders of magnitude longer to finish than a typical tree. Under coarse parallelism, the PE assigned that one monster tree becomes a straggler, and the whole computation waits for it while other PEs sit idle

. Both failures are invisible to coarse parallelism because coarse parallelism operates BETWEEN trees, while the stalls and the stragglers live WITHIN a tree. The opportunity FINGERS seizes is that a single tree’s work is itself richly parallel, at several granularities at once, and exploiting that finer parallelism is what finally keeps the compute units saturated and balances the skewed load.

What people did before, and where it broke

CPU and GPU graph-mining systems (Peregrine, Pangolin, GraphPi). Flexible and programmable, but general-purpose cores spend enormous energy and cycles on the irregular set operations and pointer chasing that dedicated hardware does far more efficiently, so throughput per watt is poor.
FlexMiner (the coarse-grained accelerator baseline). Many PEs, each assigned a whole search tree, connected by a network. Scales across trees, but each PE stalls on its own cache misses (strict depth-first has no backup work), spends most of its area on control and caching around one tiny compute unit, and is wrecked by power-law stragglers.
Set-intersection accelerators for a single operation. Speed up one intersection at a time. Useful, but they optimize the leaf of the problem without addressing how to keep many operations in flight, hide memory latency across the tree, or balance the skewed workload — the systemic issues that actually cap utilization.
Just add more coarse PEs (the iso-area alternative). Spend the same silicon on twice as many small FlexMiner PEs. But each added PE inherits the same stalls and straggler problem and they contend harder for the shared cache, so utilization per PE stays low and the aggregate barely improves.
The gap. No prior accelerator exploited the parallelism that exists WITHIN a single search tree — across its branches, across the independent candidate sets, and across the segments of one set operation — which is exactly where the stalls and imbalance live. FINGERS finds all three and builds a PE to use them.

How FINGERS works

Keep coarse parallelism, then open three fine-grained levels and pack cheap compute units

Coarse parallelism across trees (kept)

A global scheduler assigns the search tree rooted at each vertex to a different PE over a network-on-chip, exactly as FlexMiner does. This across-trees parallelism is retained as the outer layer; FINGERS adds finer parallelism inside each PE rather than replacing it.
↓ →
Branch-level parallelism (pseudo-DFS) new

Within one tree, the different branches spawned at a level are independent, so a PE need not walk strictly depth-first. FINGERS groups sibling branches into task groups and runs whichever have cache-resident data first, while the others prefetch — so a stalled branch never idles the PE, mimicking how a multithreaded core switches on a miss to hide memory latency.
↓ →
Set-level parallelism new

When a newly-added vertex extends the match, it updates several independent candidate sets (up to one per remaining pattern level) — and every one of those updates intersects or subtracts against the SAME neighbor list of the added vertex. FINGERS computes them together, so that shared neighbor list is streamed into cache once and every chunk is reused across all the sets, turning a memory-bound step into a streaming one.
↓ →
Segment-level parallelism new

A single set operation is parallelized by pre-dividing each neighbor list into read-only fixed-length segments (size 16) and processing overlapping segment pairs independently. This is what cracks open the giant neighbor lists of high-degree vertices — the very stragglers coarse parallelism chokes on — spreading one huge operation across many compute units.
↓ →
Pack many cheap intersect units per PE new

Because a set-intersect unit is tiny (under 0.01 square millimeters) while control and caching dominate PE area, FINGERS puts 24 intersect units in each PE, fed by task dividers that pair up segments and balance their load: a binary search matches long-list segment heads to short-list segments, each unit handles one long segment against its paired short ones, and over-loaded pairings are split across units.
↓ →
Unify all set operations as intersection plus bitvector new

Intersection, subtraction, and anti-subtraction are all computed as a single primitive — a segment intersection whose result is a bitvector of the long segment's length, interpreted differently per operation — and partial results are merged by bitwise OR (valid because intersecting with a union equals the union of the intersections). One simple, replicable compute unit serves every set operation.

Evaluated on 7 patterns (triangle, 4-/5-clique, tailed triangle, 4-cycle, diamond, 3-motif) across 6 graphs (AstroPh, Mico, Youtube, Patents, LiveJournal, Orkut), against FlexMiner at equal area (20 FINGERS PEs vs 40 FlexMiner PEs). A FINGERS PE is 0.934 square mm at 28nm, 1 GHz, with the 24 intersect units taking only about 12% of its area.

The idea

When the coarse parallelism is exhausted, look for parallelism at a finer grain. FlexMiner parallelized the obvious way — across independent search trees — and stopped, which left every PE unable to hide its own stalls and helpless against stragglers, because those problems live inside a single tree. FINGERS’ central move is to keep going: it discovers that one tree’s work is itself parallel at three finer granularities (branches, candidate sets, and segments of a set operation) and exploits all of them. This is the go-deeper-for-more-parallelism discipline the site sees when a system that has run out of easy concurrency finds more by subdividing the unit of work — the same instinct behind splitting a simulation into replicated partitions or a set operation into segments — and here it is what finally saturates the compute units that coarse parallelism left idle.

Spend the silicon on the compute that is actually cheap, and buy a lot of it. The measurement that reframes the design is that a set-intersect unit costs under 0.01 square millimeters while a whole FlexMiner PE costs 0.18 — the compute is almost free, and the area is nearly all control and caching overhead. That overhead is a FIXED cost per PE, so the way to make it pay is to amortize it over many compute units: FINGERS packs 24 intersect units behind one PE’s control and cache, so the expensive part is shared while the cheap part is replicated. It is the amortize-the-fixed-cost logic the site keeps meeting — when the wrapper dominates and the kernel is tiny, put many kernels behind one wrapper — and it is only worthwhile because the three fine-grained parallelism levels generate enough independent set operations to keep all 24 units fed.

Turn the power-law straggler from a curse into fuel. Under coarse parallelism, a super-high-degree vertex is pure poison: its one giant tree becomes a straggler that everything waits on. FINGERS’ segment-level parallelism inverts this — a giant neighbor list is precisely what divides into the most segments, so the biggest, most-feared operations supply the MOST fine-grained parallelism to spread across the 24 units. The vertex that bottlenecked the coarse design is the one that now keeps the compute units busiest. This is the attack-the-straggler-at-a-finer- grain move the site sees in load-balancing schedulers, but with a twist worth savoring: the skew that hurt the old design is converted directly into the parallelism the new one runs on.

Where the coarse accelerator stalls, and what FINGERS opens

One search tree, three new axes of parallelism

Extending a partial match during pattern search. Numbers from FINGERS' evaluation against FlexMiner.

Step 1 of 5

The inner loop: extend by set operations

At each tree level the algorithm holds candidate vertex sets, picks a candidate to add, and computes the next level's candidates by intersecting and subtracting neighbor lists. These set operations over neighbor lists are essentially all of the work, and they are memory-bound — the neighbor lists are large and scattered in memory.

set intersection finds validly-connected candidates; subtraction removes pattern-violating or double-counted ones
which candidate you pick determines the next sets, so the work is data-dependent

Why it works

The stalls and stragglers that starve a coarse accelerator all live inside one search tree → FINGERS finds three parallelism levels within a tree (branches, candidate sets, segments) → it attacks the utilization problem where it actually lives.
Strict depth-first traversal has only one next step, so a cache miss freezes the PE → running independent branches in parallel gives the PE ready work during a stall → memory latency is hidden like a multithreaded core switching on a miss.
The several candidate sets updated from one added vertex all use its same neighbor list → computing them together streams that list into cache once and reuses every chunk → a memory-bound step becomes a streaming one.
A set-intersect unit costs under 0.01 square mm while a PE’s control and cache dominate its area → packing 24 cheap units behind one PE’s overhead amortizes the fixed cost → less than 2x the area delivers 6.2x the single-PE throughput.
High-degree vertices have the largest neighbor lists → so they divide into the most segments and supply the most segment-level parallelism → the power-law straggler that bottlenecked coarse parallelism becomes the fuel that keeps the units busiest.

What it costs

Sparse, low-degree graphs gain little. When neighbor lists are short and candidate sets small, there is scant fine-grained parallelism to exploit, so on large sparse graphs (Youtube, Patents) the speedup shrinks to 1-2x — the technique pays off in proportion to how much parallelism the data actually contains.
Clique patterns lack set-level parallelism. For cliques the candidate sets at all future levels are identical, so there are no independent sets to update in parallel; cliques rely on branch- and segment-level parallelism alone and see smaller gains than subtraction-rich patterns.
Memory latency is not always fully hidden. On graphs with heavy cache pressure and a low compute-to-memory ratio, even branch-level parallelism cannot cover all the stalls, capping the speedup.
Segment pairing has fixed limits and overhead. The task dividers handle at most 15 long-list heads and 24 short-list heads per pairing, so larger lists must be split and processed across multiple dividers or sequentially, eroding efficiency at the extremes.
Control overhead still dominates PE area. Even after packing 24 compute units, 44.8% of the PE area is control logic and another chunk is caching and buffers — the intersect units are only about 12% — so pushing parallelism further demands proportionally more control, a real scaling limit.

The evaluation

Seven patterns (triangle, 4-clique, 5-clique, tailed triangle, 4-cycle, diamond, 3-motif) across six graphs from small dense (AstroPh, Mico) to large sparse (Youtube, Patents) to large dense (LiveJournal, Orkut), simulated at 28nm and 1 GHz, compared against FlexMiner at equal chip area (20 FINGERS PEs versus 40 FlexMiner PEs).

Coarse-grained versus fine-grained graph-mining acceleration

Property	FlexMiner PE (coarse only)	Just add more FlexMiner PEs	FINGERS PE (three fine-grained levels)
Parallelism exploited
Compute units per PE
On a cache miss
High-degree straggler
Performance / area

Speedups vary sharply with pattern and graph: subtraction-rich patterns (tailed triangle, 4-cycle, diamond) and dense graphs reach 8-10x, while cliques and sparse low-degree graphs see far less — which is exactly why FINGERS supports all three parallelism levels rather than optimizing for one, since different workloads expose different amounts of each.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

FINGERS’ speedups are proportional to how much fine-grained parallelism a workload actually contains, so they vary sharply: subtraction-rich patterns on dense graphs reach 8-10x, but cliques (whose future candidate sets are identical, offering no set-level parallelism) and large sparse low-degree graphs (short neighbor lists, small sets) fall to 1-2x. Even branch-level parallelism cannot hide all memory stalls when cache pressure is high and the compute-to-memory ratio is low. The segment-pairing hardware has fixed limits (at most 15 long and 24 short heads per pairing), so extreme neighbor lists still incur splitting overhead, and despite packing 24 compute units, control logic still occupies almost half the PE area — a real limit on how far this parallelism can be pushed before overhead dominates again. Reducing every operation to intersection-plus-bitvector is elegant and general but may leave some efficiency on the table versus custom per-operation hardware. None of this undercuts the core lesson — that when coarse, across-tree parallelism has starved the compute units and left power-law stragglers, the fix is to find the finer-grained parallelism hiding inside a single search tree, at every level it appears, and to rebalance the silicon toward the cheap compute that now has enough work to stay busy.

Background

Go finer for parallelism, amortize the fixed overhead, and turn skew into fuel

FINGERS sits in the site’s accelerator-and-parallelism cluster and rhymes with several ideas covered elsewhere on this site. Its central move — when the obvious coarse parallelism runs out, keep looking at a finer grain — is the go-deeper-for-parallelism discipline the replicated-RTL-simulation page shares when it subdivides a circuit into partitions to expose thread parallelism, and the same instinct behind matching a computation to the parallelization strategy it actually admits, as the GNN-operator- scheduling page does. Its second move is an amortize-the-fixed-cost argument in silicon: because a set-intersect unit is almost free while a PE’s control and cache are not, packing 24 cheap units behind one expensive wrapper is the same when-the-kernel-is-tiny- replicate-it logic that turns a fixed overhead into a shared one — a resource-rebalancing cousin of the whole-accelerator accounting the 8-bit-numerics page uses to judge where area really goes. Its third move is the most satisfying: segment-level parallelism turns the power-law straggler — the very high-degree vertex that bottlenecks a coarse design — into the richest source of parallelism, the same attack-the-straggler-and-balance-the-load goal the heterogeneous-serving and GPU-microservice pages pursue, here achieved by converting skew directly into work for the units. And its unification of intersection, subtraction, and anti-subtraction into a single bitvector primitive is the one-mechanism-for-many-operations move the GNN-operator page makes when it expresses 160 operators as one nested loop — generality bought by finding the common shape beneath superficially different operations. Underneath all of it is a diversity-demands-generality conclusion: patterns and graphs differ so much in which parallelism they expose that the hardware must support all three levels rather than betting on one.

If you remember only three things

1. Graph mining finds every match of a small pattern (triangle, clique, motif) in a large graph by growing a search tree per vertex and extending it with set intersection and subtraction on neighbor lists, and the state-of-the-art accelerator FlexMiner exploits only COARSE-grained parallelism (one whole tree per processing element) — which starves the hardware three ways: a depth-first PE stalls on every cache miss with no backup work, most of a PE's area is traversal control and caching around one tiny compute unit, and power-law graphs make a few very-high-degree vertices into stragglers that bottleneck the run.
2. FINGERS keeps the coarse across-tree parallelism but discovers three levels of FINE-grained parallelism inside a single tree: BRANCH-level (run independent tree branches in parallel so a stalled one never idles the PE, hiding memory latency like a multithreaded core), SET-level (the several candidate sets updated from one added vertex all share its neighbor list, so computing them together streams that list into cache once), and SEGMENT-level (split each set operation into fixed-length segments run in parallel, which cracks open exactly the huge high-degree lists that caused imbalance) — and because a set-intersect unit is tiny, it packs 24 of them per PE, unifying intersection/subtraction/anti-subtraction into one bitvector primitive.
3. The result is 6.2x faster per PE (up to 13.2x) and 2.8x faster at equal chip area (up to 8.9x) than FlexMiner, for under 2x the PE area, with intersect-unit utilization of 55-95% — largest on subtraction-rich patterns and dense graphs, smallest on cliques and sparse graphs (1-2x), which is why FINGERS supports all three levels rather than one. The durable lessons: when coarse parallelism starves the compute, find the finer-grained parallelism inside the unit of work; amortize a dominant fixed overhead by replicating the cheap compute behind it; and turn the power-law straggler into the parallelism that feeds the machine.

Check yourself

Check your understanding

1. FlexMiner already parallelizes graph mining by giving each processing element its own search tree. Predict why this coarse-grained parallelism, despite scaling across thousands of trees, still leaves the hardware badly underutilized.
2. FINGERS packs 24 set-intersect units into each PE, where FlexMiner had one. Predict the reasoning that makes 24 units the right call rather than wasteful.
3. Power-law graphs give a few vertices enormous neighbor lists, and under coarse parallelism these create stragglers that bottleneck the whole run. Predict how FINGERS' segment-level parallelism changes the role of these high-degree vertices.
4. FINGERS' speedup ranges from 8-10x on subtraction-rich patterns and dense graphs down to 1-2x on cliques and sparse graphs, and the authors deliberately build hardware for all three parallelism levels. Predict what this variation implies about the design philosophy.

Sources

ACM DL: FINGERS: Exploiting Fine-Grained Parallelism in Graph Mining Accelerators — ASPLOS 2022 (full text read via the author-hosted Tsinghua PDF; no arXiv preprint).