Parallel programs guard shared data with atomic regions, and modern hardware runs them optimistically — several at once, speculatively — aborting and retrying when two conflict, then falling back to a slow serialized lock after enough failed retries; those repeated retries and the fallback waste a lot of time; this paper (University of Murcia and Uppsala — Eduardo Jose Gomez-Hernandez, Alberto Ros, and colleagues) observes that most conflicting atomic regions touch the same small, unchanging set of cachelines when they retry, and presents cleAR, which on the first abort re-runs the region while holding exclusive ownership of exactly those cachelines — so it cannot be interfered with and is guaranteed to finish in a single retry, cutting average retries per committed region from 7.9 to 1.6 and execution time by 35 percent.
The argument in one glance
-
Problem
When two speculative atomic regions collide, the hardware wastes work retrying
Parallel programs must coordinate access to shared data, and they do it with atomic regions (ARs) — chunks of code that must appear to run without interference from other threads. The classic way is mutual exclusion: protect the region with a lock, so only one thread runs it at a time. That is simple but serializes threads even when they would not actually have conflicted. To do better, hardware offers speculative lock elision (SLE) and, more generally, hardware transactional memory (HTM): run many atomic regions at once, speculatively, assuming they will not conflict, and use hardware conflict detection to catch cases where two regions actually touch the same data in a conflicting way. When a conflict is detected, the hardware aborts: it throws away the region's work, restores a checkpoint from before the region, and retries. The problem is that these systems are best-effort. On a conflict they retry a fixed number of times, and each retry re-runs the whole region speculatively and may abort again; if the retries run out, the hardware falls back to slow serialized mutual exclusion. So a conflict is expensive twice over: repeated wasted speculative work, and a costly serialized fallback.
-
What people did
Retry speculatively a few times, then fall back to a serialized lock
The standard best-effort recipe is exactly this. When an atomic region aborts, the hardware retries it speculatively, hoping the conflicting thread has moved on. It repeats this up to a preset threshold to avoid livelock (endless mutual aborting). If the region still cannot commit after the threshold, the hardware gives up on speculation and takes the fallback path: acquire a coarse lock and run the region under serialized mutual exclusion.
-
Why it fell short
Repeated speculation and the serialized fallback both cost a lot
Both halves of this recipe are expensive. Each speculative retry redoes the entire atomic region and, under contention, may simply abort again, so a hot, contended region can burn through many retries — the authors measure an average of 7.9 speculative attempts per committed region — before it either succeeds or gives up. And when it does give up, the fallback to serialized mutual exclusion is slow, because it forces threads to run the region one at a time, exactly the serialization speculation was meant to avoid. The deeper issue is that speculation offers no guarantee: it is best-effort, so it cannot promise a region will commit in a bounded number of tries. What is missing is a way to guarantee that a region, once it has conflicted, will succeed on its very next attempt — without reverting to coarse serialization — so that the cost of a conflict is bounded rather than open-ended.
-
This paper's idea
On the first abort, re-run holding exclusive ownership of the exact cachelines
The authors observe that most atomic regions that abort touch a small, fixed set of memory locations that does not change when they retry — on average, 60.2 percent of the regions that abort after the first attempt access the same cachelines on the retry, and those cachelines fit in a small footprint (fewer than 32 cachelines). For such regions you do not need to keep speculating; you can guarantee success by locking exactly those cachelines. This paper presents cleAR (Cacheline-locked executed Atomic Region), a hardware technique that, on the first abort, re-executes the region in a cacheline-locked mode: the core acquires exclusive ownership (via the cache coherence protocol) of every cacheline the region will access, so no other thread can read or write them while the region runs. With the data held exclusively, the retry cannot be interfered with and is guaranteed to commit — bounding the region to a single retry rather than an open-ended series of speculative attempts. The authors first establish the conditions under which a region can safely run in cacheline-locked mode (its accessed cachelines are known, immutable across the retry, and few enough to lock at once), and the detection and conversion are transparent to software — programs need no changes. cleAR raises the fraction of regions that commit on the first retry from 35.4 percent to 64.4 percent, cuts fallback to serialized mutual exclusion from 37.2 percent to 15.4 percent, drops average attempts per committed region from 7.9 to 1.6, and reduces execution time by 35.0 percent over the baseline and 23.3 percent over more elaborate approaches like PowerTM.
Why this problem is worth solving
Coordinating threads around shared data is one of the oldest and most performance-critical problems in parallel computing, and speculation is how modern hardware tries to make it cheap. A parallel program constantly needs one thread to update shared data without another thread seeing a half-finished change, so it wraps such updates in atomic regions that must appear to execute indivisibly. The traditional enforcement, mutual exclusion via locks, is safe but pessimistic: it serializes every thread that takes the lock, even when two threads touch entirely different data and would never have conflicted. Because lock and unlock operations sit on the hot path of parallel programs, they often dominate performance, and choosing lock granularity is a painful trade-off — coarse locks are easy to reason about but serialize too much, while fine-grained locking is fast but error-prone. Speculative lock elision and hardware transactional memory attack this by being optimistic: let many atomic regions run at once, assume they will not actually conflict, and rely on hardware to detect the rare true conflicts and undo them. When conflicts are genuinely rare, this recovers enormous parallelism that locking would have thrown away, which is why it is built into commercial processors. The catch is what happens when conflicts are not rare — on hot, contended regions — because that is exactly where the optimism breaks down and the cost of handling conflicts starts to dominate. Making that conflict-handling cheap and predictable is what determines whether speculation actually helps on the contended regions that matter most.
The trouble is that best-effort speculation turns a conflict into an open-ended, expensive event. When two speculative atomic regions conflict, the hardware aborts one: it discards all the work that region did, rolls back to a checkpoint taken before the region began, and retries from scratch. Under low contention this is fine, because the retry usually succeeds. Under high contention it is a disaster, for two reasons. First, each retry re-executes the entire region speculatively and may conflict again with the same or another thread, so a contended region can cycle through many retries, each one pure wasted work — the paper measures an average of 7.9 attempts before a region commits. Second, to avoid livelock (threads endlessly aborting each other and never making progress), the hardware caps the retries at a threshold and then falls back to serialized mutual exclusion: it takes a coarse lock and runs the region alone. That fallback is slow precisely because it reintroduces the serialization speculation existed to avoid. So the fundamental weakness is that speculation is best-effort — it gives no bound on how many attempts a region will take, and its escape hatch is the very serialization it was meant to replace. The high, unpredictable cost of conflicts is what a better design must fix, ideally by guaranteeing that a conflicted region can finish quickly on its next try.
What people did before, and where it broke
- Mutual exclusion with locks. Protect each atomic region with a lock so only one thread runs it at a time. Where it broke. It serializes threads even when they would not have conflicted, and the lock and unlock operations dominate performance; coarse locks over-serialize while fine-grained locks are hard to get right.
- Speculative lock elision and hardware transactional memory. Run atomic regions concurrently and speculatively, using hardware conflict detection to undo the rare true conflicts. Where it broke. They are best-effort: on a conflict they retry, and each retry redoes the whole region and may abort again, so contended regions waste many attempts (about 7.9 on average).
- Retry a fixed number of times, then fall back. Cap speculative retries at a threshold to avoid livelock, then take a coarse lock. Where it broke. The fallback to serialized mutual exclusion is slow, reintroducing exactly the serialization speculation was meant to avoid, and it is triggered often under contention.
- Non-speculative primitives that need addresses known in advance. Techniques like hardware multiple-compare-and-swap guarantee progress but require knowing all accessed addresses a priori. Where it broke. That is only feasible for a restricted class of programs, so it cannot be applied directly to general atomic regions.
- The gap. No technique gave a general, software-transparent guarantee that a conflicted atomic region would commit on its next attempt without falling back to coarse serialization, so the cost of conflicts stayed high and unbounded.
How cleAR works
Converting a conflicted region into a guaranteed single retry
-
-
-
new
-
new
-
new
-
new
The idea
Turn a speculative atomic region into a guaranteed one when it conflicts. cleAR’s foundational move is to stop treating conflict as something to keep gambling on and instead, on the first abort, switch the region to a mode that cannot fail — exclusive cacheline locking — so the retry is guaranteed to commit. Running atomic regions optimistically and speculatively, tracking their read and write sets and undoing conflicts, is the same transactional-memory foundation the work on software transactional memory for processing-in-memory systems covered elsewhere on this site builds on, providing speculative atomicity with conflict detection. cleAR keeps that speculative first attempt but replaces the open-ended retry loop with a single, guaranteed one, changing how the conflict case is handled rather than how the common case runs.
Handle contention without collapsing to serialization. The point of cleAR is that a conflicted region need not fall all the way back to a coarse serialized lock; it can still finish on its own next attempt by locking just its data. Handling contention on shared data cleverly, so hot conflicts do not force the slow, fully-serialized path, is the same goal the work on cooperative concurrency control for write-intensive key-value workloads covered elsewhere on this site pursues, keeping throughput up precisely where contention is worst. cleAR does this at the hardware level for atomic regions, converting the expensive fallback into a bounded, single-retry guarantee for the majority of regions that qualify.
Use the cache coherence protocol as the locking mechanism. The elegance of cleAR is that it needs no new locking hardware: it acquires exclusive ownership of each needed cacheline through the coherence protocol the processor already has, and exclusivity means no other core can interfere. Repurposing the cache coherence machinery already in the processor to provide a strong guarantee, rather than adding a separate mechanism, is the same instinct the work on a cache-coherent interface to the network card covered elsewhere on this site follows, letting coherence do the heavy lifting. cleAR uses coherence-level exclusivity as a per-cacheline lock, which is why the re-execution is guaranteed conflict-free and why the technique is transparent to software.
Following a conflicted region through cleAR
Two threads hit the same hot atomic region
A trace, drawn from the paper, of how cleAR bounds a contended region to a single retry.
Step 1 of 5
Two threads speculatively run the same small atomic region
Two threads each enter a hot atomic region that updates a shared data structure, running speculatively under hardware transactional memory. The region touches only a handful of cachelines, and it accesses the same ones regardless of which thread runs it.
This is exactly the kind of small, stable-footprint region cleAR targets.
Why it works
- Most conflicting regions have a stable, small footprint. A contended region often touches the same few cachelines each time it runs → so those cachelines are known and unchanged on the retry → so the hardware can lock exactly them, which covers about 60 percent of regions that abort.
- Exclusive ownership makes interference impossible. A conflict happens only when another thread accesses the region’s data mid-execution → but holding every needed cacheline exclusively bars any other core from touching them → so the locked retry cannot conflict and is guaranteed to commit.
- A single guaranteed retry beats open-ended speculation. Best-effort retries can abort repeatedly under contention → but converting to cacheline locking on the first abort bounds the region to one more attempt → so average attempts per committed region fall from 7.9 to 1.6.
- It avoids the slow serialized fallback. Running out of speculative retries normally forces a coarse serialized lock → but a guaranteed single retry lets the region finish itself → so fallback to serialized mutual exclusion drops from 37.2 percent to 15.4 percent.
- Reusing coherence keeps it transparent and cheap. Exclusive cacheline ownership is already provided by the coherence protocol → so cleAR needs no new locking hardware and no program changes → so the detection and conversion are transparent to software.
What it costs (trade-offs and scope)
- It only helps regions with a small, stable footprint. cleAR’s guarantee applies when the accessed cachelines are known, immutable across the retry, and few enough (fewer than 32) to lock at once; regions whose addresses depend on data that changes between attempts, or that touch too many cachelines, do not qualify and keep the normal threshold-and-fallback path.
- Holding cachelines exclusively can block other threads. While a region runs cacheline-locked, it denies other cores access to those cachelines; this guarantees the region’s progress but can stall others that want the same data, so it trades some concurrency for a bounded, guaranteed commit.
- It must coordinate with the fallback path. Because some regions still fall back to serialized mutual exclusion, cleAR needs a mechanism to ensure cacheline-locked executions and fallback executions do not clash, which is extra hardware complexity added to the coherence and speculation machinery.
- It is a hardware technique, evaluated in simulation. cleAR adds architectural support and is evaluated in a full-system simulator (gem5, modeling 32 cores similar to an Intel Icelake); realizing it requires processor changes, and the exact gains depend on the microarchitecture and workloads modeled.
- The benefit tracks contention and region shape. The improvements are largest where conflicts are frequent and regions are small and stable; workloads with little contention gain little (speculation already succeeds), and those with large or data-dependent regions fall outside the qualifying set.
The evaluation
Handling a conflicted atomic region
| Property | Serialized locks | Best-effort HTM (retry then fall back) | cleAR |
|---|---|---|---|
| Runs non-conflicting regions in parallel | |||
| Attempts per committed region | |||
| Falls back to serialized mutual exclusion | |||
| Guarantees progress on the retry | |||
| Execution time |
Check yourself
Check your understanding
1. Why is best-effort hardware transactional memory expensive when atomic regions conflict often?
2. What key observation does cleAR exploit?
3. How does cleAR guarantee a conflicted region commits on a single retry?
4. Predict: two workloads run under cleAR — one with tiny, hot, frequently-conflicting atomic regions that always touch the same few cachelines, and one whose atomic regions are large and access data-dependent addresses that differ each attempt. Where does cleAR help, and why?
Sources
The paper is “Bounding Speculative Execution of Atomic Regions to a Single Retry” by Eduardo Jose Gomez-Hernandez, Juan M. Cebrian, Stefanos Kaxiras, and Alberto Ros (University of Murcia and Uppsala University), published at ASPLOS 2024, DOI 10.1145/3622781.3674176.
This explainer is written from the paper’s full text (the authors’ repository copy). Mutual exclusion is a fundamental construct in parallel programs, and speculative lock elision and hardware transactional memory execute atomic regions concurrently and speculatively, ensuring correctness with conflict detection; but practical implementations are best-effort and, on conflict, retry a predetermined number of times before falling back to mutual exclusion. The paper proposes cleAR (Cacheline-locked executed Atomic Region), a hardware technique that on the first abort forces re-execution to use cacheline locking, bounding the speculative retries of a significant portion of atomic regions to one. It first establishes the conditions under which an atomic region can re-execute in cacheline-locked mode (its accessed cachelines are immutable on the retry and bounded to a small number, fewer than 32), noting that on average 60.2 percent of the regions that abort after the first attempt are immutable; by acquiring exclusive ownership of those cachelines via the cache coherence protocol, the retry cannot be interfered with and is guaranteed to commit, and the detection and conversion are transparent to software, with coordination to the fallback path for correctness. Evaluated in full-system gem5 (32 cores, Intel-Icelake-like) on data-structure benchmarks and the STAMP suite, cleAR increases the average fraction of regions that succeed on the first retry from 35.4 percent to 64.4 percent, reduces fallback (coarse-grain mutual exclusion) execution from 37.2 percent to 15.4 percent, reduces average attempts per committed region from 7.9 to 1.6 (increasing regions committed after the first try by 29.1 percent and reducing the need to fall back by 21.7 percent), and reduces average execution time by 35.0 percent over a baseline configuration and by 23.3 percent over more elaborate approaches like PowerTM. No numbers beyond the paper’s own have been introduced; exact conditions, hardware details, and full results should be confirmed in the paper.