BeeZip: Towards An Organized and Scalable Architecture for Data Compression

Compressing data is now one of the largest single consumers of processor time in a data centre, so people build hardware for it — and every such chip has bought its speed by compressing worse, landing around a ratio of 2 where software gets over 3; BeeZip (Chinese Academy of Sciences) argues the losses came from specific shortcuts rather than from hardware itself, and reaches 3.14 by scheduling the collisions prior designs simply threw away and by not storing the search window at full size everywhere it is needed.

The argument in one glance

Problem

Squeezing data has become one of the biggest bills in a data centre

Every byte stored or sent gets compressed first, and one measurement of a large provider found a single compression algorithm consuming more processor cycles than any other. Inside it, the dictionary-matching stage is nearly all of the work — around 80 percent of the time at moderate settings and almost all of it at aggressive ones. It is a tax paid continuously, everywhere.
What people did

Build a chip for it

The natural answer, and plenty exist — inside processors from two major vendors, on accelerator cards, as library offloads for graphics processors. They use brute-force comparator arrays over a shift register, or they split the lookup table across memory banks and run many lookups at once. They deliver the throughput they promise.
Why it fell short

All of them compress noticeably worse

Hardware accelerators land around a ratio of 2 while software reaches over 3, and the ratio is the reason anyone is compressing at all. The losses come from the shortcuts that made parallelism possible: comparator arrays only cover a tiny window, and hash-table designs simply drop data when two lookups collide on the same bank. One published design reaches a ratio of 1.68 at its widest setting.
This paper's idea

The losses are from specific shortcuts, not from being hardware

Split the algorithm so the regularly parallel part and the dependent part live in separate engines. Then schedule the bank collisions rather than dropping them, with a knob for how many you are willing to absorb. And stop giving every parallel unit a full copy of the search window, since most matches are nearby anyway. That reaches 3.14, above every accelerator measured.

Why this problem is worth solving

The two numbers that describe a compressor pull against each other, and hardware has consistently sacrificed the wrong one.

The original size of a file divided by its compressed size, so a ratio of 3 means the data takes a third of the space. It is the entire point of compressing — the reason to spend processor time at all is to store or send less — while throughput is how fast you can do it. Accelerators have historically improved throughput by degrading the search for repeated text, which improves the number people were not trying to improve, at the cost of the one they were.

is what the whole exercise is measured against, and a design that doubles speed while dropping from 3 to 2 has given back most of the benefit.

The trend in algorithms is making the hardware problem harder rather than easier.

The buffer of recently-seen data that a dictionary compressor searches for repeats. Anything appearing in it can be encoded as a short reference rather than repeated literally, so a bigger window finds more matches and compresses better. The older standard used 32 kilobytes; newer algorithms use hundreds of kilobytes or megabytes. That is straightforward in software, where the window is just memory, but expensive in hardware, because designs that run many searches in parallel have traditionally given each parallel unit its own copy.

is where the memory cost lives, and it grows with the product of window size and parallelism.

What people did before, and where it broke

Hold the history in a shift register and compare against all of it at once. A brute-force search implemented in logic, used by an accelerator shipping inside two production processor families. Where it broke. Comparator arrays do not scale, and timing gets worse as the register grows. One such design supports a 512 byte window; another has a 64 kilobyte register but only about five thousand comparators, so it cannot really search all of it.
Split the hash table across memory banks and look up many positions in parallel. The more scalable family, and the basis of most recent work. Where it broke. Any hash value can land in any bank, so several lookups in one cycle can collide on the same one — and the standard response is to discard the colliding lookups. Every discarded lookup is a match not found, which is why one such design falls to a ratio of 1.68 at its widest parallel setting.
Give each parallel matching unit its own copy of the history window. How parallel-hash designs make the search independent. Where it broke. It was affordable when the window was 32 kilobytes. At half a megabyte, replicating across sixteen units is tens of megabytes of on-chip memory, and the paper’s own control experiment shows doing it costs 22.9 additional megabytes for an 11.9 percent throughput gain and no ratio improvement at all.
Pack fragments of the history into the hash table itself. A refinement that removes the separate history buffer to save memory. Where it broke. It saves memory but does nothing about the collision problem, and the design that does it reports the parallel conflicts damaging its own ratio.
Rewrite the algorithm so the control flow is regular. What accelerators must do, because the dependencies are genuinely awkward — whether to probe depends on a lookup result, and how far to advance depends on how long a match turned out to be. Where it broke. The paper notes that existing rewrites introduce redundant probing, and probing is exactly the operation that a large window makes expensive.
The gap. Everyone treated the compression ratio losses as the price of parallelism. They are not — each one traces to a specific shortcut, and the shortcuts can be replaced with scheduling, a different unit of parallel work, and a memory layout that reflects where matches actually are.

