A one-for-all and o(v log(v ))-cost solution for parallel merge style operations on sorted key-value arrays

A surprising number of important computations — adding two sparse vectors, intersecting two sets, joining two database tables, merge sorting — are all the same shape underneath — walk two sorted key-value lists together and combine matching keys, and these merges eat most of the time in workloads like sparse matrix multiplication; this paper (UC Santa Barbara, Tsinghua) shows they are all one operation, gives a single abstract machine and four composable building blocks that express every variant regardless of key size or math, and builds the hardware for order V-log-V cost instead of the usual V-squared, hitting up to about 8 times speedup.

The argument in one glance

Problem

The same merge shows up everywhere, but every use gets its own incompatible solution

A whole family of important computations turns out to have the same underlying shape: take two sorted key-value arrays, walk them together, and combine elements whose keys match. Adding two sparse vectors, intersecting or unioning two sets, joining two database tables, and merge sort itself are all instances of this merge-style operation. And it is not a niche: sparse vector addition, a merge-style operation, takes up to 98 percent of the runtime of sparse matrix-matrix multiplication, and merges dominate graph mining too. So making merges fast matters enormously. The trouble is that the field has treated each flavor as a separate problem. The method that finds a set intersection — output only keys present on both sides — is built differently from the one that finds a union, which is different again from merge sort, and useful-but-less-common variants like set difference, left-join, and range-match are barely studied at all. There is no single solution that covers them all, so every application reinvents its own merge.
What people did

Build a fast, specialized merge unit for each application

The natural response is to accelerate each merge in hardware or with vector instructions, tuned to the job. Database accelerators build merge units for joins; sparse-linear-algebra accelerators build them for sparse addition and multiplication; sorting libraries have their own vectorized merge. Each is a monolithic datapath that fuses key-matching and value-combining for one specific task.
Why it fell short

Specialized units are rigid in datatype, and cost grows quadratically with parallelism

These per-application designs hit three walls. First, they are not reusable: the technique for one pattern cannot do another, so intersection hardware cannot do union or sort. Second, they are rigid in what they can hold, because they tightly couple key-matching and value-calculation into one datapath fixed to a datatype, usually 32-bit keys and values — but real sparse tensors and database tables use 64-, 96-, or 128-bit keys, or fixed-length strings, and want different value math, so one merge unit ends up serving only one application. Third, and most fundamentally, running V lanes in parallel almost always costs a V-by-V grid of comparators, a quadratic hardware cost of order V-squared for order-V performance; as one database-accelerator paper put it, because comparators grow quadratically with input width, wide merge hardware is hard to build. So you can have a fast merge, or a flexible one, but the parallel versions are expensive and each does only one job.
This paper's idea

Unify every merge into one machine, express it in four primitives, and build it cheaply

This paper shows all these operations are one operation, and attacks all three walls together. It introduces a unified abstract machine, the zip machine, that models any merge-style operation as a merge sort of the two arrays followed by a small state machine over a sliding window — so a single model covers union, intersection, sort, difference, join, and range-match, differing only in the state machine. It then restricts that machine into a fixed pipeline and shows any such pipeline compiles to just four composable, parallel primitives that place no restriction on key size, value size, or the combining math. And it implements those primitives on a bitonic sorting network, which needs only order V-log-V hardware instead of V-squared. The result is a single flexible design, usable as a SIMD instruction extension or a drop-in merge unit, delivering up to about eight times speedup.

Why this problem is worth solving

The merge is a hidden bottleneck under a startling range of workloads, so a better one pays off broadly.

A merge-style operation takes two sorted key-value arrays and produces a third, by scanning both in order and deciding, at each key, what to emit. Which keys survive and how their values combine defines the operation: keep keys on either side and add their values, and you have sparse vector addition, set union, or an outer join; keep only keys on both sides and multiply, and you have sparse multiplication, set intersection, or an inner join; keep everything in sorted order, and you have merge sort; match each element of one array to a range of the other, and you get piecewise functions or conversions between sparse storage formats. This one shape recurs across scientific computing, deep learning, databases, and graph analytics, and it is often the dominant cost — the paper measures sparse vector addition consuming up to 98 percent of sparse matrix-matrix multiplication. Because the merge sits on the critical path of so many important kernels, an inefficiency in how merges are done is an inefficiency almost everywhere, and conversely a single fast, general merge lifts all of them at once. That is what makes the fragmentation of the field — a different, rigid, expensive merge for each use — worth fixing.

The way merges are parallelized is exactly what makes them rigid and costly.

