RANGE-BLOCKS: A Synchronization Facility for Domain-Specific Architectures

Specialized accelerator chips are great at crunching fixed data but cannot really insert into or delete from a data structure, because they lack any way to lock a region while many parallel units modify it — and bolting on ordinary per-address locks needs huge on-chip lock tables and stalls everything; this paper (Simon Fraser University — Anagha Molakalmur Anil Kumar, Aditya Prasanna, Arrvindh Shriraman) presents Range-blocks, which locks a whole range of keys at once, so one tiny 2-kilobyte table replaces a 256-kilobyte lock cache and a 128-tile accelerator runs 15 times faster.

The argument in one glance

Problem

Accelerators can crunch data but cannot safely reshape it

Domain-specific architectures (DSAs) are accelerators built for one kind of computation — graph analytics, sparse linear algebra, database indexing — and they get their speed by specializing to a fixed data layout and running many parallel tiles over it. But that specialization comes with a sharp limitation: they work predominantly with static data structures. A DSA can update values in place, but it struggles to insert or remove data, which is exactly what real applications need — mutable, dynamically resizable structures like trees and hash tables that grow and shrink as the program runs. The reason DSAs cannot support dynamic data structures is that they lack a synchronization facility: when many parallel tiles want to modify a shared structure concurrently, something has to guarantee that two of them do not corrupt the same region at once, and DSAs simply do not have that machinery. Without it, an insert or delete that touches part of a tree cannot be safely coordinated with other operations happening at the same time. So the accelerators that are fastest at processing data are stuck being unable to safely change its shape, which cuts them off from a huge class of real-world workloads.
What people did

Borrow per-address atomics, or batch the updates on the host

To get some form of synchronization, DSAs fall back on one of two workarounds. The first is address-based atomics: treat synchronization the way CPUs do, taking a lock on each individual memory address (or object) that an operation touches, so concurrent operations serialize on those locks. The second is to give up on doing dynamic updates on the accelerator at all and batch them back on the host CPU, which does have proper synchronization, then hand the updated structure back. Both let a DSA nominally support mutation without inventing anything new.
Why it fell short

Both fallbacks are slow and need huge on-chip lock storage

Neither workaround is workable in practice. Address-based atomics are a poor fit for the kinds of structures DSAs manipulate: an operation on a tree or nested structure touches many objects, so it needs many individual address locks, and holding all those locks requires large on-chip caches — the paper points to caches on the order of 256 kilobytes just for the locks. That is a lot of scarce on-chip area and energy spent on bookkeeping, and acquiring many locks per operation also generates heavy on-chip traffic and serializes work, imposing prohibitive performance penalties. Batching updates on the host is worse in a different way: it drags data back and forth between the accelerator and the CPU and forfeits the parallelism the DSA was built for, so it does not scale. Underneath both is the same mismatch: address-based locking is fine-grained and oblivious to the structure, so it cannot compactly express "keep everyone out of this region of the tree," and it relies on ordering protocols to eventually reach mutual exclusion rather than expressing the conflict directly. What was missing was a synchronization primitive designed for the way DSAs lay out data — one that locks meaningful regions cheaply and reaches mutual exclusion immediately.
This paper's idea

Lock a range of keys, not a pile of addresses

Range-blocks (RBlox) is a hardware synchronization facility built specifically for DSAs so they can support dynamic data structures. Its central idea is to synchronize on key ranges rather than individual addresses: a lock covers a contiguous range of keys — say all keys from 10 up to 50 — which naturally captures a region of the data structure and taps into the parallelism inherent in how the structure is laid out. Two observations make this practical in hardware. First, range locks are symbolic: a single range compactly represents mutual exclusion over many nested objects at once, so any operation needs far fewer locks, and a tiny on-chip table — about 2 kilobytes — suffices where address-based locking needed caches around 256 kilobytes. Second, a range explicitly names the region of interest, so mutual exclusion is achieved instantly by checking whether two ranges overlap, instead of relying on an ordering protocol to serialize accesses. Together these turn synchronization from a heavyweight, cache-hungry, ordering-dependent mechanism into a compact, direct one that matches how DSAs work. On a 128-tile dataflow DSA, RBlox improves performance by 15 times, reduces DRAM bandwidth by 4 times, saves 70 percent of on-chip traffic, and uses only 6.6 percent of the on-chip energy compared with the address-based approach.

Why this problem is worth solving

Accelerators are where performance-critical computing is heading, and being unable to mutate data structures shuts them out of a huge range of real applications.