How BeeZip finds repeated text

From input bytes to encoded matches, in two engines

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

10.42 gigabytes per second at ratio 2.96, or 5.95 at ratio 3.14 — higher than every accelerator compared against.

The idea

Hardware compression did not have to compress worse; it just kept choosing to. The gap being attacked is stark — accelerators cluster around a ratio of 2 while software reaches past 3 — and the framing that makes the paper work is refusing to treat that as intrinsic. Each loss traces to a nameable shortcut. Shift-register designs search a tiny window because comparator arrays do not scale. Hash-table designs discard lookups that collide on the same bank. Algorithm rewrites that make the control flow regular introduce redundant probing. None of these is a law about silicon; they are engineering decisions that were cheap when the window was 32 kilobytes and are not now. The structural move that opens everything else up is splitting the algorithm in two, because hashing sixteen input positions is perfectly regular while deciding where to search next depends on how long the previous match turned out to be — and tangled together, the dependent half dictates the parallelism of both. Refusing to accept that the fast implementation must be the worse-compressing one is the same stance as the scientific floating-point compression work covered elsewhere on this site.

When parallel lookups collide, schedule them instead of dropping them — and expose the trade as a knob. This is the sharpest contribution and it is almost embarrassingly direct. The hash table is split across 32 banks and any hash value can land in any of them, so several of the sixteen lookups issued in a cycle routinely target the same bank. Prior designs discard the losers, and a discarded lookup is a match that will never be found. BeeZip instead gives each bank a serialiser that filters the incoming values destined for it and feeds them through one at a time, with a crossbar afterwards to restore order. What makes this more than an obvious fix is the measurement behind it and the knob in front of it: a histogram of collision depth shows queue lengths typically of two or three, so a threshold of four absorbs nearly all real conflicts, and the ratio improves sharply from a threshold of one to two before saturating past four. That threshold is runtime-configurable, which is what turns the three published operating points into a genuine dial rather than three separate chips. Discovering that a many-to-many mapping onto banks creates conflicts that must be scheduled rather than dropped is the same problem as the near-data load balancing work covered elsewhere on this site.

Stop storing the search window at full size everywhere, because matches are not uniformly distributed. The memory argument is where the large window is made affordable, and it has two halves. The first is the unit of parallel work — grouping 64 lookups into a job and walking a job sequentially means a long match can skip the positions it covers, whereas parallelising consecutive lookups probes positions the match would have skipped, which is exactly the redundant work a large window makes expensive. The second is that within each matching unit, only one of four search engines holds the full half-megabyte history; the others are small copies of recent history, sized from the observed distribution of match distances, with larger engines able to serve requests aimed at smaller ones. The control experiment is convincing: making all four full-sized adds 22.9 megabytes for an 11.9 percent throughput gain and no ratio improvement whatsoever. Tiering copies of a large structure by how often each part is actually reached is the same technique as the embedding table caching work covered elsewhere on this site.

Processing one batch of lookups

Sixteen input positions, from hash to encoded match

Sixteen bytes arriving per cycle, a hash table split across 32 banks, and sixteen matching units downstream.

Step 1 of 5

Hash sixteen positions at once

Sixteen hash units each take five bytes starting at consecutive input positions and compute a hash value using the same integer hash the reference software uses. This part is embarrassingly parallel and has no dependencies at all.

Each hash value splits into three fields — which bank it belongs to, which row within that bank, and a tag for checking. The bank count and the number of hash units are deliberately independent, so the parallelism of hashing and the number of table banks can be tuned separately.

Why it works