The obvious way to merge two length-V arrays in parallel is to compare every element of one against every element of the other, which is a V-by-V grid of comparators. That grid delivers order-V throughput but at order V-squared hardware cost, and the cost grows so fast with width that building a wide parallel merge is impractical. Worse, that comparator grid, and the datapath hung off it that does the value arithmetic, are usually fused into one monolithic block wired for a specific key width and a specific operation. So the design is doubly constrained: the quadratic comparator array limits how parallel you can afford to be, and the fixed datapath limits what datatypes and calculations it can serve, which is why a merge unit built for 32-bit sparse addition cannot be reused for a database join on string keys, or for a sort. Every parallel merge in prior work, except plain merge sort, inherits this quadratic, single-purpose structure. Breaking merges free of it — making one parallel merge that is cheap, and that can be reconfigured at runtime for any pattern, key size, and operation — is the technical heart of the paper.

What people did before, and where it broke

Per-pattern parallel merge methods. Build a distinct algorithm for intersection, another for union, another for sort. Where it broke. The methods are incompatible; one cannot do another, and less-common patterns like difference, left-join, and range-match go unsupported.
Monolithic domain-specific merge units. Fuse key-matching and value-calculation into one datapath tuned for a task. Where it broke. The fixed datatype (usually 32-bit) and fixed operation mean one unit serves only one application, unable to handle the 64-, 96-, 128-bit or string keys and varied math that real sparse tensors and database tables need.
V-by-V comparator arrays for parallel matching. Compare all pairs of the two inputs at once for order-V throughput. Where it broke. The comparator count grows quadratically with width, an order V-squared cost, so wide parallel merges are prohibitively expensive to build.
Reduced-comparator sparse schemes. Some accelerators cut the comparator count to between order V-to-the-1.5 and V-to-the-1.33. Where it broke. Still super-linear and still tied to a specific design, short of a genuinely cheap and general solution.
The gap. No approach unified all merge-style operations into one model, let it be reconfigured at runtime for any key size and value math, and implemented it at order V-log-V cost. Doing all three at once is what this paper contributes.

How the solution works

From many isolated merges to one machine, four primitives, and cheap hardware

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

The idea

All these operations are the same operation, so give them one machine. The paper’s founding move is a reframing: sparse addition, set intersection, database join, and merge sort are not distinct problems but one, and it captures that with the zip machine. The insight is that if you merge-sort the two input arrays first, identical keys become neighbors, so matching keys reduces to looking at a small sliding window of the merged stream; a tiny state machine over that window, deciding what to emit at each step, then expresses every variant — the only thing that changes between union, intersection, sort, difference, and join is the state machine’s decisions. That single model turns a scattered field into one problem with one solution. Building a unifying abstract machine that subsumes a whole family of sparse operations under one execution model, rather than treating each as its own accelerator, is the same consolidating ambition the work on the sparse abstract machine covered elsewhere on this site pursues, replacing a zoo of point designs with one machine that many operations compile onto.

Separate matching from arithmetic, and both become configurable. The restricted zip machine’s key structural choice is to split the work into two clean stages: figure out which elements pair up and where the gaps are, producing two aligned operand streams; then apply the combining math element-wise. This separation is what buys flexibility, because once matching is its own stage, the pattern is just a small configuration fed to a table-lookup step rather than baked into wiring, and once arithmetic is its own stage, it is ordinary vector math that can be anything on any datatype. The four primitives — merge-and-tag, match-to-commands, permute-into-operands, and split-for-length — are composable, so the same building blocks assemble every operation. Expressing a diverse space of sparse computations as compositions of a few reconfigurable primitive instructions, rather than fixed-function datapaths, is the same composable-ISA philosophy the work on a stream ISA and processor specialization for sparse computation covered elsewhere on this site adopts, trading monolithic units for primitives that recombine.

Reuse the sorting network so parallelism is cheap. The final move dissolves the quadratic cost. A parallel merge does not actually need to compare all pairs; a bitonic sorting network merges two sorted arrays with only order V-log-V compare-and-swap elements, a classic result, and the paper shows the same network can carry both the merge and the permutation the primitives need, with each switcher gaining a two-bit state so multi-field keys route correctly. So the whole design runs V lanes at order V-log-V hardware rather than V-squared, and can be dropped into an existing accelerator to slash its merge-unit cost. Attacking sparse matrix multiplication by making its dominant merge both flexible and cheap in hardware is the same target the work on multi-dataflow sparse matrix multiplication acceleration covered elsewhere on this site aims at, and this paper contributes the merge engine underneath, the part that consumes most of the time.

Following a set-union through the four primitives

Computing the union of two sorted arrays in one parallel pass

A trace, following the paper's example, of how the four primitives merge two sorted key-value arrays under the union (OR) pattern.

Step 1 of 5

Two sorted arrays arrive

The inputs are two sorted key-value arrays, for example keys one, two, five, eight and keys one, three, five, seven. The union should keep every key, combining the values where a key appears on both sides, and this whole job runs in a single pass over the two inputs.

