This is a report of the research done by Vadym Musiienko as a SURP RA during the summer of 2026.

Mirakuru: Software-Hardware Co-Design for Highly Concurrent Heterogeneous CXL Lock-Free Data Structures

The Problem

DRAM is one of the largest and fastest-growing costs in the datacenter. A DIMM’s useful lifetime exceeds a typical server refresh cycle, yet it is decommissioned with the host. And DIMM slots are designed for the most current DDR generation, stranding functional older modules. The result is stranded capacity and avoidable embodied carbon. A state-of-the-art solution to this financial and environmental cost is Compute Express Link (CXL), which enables flexible memory expansion and the reuse of decommissioned DIMMs. A standard setup exposes a remote pool of heterogeneous memory to the operating system as a CPU-less (zNUMA) node, shown in the figure below.

A zNUMA node is a NUMA node that carries memory but no CPU of its own, so the host reaches across CXL purely to load and store data in that pool.

Why Lock-Free Structures Struggle on CXL

However, CXL memory is slower than local DRAM, so concurrent data structures placed on it, such as hash tables and skip lists, can degrade an application’s quality of service (QoS). These structures rely on compare-and-swap (CAS), which updates a shared location only if it still holds the value the thread last read.

Here is what that means in practice. A thread reads a shared location, decides what it wants to write, and then asks the hardware to write the new value only if the location still holds the value it read a moment ago. If another thread got there first and changed it, the CAS fails and the losing thread has to start its operation over.

Figure below illustrates how such an update can fail, forcing thread 1 into its fallback path, where it must redo its find(B) call to recover the true prev and curr. Picture two threads working on a linked list. Thread 1 walks the list to find where its new node belongs, landing on a prev and a curr. Before it can splice its node in, Thread 2 deletes curr, so prev no longer holds what Thread 1 expects, and its CAS fails.

CXL’s higher latency extends the contention window between a thread’s read and its update, letting more threads collide on the same data. The two heatmaps below (local memory and conventional CXL) show that CAS success on the slower, remote CXL memory falls below local by up to 8.4% in the most contended configurations, so non-blocking applications hit their fallback paths more often. Every one of those failures is a thread throwing away work and redoing it.

The Idea: Expose the Heterogeneity

How often an object’s CAS succeeds depends on which device holds it, because the pool mixes devices of different latencies. Yet the CXL interface as constructed today is needlessly restrictive. By presenting the pool as uniform memory, it prevents the programmer from placing the most contended data on the fastest device. Our proposed co-design exposes the heterogeneity the interface hides.

The rest of the work is making that heterogeneity visible in a way software can act on, and it starts down in the memory controller.

Building the Controller in gem5

At boot, our CXL controller initializes the connection to each attached device; the handshake reports that device’s timing characteristics, from which the controller derives a priority ordering over the pool, fastest first. It then maps physical addresses to devices on demand: when a request arrives for an address that has not been mapped yet, the controller binds that address to the fastest device with capacity remaining.

A few details are worth spelling out. Because the ordering comes straight from the boot handshake, the controller already knows that DDR5 beats DDR4 beats DDR3 before a single memory request arrives. The mapping is sticky: once an address lands on a device it stays there. Addresses are bound in the order they are first touched, not by their numeric value, so the earliest-touched addresses get the fastest memory and later ones fall through the tiers in speed order as each device fills. That is what later lets software reason about placement: an allocation that reserves the pool and walks it in order sees the devices laid out fastest-first, so a device’s speed rank corresponds to a known slice of the reservation.

The controller ships with three placement strategies, selected by a parameter. direct passes physical addresses through to the pool untouched, which is what a conventional CXL controller does. random assigns each newly touched cache line to a random device, our baseline. speed is Mirakuru’s fastest-first mapping described above.

The Controller as a Simulated Device

The controller lives in three files. src/mem/CXLcontroller.py declares its parameters to the configuration layer, src/mem/cxl_controller.cc holds the C++ that does the work, and src/python/gem5/components/memory/cxl_memory.py wraps it in a memory component that any board can accept in place of ordinary DRAM. The board attaches to the controller and sees one flat range of memory. Behind it sit the individual devices, each with its own DRAM timing model, and the board never learns they exist.

gem5 does not have one way of accessing memory. It has three, and a full-system run uses all of them, so the controller has to implement all three.