The two halves of the algorithm have opposite characters. Hashing consecutive input positions has no dependencies at all, while advancing the search depends on the length of the match just found → so keeping them in one loop lets the dependent half cap the parallelism of both → and splitting them into pipelined engines lets each be parallelised on its own terms.
A collision is a lost match, not just a lost cycle. Discarding a lookup that collides on a bank means the repeat it would have found is encoded literally instead → so the standard shortcut converts a scheduling problem into a compression loss → and serialising the collisions costs cycles rather than ratio.
The collision depth is small enough to absorb. Measured queue lengths are typically two or three → so a threshold of four catches nearly all real conflicts, and the ratio saturates there → which is why the trade can be exposed as a knob rather than a design-time decision.
Sequential processing within a job lets long matches skip work. Advancing by the match length means the covered positions are never probed → so a design that parallelises consecutive positions performs probes a longer match makes unnecessary → and probing is precisely what a large window makes expensive.
Match distances are concentrated, so full copies are mostly waste. Over 85 percent of matches are under sixteen bytes and distances skew toward recent history → so only one engine per unit needs the full half-megabyte window and the rest can be small → confirmed by the control showing full-size copies buy 11.9 percent throughput and no ratio for 22.9 extra megabytes.

What it costs (trade-offs and scope)

Nothing was fabricated. The design is written in Verilog, verified by functional simulation, and put through logic synthesis on a 14 nanometre library. Throughput is cycle counts multiplied by an assumed 1 gigahertz that synthesis says timing permits. The paper states that area and power need physical fabrication and offers only qualitative analysis of them.
The memory cost is real and admitted. 13 megabytes of on-chip memory, which the paper says exceeds current designs in its family, and memory accounts for over 98 percent of the 28.91 square millimetre area. Two ways to dissipate it are proposed — sharing a cache with a processor core, or time-multiplexing scratchpad with other accelerators — and neither is implemented.
Several baselines are the authors’ own reconstructions. No results existed on this dataset for two of them, so one was re-simulated from its open-source hardware at an assumed matching clock frequency to remove process differences, and another was modelled behaviourally in software with a different entropy coder — which the authors say may slightly overestimate its performance.
Its closest competitor is faster. A commercial accelerator reaches 11.50 gigabytes per second against 10.42, so the claim is a 7 percent better ratio for 9 percent less throughput. Its architecture is undocumented, so nothing more can be said about why.
Only one stage is offloaded. The dictionary matching runs in hardware; entropy coding stays in software, as does all decompression. The argument that entropy coding will not become the bottleneck is by analogy to a system that offloads the same way, not a measurement.
The power comparison is not like for like, and the paper says so. Just under 2 watts for the synthesised block against 78.5 watts and 28 watts for two competitors, both measured at system level.
The ratio knob is still lossy. Even the highest setting discards collisions past a threshold of four, which is why it reaches 3.14 against software’s 3.19 at a comparable level.
Scaling is bounded by the other engine. Matching throughput scales linearly to 32 units then saturates, capped by the hashing engine’s 15.6 gigabytes per second, and the number of matching units barely affects the ratio at all.
One corpus, and one load-bearing distributional assumption. Everything is measured on a single 212 megabyte dataset, and the short-first probing that provides a 2.5 times throughput difference rests on the observation that most matches are under sixteen bytes.

The evaluation

Three ways to build hardware for dictionary compression

Property	Shift register with comparator arrays	Banked hash table, drop on collision
How the history is searched
What happens on a parallel conflict	Not applicable
Compression ratio achieved
Throughput	3.12 and 6.35 gigabytes per second
Cost		Memory grows with window size times parallelism

A 212 megabyte standard corpus, against software, a graphics library, a commercial accelerator, two production processor blocks and three research designs.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

Nothing here was fabricated. The design is Verilog put through functional simulation and logic synthesis at 14 nanometres, with throughput derived from cycle counts at an assumed 1 gigahertz that synthesis says the timing supports; the paper states plainly that area and power need physical fabrication and treats them only qualitatively. Several comparison points are the authors’ own reconstructions, because no results existed on this dataset — one competitor was re-simulated from its open hardware at a deliberately matched clock, another modelled behaviourally in software with a different entropy coder, which they note may overestimate it. The closest competitor is also faster, at 11.50 against 10.42 gigabytes per second, so the claim there is 7 percent more ratio for 9 percent less speed, against an architecture nobody has published. The memory cost is substantial and acknowledged — 13 megabytes on chip, exceeding others in its family, with over 98 percent of the area being memory, and the two proposals for dissipating it are unimplemented. Only the dictionary stage is offloaded; entropy coding and all decompression stay in software. The power comparison sets a synthesised block against system-level measurements, which they flag. And the short-first probing worth a 2.5 times throughput difference rests on a distributional property of the one corpus tested.