The same pass, with a different pattern configuration, would compute intersection, sort, difference, or a join instead.

Why it works

Merge-sorting first makes matching local. Finding which keys pair up could require comparing everything to everything → but after a merge sort identical keys are neighbors, so matching only needs a small sliding window → so a tiny state machine, not a global comparison, suffices to express any pattern.
One state machine covers every variant. Union, intersection, sort, difference, and join look like different problems → but each is just a different set of decisions over the same merged event stream → so a single abstract machine subsumes them all, ending the need for a separate method per operation.
Splitting matching from arithmetic unlocks flexibility. Fusing key-matching and value math into one datapath fixes the datatype and operation → but making matching a configurable lookup and arithmetic a separate element-wise step frees both → so any key width, value width, and combining operation is supported at runtime on fixed hardware.
A sorting network merges in log-linear hardware. A parallel all-pairs merge needs a V-by-V comparator grid, order V-squared → but a bitonic sorting network merges two sorted arrays with only order V-log-V switchers → so the same order-V throughput comes at dramatically lower cost.
Two-bit switcher state handles wide, multi-field keys. A plain sorting network compares single fixed-width elements → but giving each compare-and-swap switcher a two-bit state lets it defer to less-significant fields when more-significant ones tie → so the one cheap network correctly routes arbitrarily large multi-field keys.

What it costs (trade-offs and scope)

Inputs must be sorted. Merge-style operations, and the zip machine, assume the two input key-value arrays are already sorted; feeding unsorted data requires a separate sort first, and the benefits accrue to the merge, not to producing the sorted order.
Only patterns that fit the restricted machine are covered. The restricted zip machine expresses operations as a fixed pipeline with a finite sliding window and four FIFO commands; one-to-many matching is handled by duplicating and finite-state encoding, but operations needing genuinely unbounded state beyond this structure fall outside the model.
The measured speedups are CPU SIMD. The headline results are from encoding the primitives as SIMD instructions on CPU at 16 lanes; the order V-log-V hardware design is presented and analyzed, and the primitives can serve as an accelerator merge unit, but the end-to-end accelerator gains depend on the surrounding design, and throughput scaling flattens beyond a point.
The pattern is a bounded configuration. The matching pattern is encoded compactly and realized by fixed-size parallel table lookups, which is expressive across the studied operations but is a finite configuration space rather than arbitrary logic.
It accelerates the merge, not the whole kernel. The work targets the dominant merge inside applications like sparse matrix multiplication; the rest of such a kernel — its loop structure, memory layout, and orchestration — is complementary and not what this design speeds up.

The evaluation

Parallelizing merge-style operations

Property	Per-application merge units	V-by-V comparator merge
Operations supported
Key and value flexibility
Hardware cost for V lanes
Deployment
Measured speedup (16 lanes, CPU)	Baseline	Baseline

From the paper's CPU evaluation with 16 lanes (512-bit SIMD, 32-bit elements). The unified zip-machine primitives achieve 8.4 times speedup on set operations, 7.3 times on database joins, 6.5 times on sparse vector, matrix, and tensor addition and multiplication, 8.0 times on merge sort over scalar (3.4 times over state-of-the-art SIMD), and 4.4 times on sparse matrix-matrix multiplication over the best baseline, at order V-log-V hardware cost rather than V-squared.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The contribution is a genuine unification: recognizing that sparse addition, set operations, database joins, and merge sort are all one merge-style operation, and delivering a single design that is general, flexible, and cheap at once. The zip machine models any such operation as a merge sort followed by a small state machine; restricting it yields a fixed pipeline that compiles to four composable primitives — merge-and-tag, match-to-commands, permute-into-operands, split-for-length — which separate matching from arithmetic so any key size, value size, and operation are supported; and implementing them on a bitonic sorting network brings the parallel cost from order V-squared down to order V-log-V. As a SIMD extension on CPU it reaches up to about eight times speedup across a wide range of kernels. Read it within scope. Inputs must be pre-sorted; only operations expressible in the restricted machine’s finite-window, four-command pipeline are covered; the headline numbers are CPU SIMD at 16 lanes, with the hardware design analyzed rather than the main measured result; the pattern is a bounded configuration; and it accelerates the merge itself, not the entire surrounding kernel. Within those bounds it is an elegant example of finding one problem hiding behind many, and solving it once, cheaply, for all.

Background

Why sparse merges are worth this much effort