Domain-specific architectures deliver their large speedups precisely by specializing, and much of the world’s most demanding computing — graph analytics, databases, sparse and scientific workloads — is moving onto them. But real applications do not just read fixed data; they insert, delete, and resize: databases update indexes, graph systems add and remove edges, and countless algorithms rely on trees and hash tables that change shape as they run. If an accelerator can only update values in place, it can accelerate the static core of these workloads but not the mutation around it, which either caps the speedup or forces expensive round-trips to a host CPU that can mutate safely. So the inability to support dynamic data structures is not a corner case; it is a wall that keeps DSAs from taking on whole application domains. And the root cause is specific and fixable — the missing piece is synchronization, the ability to let many parallel units safely modify a shared structure. Providing that primitive, cheaply and in a way that fits how accelerators are built, therefore widens what DSAs can do, letting the fastest hardware handle the dynamic, mutable workloads that were previously off-limits. Because the fallbacks are so costly, an efficient synchronization facility can be the difference between a DSA being usable for these workloads or not.

The key realization is that the unit of locking should match the structure and directly express the conflict, not track individual addresses.

Address-based locking is inherited from general-purpose CPUs, where memory is an unstructured array and the natural thing to protect is a word or an object. But the data structures DSAs manipulate have meaningful regions — the keys in a subtree, a span of a sorted structure — and an operation typically cares about one such region, not a random scatter of addresses. Locking by address forces you to enumerate every object in the region and hold a separate lock for each, which is both expensive (many locks, big tables, lots of traffic) and indirect (you have not said “this region is mine,” you have only said “I hold these particular addresses”). RBlox’s insight is that a key range is a far better unit: it is symbolic, so one range stands in for all the nested objects it contains, collapsing many locks into one and shrinking the hardware from a 256-kilobyte cache to a 2-kilobyte table; and it is explicit about the region, so two operations conflict exactly when their ranges overlap, which the hardware can check immediately to grant mutual exclusion — no ordering protocol, no waiting to serialize. Matching the lock granularity to the data structure’s own layout is what makes synchronization both compact enough to fit on an accelerator and fast enough not to erase its speed. The abstraction, not just the implementation, is the contribution.

What people did before, and where it broke

Keep DSAs to static data structures. Only support in-place value updates, no inserts or deletes. Where it broke. Real applications need mutable, resizable structures (trees, hash tables), so static-only DSAs cannot serve those workloads.
Use address-based atomics. Lock each individual address or object an operation touches, as CPUs do. Where it broke. Operations on nested structures touch many objects, needing many locks and large on-chip caches (around 256 kilobytes), with heavy traffic and serialization — prohibitive penalties.
Batch updates on the host. Send mutations back to the CPU, which has real synchronization, and return the updated structure. Where it broke. It shuttles data between accelerator and host and forfeits the DSA’s parallelism, so it does not scale.
Rely on ordering to reach mutual exclusion. Let lock protocols serialize conflicting accesses over time. Where it broke. Ordering-based exclusion is indirect and slow compared with directly expressing which region is being protected.
The gap. No synchronization primitive matched the way DSAs lay out data — locking meaningful regions cheaply and reaching mutual exclusion immediately — so DSAs could not efficiently support dynamic data structures.

How Range-blocks works

From per-address locks to symbolic range locks

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

The idea

Give the accelerator a primitive it lacked so it can handle richer data. RBlox adds a synchronization facility to DSAs specifically so they can move beyond static layouts to mutable, dynamically resizable data structures. Extending a domain-specific accelerator with the machinery it needs to support genuine data structures — not just flat static arrays but indexes and trees that programs actually use — is the same enterprise the work on caching multi-level indexes in domain-specific architectures (METAL) covered elsewhere on this site pursues, equipping DSAs to handle the structured, hierarchical data of real applications. RBlox supplies the missing synchronization piece so those structures can also be safely mutated in parallel.

Specialize the mechanism to the data structure’s own layout. Rather than reuse the CPU’s address-based locking, RBlox designs synchronization around how DSAs lay out data, locking key ranges that correspond to regions of the structure and exploiting the parallelism that layout exposes. Building a hardware mechanism that is specialized to the structure of the data it operates on, so it is far more compact and efficient than a general-purpose approach, is the same principle the work on an instruction set and processor specialization for sparse computation (SparseCore) covered elsewhere on this site is built on, tailoring the hardware to the shape of the data. RBlox tailors the locking primitive to the data structure, shrinking a 256-kilobyte lock cache into a 2-kilobyte table.

Express conflicts directly to make mutual exclusion instant. Because a range names the region an operation protects, RBlox detects a conflict simply when two ranges overlap, granting exclusion immediately instead of serializing through an ordering protocol. Coordinating concurrent modifications of a shared structure by directly reasoning about which operations actually conflict, rather than pessimistically serializing everything, is the same goal the work on cooperative concurrency control for write-intensive key-value workloads (cooperative concurrency control) covered elsewhere on this site shares, letting non-conflicting work proceed in parallel. RBlox’s overlapping-range test is its way of admitting all the concurrency the data structure allows while still guaranteeing safety.