• Functional accesses are used to set memory up: loading the kernel and disk image, and debugger reads. They are not supposed to take any simulated time.
• Atomic accesses serve the fast-forward cores that boot Linux. There is no scheduling here, so the call has to return a latency on the spot.
• Timing accesses are the real ones, used once the region of interest switches to cycle-accurate cores. A request is sent now and the response comes back later.

All three share the same address translation. What differs is how packets are handled, and that difference is a trade-off. Functional and atomic accesses are synchronous, so the controller rewrites the address on the caller’s own packet and passes the same object along, which costs nothing. Timing requests outlive the call, so the controller has to allocate a copy carrying the device address, keep a record tying it back to the original, and reunite them when the response arrives. Copying every packet is real overhead, but only the timing path pays it, and the timing path is the only one whose numbers I report.

Controller Latency

CXL memory is slower than local DRAM, and the controller has to add that delay itself. Its latency is a parameter, exposed up to a command-line flag on the config script, so sweeping it needs no recompile. It is specified as a round trip and applied half on the way to memory and half on the way back, so the number in the config is the number you would measure on a real link.

In timing mode there is nothing to return a latency to, so the controller schedules. It holds requests and responses in queues stamped with the tick at which each is allowed to leave, and wakes itself at that tick to pass the packet on. If the component downstream is busy and refuses a packet, the controller waits to be told to retry rather than spinning, and once unblocked it releases anything whose deadline has already passed.

The queues are unbounded, so the controller never pushes back on the CPU no matter how much traffic arrives. That is a deliberate simplification: it models the link’s delay and not its bandwidth. This study is about how latency stretches the contention window between a thread’s read and its CAS, so leaving bandwidth out keeps one variable in the experiment instead of two.

Fragmentation

The direct strategy models a conventional CXL controller, and on a freshly simulated pool it flatters one. Pass physical addresses through untouched and a contiguous allocation lands contiguously, so the benchmark’s array sits on whichever device happens to back that stretch of the address space, and often on that one device alone. It never spans the pool, so it never sees the heterogeneity the study is about. Real pools do not look like that. Memory is allocated and freed over a machine’s life, and a large allocation ends up spread across whatever holes are left, spanning devices. Without fragmentation the baseline is not a baseline.

My first version produced it honestly, from inside the benchmark itself. Before touching the CAS array, the program allocated the entire pool in small blocks, wrote to each one to force the controller to map it, then freed a configurable percentage at random. Whatever the benchmark allocated afterwards fell into those holes, the same way a real allocator would be forced to.

It worked, and it was far too slow. Every one of those writes is a simulated store. Touching the whole pool a small block at a time means the benchmark drives the entire memory through the controller, one cache line at a time and all of it through the full timing model, before it performs a single real operation. Runs that should have taken minutes did not finish.

The fix was to notice what I actually needed. The guest never had to produce a fragmented layout. The controller only had to start from one, and it can build that in host code at construction, before any simulated time passes.

So I deleted the benchmark-side version and made fragmentation a property of the controller. It divides the pool into fixed-size granules, picks a random subset of them, and permutes their addresses among themselves. The percentage of granules disturbed is a parameter: at 100 the entire pool is shuffled, at 40 a randomly chosen 40% trade places while the rest stay put, and at 0 the controller skips the work entirely and passes every request straight through untouched. A seed parameter fixes the permutation so a sweep over thread counts and array sizes compares like with like. On the request path the whole mechanism reduces to one array lookup.

The trade-off is that this models fragmentation rather than reproducing it. A real system fragments at page granularity, through the interaction of a kernel allocator, a user-space allocator, and a workload’s allocation history. Mine imposes the scatter from below, at a granularity I choose. It gives the experiment the property it depends on, which is that a contiguous run of physical addresses lands on devices of different speeds in proportions I control. It does not claim to reproduce any particular allocator’s behavior.

A fragmented run now costs the same wall-clock time as an unfragmented one, because the controller does the same amount of simulated work in both.

The Address Map

The random and speed strategies pick a device the first time an address is touched and have to remember that choice for the rest of the run. The obvious structure is a hash map: constant lookup, constant insert, and memory proportional to what the workload actually touches rather than to the size of the pool. That is what I wrote first.

It turned out to be the wrong choice. The map is consulted on every memory access in the simulation, and it grows to millions of entries as the guest’s footprint expands. Constant time here hides a hash, a modulo by a load factor, a bucket lookup, and a pointer chase through a structure far too large to sit in any host cache, plus a rehash of everything each time the table outgrows itself. So the simulation got slower as the pool filled, and the slowdown was worst in the large-pool configurations I most wanted to measure.