It helps to see why so much architecture work circles this one primitive. A great deal of modern computing is sparse: matrices and tensors that are mostly zeros, sets and graphs and database tables represented as lists of the entries that actually exist. Working with such data means constantly bringing two of these sorted lists together — the nonzeros of two matrix rows, the members of two sets, the rows of two tables — and reconciling them by key, which is exactly a merge. Because sparsity is everywhere in scientific computing, machine learning, graph analytics, and databases, this reconciliation is one of the most executed operations in the datacenter, and in kernels like sparse matrix multiplication it is where nearly all the time goes. That is why the field has produced a steady stream of accelerators for the broad space of sparse tensor algebra, each trying to make these irregular, data-dependent combinations efficient. Serving that whole varied space of sparse operations with flexible, efficient hardware rather than a rigid single-purpose engine is the same goal the work on a flexible and efficient accelerator for sparse tensor algebra covered elsewhere on this site pursues. This paper zooms in on the merge at the center of it and shows that the many merges are one, cheaply parallelizable once you see them that way.

If you remember only three things

1. Merge-style operations — walking two sorted key-value arrays together and combining matching keys — underlie sparse vector addition, set intersection and union, database joins, and merge sort, and they dominate runtime in applications like sparse matrix multiplication (sparse addition alone is up to 98 percent of it), yet prior work treated each variant as a separate problem with incompatible methods, hard-wired fixed key and value sizes so one merge unit served one application, and paid an order V-squared hardware cost for order-V parallelism via all-pairs comparator grids.
2. The paper unifies them with the zip machine, which models any merge-style operation as a merge sort of the two arrays (making identical keys neighbors) followed by a small state machine over a sliding window; restricting it to a fixed pipeline that separates key-matching from value arithmetic, it compiles any such machine to four composable, single-pass SIMD primitives — KeyCombine (merge and tag), Match (turn the pattern into command streams by parallel table lookups), SEPermute (shuffle values into two aligned operand streams field by field), and GetBreakpoint (split inputs longer than a vector) — so any key size, value size, and combining operation is supported at runtime on fixed hardware.
3. Implementing the primitives on a bitonic sorting network, with each compare-and-swap switcher augmented by a two-bit state for multi-field keys, brings the parallel cost from order V-squared to order V-log-V, and the design serves as a SIMD instruction extension or a drop-in replacement for an accelerator's merge unit; on CPU with 16 lanes it achieves 8.4 times speedup on set operations, 7.3 on joins, 6.5 on sparse algebra, 8.0 on merge sort over scalar (3.4 over state-of-the-art SIMD), and 4.4 on sparse matrix multiplication, with the caveats that inputs must be pre-sorted, only operations expressible in the restricted machine are covered, and the headline numbers are CPU SIMD.

Check yourself

Check your understanding

1. What is a merge-style operation, and why does making it fast matter so much?
2. What three limitations did prior parallel-merge solutions have?
3. What is the zip machine, and how does it enable a single flexible solution?
4. How does the design avoid the quadratic hardware cost, and what did it achieve?

Sources

The paper is “A One-for-All and O(V log(V))-Cost Solution for Parallel Merge Style Operations on Sorted Key-Value Arrays” by Bangyan Wang, Lei Deng, Fei Sun, Guohao Dai, Liu Liu, Yu Wang, and Yuan Xie (University of California, Santa Barbara; Tsinghua University; and Alibaba DAMO Academy), published at ASPLOS 2022, DOI 10.1145/3503222.3507728. It is released under a Creative Commons Attribution license.

This explainer is written from the full text of the authors’ version. Everything above comes from the paper’s own sections: the introduction and problem statement defining merge-style operations over two sorted key-value arrays and their patterns (OR for sparse addition, set union, and outer join; AND for sparse multiplication, set intersection, and inner join; SORT for merge sort; and range-match for piecewise functions and sparse-format conversions), the measurement that sparse vector addition takes up to 98 percent of sparse matrix-matrix multiplication, and the three limitations of prior work (no one-for-all solution, no runtime flexibility for variable key and value sizes and calculations given fixed hardware, and an order V-squared comparator-array cost); the general zip machine as a merge sort followed by a state machine over an event stream with per-event push or no-push actions, and the restricted zip machine that builds two aligned operand streams via four FIFO commands (NoPush, PushCurrent, PushMostRecent, PushDefault) determined from a sliding window of three events, then applies the operation element-wise; the four composable vectorized primitives KeyCombine, Match (parallel table lookups turning a pattern into command streams), SEPermute (a shuffle producing operand streams field by field), and GetBreakpoint (divide-and-conquer for inputs longer than one vector); the order V-log-V hardware based on a bitonic sorting network with each compare-and-swap switcher augmented by a two-bit state for multi-field keys, usable as a SIMD ISA extension or a drop-in merge unit; and the CPU evaluation at 16 lanes (512-bit SIMD, 32-bit elements) reporting speedups of 8.4 times for set operations, 7.3 for database joins, 6.5 for sparse vector, matrix, and tensor addition and multiplication on real and complex numbers, 8.0 for merge sort over scalar and 3.4 over state-of-the-art SIMD, and 4.4 for sparse matrix-matrix multiplication over the best baseline.