Following an insert through Range-blocks

Safely inserting into a shared structure on a DSA

An illustration, drawn from the paper's abstract, of how RBlox synchronizes a mutation. Internal mechanism details are the paper's.

Step 1 of 5

An operation targets a region of keys

A tile wants to insert (or delete) in some part of the data structure — say the keys between 10 and 50. Rather than identifying every object it will touch, it names the key range it needs.

The range corresponds to a region of the structure, exploiting its layout.

Why it works

A range matches the region an operation cares about. Address locks scatter across many objects → but a key range names the whole region of the structure directly → so one lock captures what an operation actually needs.
Symbolic ranges collapse many locks into one. Locking every nested object needs a huge lock cache → but a single symbolic range represents mutual exclusion over all of them → so a 2-kilobyte table replaces a 256-kilobyte cache.
Overlap testing gives immediate mutual exclusion. Ordering-based locking serializes to eventually exclude → but two ranges conflict exactly when they overlap → so the hardware grants or denies exclusion instantly.
Non-overlapping ranges run fully in parallel. Coarse or pessimistic locking blocks unrelated work → but disjoint key ranges are known not to conflict → so the DSA exploits the parallelism the data layout allows.
Compact, direct synchronization saves traffic and energy. Many locks per operation flood the on-chip network → but few symbolic range locks and direct conflict checks → so on-chip traffic drops 70 percent and energy to 6.6 percent.

What it costs (trade-offs and scope)

It requires new hardware in the accelerator. RBlox is a hardware synchronization facility — the range-lock table and overlap-check logic — that must be added to the DSA, not a software-only change.
The benefit assumes range-structured data. The efficiency comes from operations mapping to contiguous key ranges over the structure; workloads whose accesses do not correspond to clean ranges would fit the abstraction less well.
Very broad or highly-overlapping ranges reduce parallelism. Mutual exclusion is by overlap, so if operations frequently need wide, overlapping ranges, more of them conflict and serialize, shrinking the concurrency benefit.
It targets DSAs, not general CPUs. The design is specialized to how domain-specific accelerators lay out data and run tiles; its advantages are tied to that setting rather than to general-purpose synchronization.
Reported figures are on a specific accelerator and baseline. The 15-times speedup, 4-times DRAM-bandwidth reduction, 70-percent traffic saving, and 6.6-percent energy are measured on a 128-tile dataflow DSA against address-based atomics; results depend on the workload, structure, and baseline.

The comparison

Synchronizing dynamic data-structure updates on a DSA

Property	Address-based atomics	Batch on host	Range-blocks
Lock granularity
On-chip lock storage
Mutual exclusion
Uses DSA parallelism
Performance and cost

A comparison of ways to synchronize dynamic data-structure updates on a domain-specific accelerator. Address-based atomics need many locks and a large on-chip cache while serializing through ordering; batching on the host forfeits the DSA's parallelism. Range-blocks locks whole key ranges symbolically, so one small 2-kilobyte table replaces a 256-kilobyte cache and mutual exclusion is instant by overlap — giving 15 times higher performance at 6.6 percent of the on-chip energy on a 128-tile dataflow DSA. Exact figures should be read from the paper.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

This explainer is based on the paper’s abstract and public metadata, not its full text, which was not available at the time of writing. The high-level claims are the authors’: Range-blocks (RBlox) is a hardware synchronization facility for domain-specific architectures (DSAs) that enables support for dynamic (mutable, resizable) data structures, which DSAs otherwise cannot support because they lack synchronization and are forced to use address-based atomics or host-side batching (both with prohibitive penalties and large lock caches). RBlox uses key ranges to capture synchronization boundaries and exploit the parallelism of the data-structure layout, based on two observations: (i) range locks are symbolic and compactly represent mutexes over multiple nested objects, so operations need fewer locks and a small on-chip table (about 2 kilobytes) suffices versus large caches (about 256 kilobytes) for address-based locks; and (ii) ranges explicitly represent the region of interest, so mutual exclusion is achieved instantly (by overlap) instead of relying on ordering. The reported results, on a 128-tile dataflow DSA, are a 15-times performance improvement, a 4-times DRAM bandwidth reduction, 70 percent less on-chip traffic, and 6.6 percent of the on-chip energy. The background above on domain-specific architectures, static versus dynamic data structures, synchronization and mutual exclusion, and address-based locking is standard context provided to make the approach intuitive. The Flow, the step-by-step walkthrough, and the “Why it works” reasoning are illustrations built from the abstract’s description, not detailed accounts from the paper — the exact hardware design, the range-lock table and conflict logic, and the full evaluation should be read from the paper. Do not treat specific procedural details here as established beyond what the abstract states.

Background

Why specialized hardware keeps needing general-purpose primitives rebuilt for its own shape