I replaced it with a flat array. The pool’s size is known before the simulation starts and every request is cache-line aligned, so the map can be one array slot per cache line, allocated once and pre-filled with a sentinel meaning “not yet assigned.” An index computation replaces the hash, and a lookup becomes one memory read with no indirection.

The trade-off is memory for speed, paid up front. The array is sized for the entire pool whether the workload touches all of it or none of it, which costs about 12% of the pool’s size in host RAM. A hash map would have used a fraction of that for a sparsely touched pool. I took the memory hit because simulation wall-clock time was the binding constraint on how many configurations I could sweep, and host RAM was not.

One more detail keeps the array small: it stores one entry per cache line rather than one per address. The low bits of an incoming address are split off before the lookup and added back to the device address afterwards, so a narrow request still lands on the correct byte without the map ever holding an entry for it.

Fixing the x86 Board

Both maps index by address, and on x86 that turns out not to be a matter of dividing by the block size, because the guest’s physical address space has a hole in it. The region between 3 GiB and 4 GiB is reserved for memory-mapped I/O, so on a machine with more than 3 GiB of RAM the memory sits on both sides of a gap that nothing backs. Indexing naively would have sized my array for the hole as well and wasted a slot for every address in it. Instead the controller walks its device ranges and collapses them into a dense index space, so the map has no entries for addresses no device serves. The same routine runs in reverse to turn an index back into a real device address, which is what the fragmentation shuffle uses, and both maps share it by passing in the granularity they care about.

Getting that far meant fixing gem5 itself. X86Board, the board model for full-system x86, refuses to be configured with more than 3 GiB of memory. It throws an exception and names the I/O hole as the reason, which is a hard ceiling for a project about large memory pools.

The board was closer to working than the exception suggested. I removed the ceiling in src/python/gem5/components/boards/x86_board.py and taught the board to split memory around the hole, putting everything up to 3 GiB below it and the remainder above 4 GiB. Two further things were broken underneath, both of which had to be fixed before a larger machine would boot and see all of its memory.

None of this is CXL work, but the fix is general: any gem5 user who wants a full-system x86 machine with more than 3 GiB of RAM needs it.

Testing It: The Benchmark

We evaluate the co-design on a highly concurrent array of atomic elements on which we perform CAS operations.

We implement the controller in gem5 and run the benchmark in full-system mode on a simulated x86 Linux host with 64 cores. Its cores are cacheless and it uses no local memory, so every access reaches the pool, isolating the controller’s impact. The pool comprises three devices, fastest to slowest: DDR5, DDR4, and DDR3.

The cacheless, no-local-memory setup is deliberate: with no cache to hit and no fast local read to fall back on, every mapping decision the controller makes lands in the numbers. We sweep two knobs, the thread count and the array size, because their ratio sets the level of contention. We also draw accesses from a Zipfian distribution, so a small set of hot elements absorbs most of the traffic, the way real keys do.

As an upper bound, we run the same host with a single local DDR5 device. Our baseline is the same pool under random placement, assigning each cache line to a random device.

Results

Figure below reports the CAS success rate under our fast-priority CXL controller. We define the high-contention cases to be those in which the number of threads exceeds the size of the array, where placement matters most. Across them, the controller improves the success rate by as much as 7.1 and by 4.2 percentage points on average over the baseline, a relative gain of up to 25.5%. From this we conclude that CXL-awareness can improve application performance.

Read the three heatmaps together: local DDR5 sets the ceiling, conventional CXL sits well under it in the high-contention corner, and Mirakuru pulls the pool back toward local without any help from the application yet.

What’s Next

As future work, we propose a topology-aware allocator built on this controller. It reserves the entire pool in one contiguous allocation, and because the controller maps fastest-first, each device occupies a known, speed-ordered range within it. Our malloc then takes a size and a target device by speed rank, serving the block from that device and falling back to the next fastest when it is full. This gives the programmer the device-level placement the standard CXL interface hides, keeping hot data on fast memory and cold data on slow.

We also plan to deploy Mirakuru in the state-of-the-art non-blocking concurrent indices of the Synchrobench suite. Presampling the Zipfian key distribution, we place the most popular keys on the fastest device, keeping the hot set on fast memory and the cold tail on slower devices. The work in this study provides strong motivation that this approach will improve their performance as well, especially under contention-aware placement.