Background

Why compression keeps getting more expensive to make fast

Dictionary compression has a structure that resists hardware in an unusual way. The work is not arithmetic, it is search — and search whose next step depends on the result of the last one, since how far you advance is determined by how long a match you just found. That makes it terrible for the kind of wide, regular parallelism accelerators are good at, which is why every accelerator in this space is really a story about what was given up to make the control flow regular. Meanwhile the algorithms keep moving the other way: the standard that dominated for three decades used a 32 kilobyte window, and its successor uses hundreds of kilobytes, precisely because more history means better ratios. So the workload becomes more memory-hungry exactly as the pressure to accelerate it grows, and compression shows up as pure infrastructure overhead — the same framing under which the serverless function compression work covered elsewhere on this site treats it as something to be spent carefully rather than a feature. That combination is what makes this a harder architecture problem than it first appears.

If you remember only three things

1. Compression is one of the largest consumers of processor time in data centres, so accelerators exist — but every one of them compresses noticeably worse than software, landing around a ratio of 2 where software reaches past 3, which gives back most of the reason for compressing in the first place.
2. BeeZip argues those losses come from specific shortcuts rather than from hardware being hardware: it splits the algorithm so the regularly parallel hashing and the dependent matching become separate engines, serialises the hash-table bank collisions that prior designs simply discarded — with the tolerance exposed as a runtime knob calibrated against the measured collision depth — and groups lookups into jobs walked sequentially so a long match skips the positions it covers.
3. The large search window is made affordable by sizing history copies to where matches actually are, with only one full copy per matching unit; the result is 3.14 at 5.95 gigabytes per second, higher ratio than every accelerator compared, though nothing was fabricated, several baselines were reconstructed by the authors, its closest competitor is faster, and over 98 percent of the area is memory.

Check yourself

Check your understanding

1. Why do parallel hash-table compression accelerators lose compression ratio?
2. Why does the matching engine process positions within a job sequentially rather than in parallel?
3. How is the memory cost of a half-megabyte search window kept manageable?
4. What should qualify how the reported results are read?

Sources

The paper is “BeeZip: Towards An Organized and Scalable Architecture for Data Compression” by Ruihao Gao, Zhichun Li, Guangming Tan and Xueqi Li, published at ASPLOS 2024 Volume 3, pages 133-148, DOI 10.1145/3620666.3651323. It is open access under a Creative Commons Attribution licence.

This explainer is written from the full text of the published paper. Everything above comes from its own sections 2 through 10: the description of hash-boosted dictionary matching with its lookup, probe and update actions and the two output representations; the classification of prior accelerators into shift-register and parallel-hash-table families with their respective scaling limits, including the 512 byte window of one production design and the comparator count of another; the profiling establishing that the dictionary stage is 79.74 percent of the algorithm at moderate settings and that branch misprediction wastes over 30 percent of pipeline slots; the two challenges of window size and control flow irregularity, including the observation that existing algorithm rewrites introduce redundant probing; the section 4 split into two staged algorithms with their parameters, and the argument that sequential processing within a job lets long matches skip positions; the section 6 hashing engine with its many-to-many bank mapping, the serialiser and crossbar scheduling structures, the contrast with designs that discard colliding lookups, and the runtime threshold with the measurement of collision depth justifying its settings; the section 7 matching engine with its job dispatch, match job table, heterogeneous-scale search engines sized from the match distance distribution, short-first probing based on over 85 percent of matches being under sixteen bytes, and speculative issue; and the section 8 evaluation including the full baseline table, the exact methods by which each competitor’s numbers were obtained, the window size sweep, the memory and area accounting with its homogeneous control experiment, the ablations on probing and speculation, and the power comparison the authors themselves qualify as not being at the same level.