It helps to see Range-blocks within a recurring tension in computer architecture: domain-specific accelerators win by shedding the generality of a CPU and specializing hard to one workload, but real applications keep dragging back in the general-purpose capabilities that the specialization left behind — memory management, indexing, and here, synchronization. The pattern is that a DSA is superb at the static, regular core of a computation and then hits a wall the moment the workload needs something dynamic or coordinated, because the primitive that a CPU takes for granted simply is not there. The productive response is not to abandon specialization or to bolt the CPU’s version on unchanged, but to redesign the missing primitive to fit the accelerator’s own structure and constraints, so it stays cheap and parallel. RBlox is a clean instance: it rebuilds synchronization around key ranges that match how DSAs lay out data, rather than importing the CPU’s address-based locks that need huge caches and serialize everything. This effort to give accelerators the general-purpose capabilities they lack, in a form tailored to their strengths, is the same terrain the work on accelerating task-parallel workloads by recovering program structure (TaskStream) covered elsewhere on this site occupies, bringing flexible parallel execution to specialized hardware. Range-blocks’s particular contribution is to show that the right abstraction — locking symbolic key ranges and detecting conflict by overlap — turns synchronization from a prohibitive bottleneck into a compact, fast facility, unlocking dynamic data structures on accelerators.

If you remember only three things

1. Domain-specific architectures (DSAs) accelerate computation by specializing to a fixed data layout and running many parallel tiles, but they mostly work on static data structures and can only update values in place — they cannot safely insert or remove data, because they lack a synchronization facility to coordinate concurrent modifications of a shared structure. Real applications (databases, graph systems, and algorithms built on trees and hash tables) need mutable, resizable structures, so this is a wall that keeps DSAs out of whole workload domains. The existing fallbacks are both bad: address-based atomics lock every object an operation touches, needing many locks, a large on-chip cache (around 256 kilobytes), heavy traffic, and serialization; and batching updates back on the host CPU forfeits the accelerator's parallelism and does not scale.
2. Range-blocks (RBlox) is a hardware synchronization facility for DSAs that locks key ranges instead of individual addresses. A range lock covers a contiguous span of keys — say 10 to 50 — which naturally captures a region of the data structure and exploits the parallelism inherent in its layout. Two observations make this efficient in hardware: range locks are symbolic, so one range compactly represents mutual exclusion over all the nested objects it contains, letting a tiny 2-kilobyte on-chip table replace a 256-kilobyte lock cache; and a range explicitly names the protected region, so two operations conflict exactly when their ranges overlap, which the hardware checks directly to grant mutual exclusion instantly rather than serializing through an ordering protocol.
3. On a 128-tile dataflow DSA, RBlox improves performance by 15 times, reduces DRAM bandwidth by 4 times, saves 70 percent of on-chip traffic, and uses only 6.6 percent of the on-chip energy compared with address-based atomics — making dynamic data structures practical on accelerators. The trade-offs and scope: it requires adding the range-lock hardware to the DSA, its efficiency assumes operations map to contiguous key ranges over the structure, very broad or frequently-overlapping ranges reduce the parallelism benefit, and it targets DSAs rather than general CPUs. This explainer is based on the paper's abstract; the hardware design and full evaluation should be confirmed in the paper.

Check yourself

Check your understanding

1. Why can domain-specific accelerators (DSAs) not easily support dynamic data structures?
2. Why are the existing fallbacks (address-based atomics or host batching) inadequate?
3. What is Range-blocks's key idea, and what two observations make it practical?
4. What does Range-blocks achieve, and what are the limits of the approach?

Sources

The paper is “RANGE-BLOCKS: A Synchronization Facility for Domain-Specific Architectures” by Anagha Molakalmur Anil Kumar, Aditya Prasanna, and Arrvindh Shriraman (Simon Fraser University), published at ASPLOS 2025, DOI 10.1145/3669940.3707225.

This explainer is written from the paper’s abstract and public metadata; the full text was not available at the time of writing, so the page is marked a draft. As reported there, Range-blocks (RBlox) is a hardware synchronization facility for domain-specific architectures that enables dynamic data structures by locking key ranges rather than addresses. It rests on two observations: range locks are symbolic and compactly represent mutual exclusion over many nested objects (so a roughly 2-kilobyte on-chip table replaces a roughly 256-kilobyte lock cache), and ranges explicitly represent the region of interest so mutual exclusion is instant by overlap rather than by ordering. On a 128-tile dataflow DSA, the paper reports a 15-times performance improvement, a 4-times DRAM bandwidth reduction, 70 percent less on-chip traffic, and 6.6 percent of the on-chip energy versus address-based locking. Background on domain-specific architectures, dynamic data structures, and synchronization is standard context. The specific numbers are the paper’s own; the hardware design and full evaluation should be confirmed in the paper.