CS Paper Radar

Do Apple M-Series Processors Enforce the Compound Memory Model? Sequential and Parallel Composition of Arm and TSO

Vijay Nagarajan

cs.AR cs.PL ·submitted 2026-11-16 17:00 UTC · v1
code/data

Abstract

Apple's M-series processors can run each thread under the Arm memory model or under a TSO model, and threads of both kinds can share memory. This raises two questions of composition that Apple has not answered. Across threads, how does the machine behave as a whole? Within a thread, which Arm instructions play the roles of TSO's loads, stores and atomic read-modify-writes, and how are they ordered between themselves and across other Arm instructions? We propose that both answers are compositions of preserved program order. Across threads, each thread keeps the preserved program order of its own model: a parallel composition. Within a TSO thread, every Arm instruction keeps TSO's order and adds Arm's, and every atomic memory operation (AMO) is locked, as x86's read-modify-writes are: a sequential composition. We test both on an Apple M1 and an Apple M2 running Linux, with 936 litmus tests chosen from the two models' preserved program order, each run 6x10^8 times on each machine. Arm-mode threads follow Arm's official model, TSO-mode threads follow x86-TSO and the sequential composition, and programs that mix the two modes follow the compound model: neither machine shows an outcome these models forbid. Both machines also preserve three orders that these models do not require, and a compare-and-swap whose comparison fails behaves as if it writes back the value it read, which the Arm model does not require. All three orders held in runs up to 40 times longer.

Comment
26 pages, 6 figures, 11 tables. Artifact: https://github.com/vijay-nagarajan/apple-tso-litmus

Closest papers

Nearest neighbours by meaning across the whole index.

TEMPO: A Tag-Based Framework for Efficient Memory Ordering

cs.AR ·2026-09-19 ·Pranith Kumar, Prasun Gera, Hyojong Kim, Chulhyung Park, Hyesoon Kim
top venue similarity 0.61
Abstract · Published at the 2026 59th IEEE/ACM International Symposium on Microarchitecture (MICRO)

Weak-memory processors rely on ordering instructions for correctness, yet conventional implementations often enforce them more conservatively than the memory model requires. This over-enforcement manifests as drain-induced retirement stalls at ordering instructions and conservative squash/replay of speculative loads, suppressing legal executions and reducing throughput. We present TEMPO, a tag-based framework for precise micro-architectural implementation of ordering instructions. TEMPO assigns lightweight ordering tags to instructions and decomposes enforcement across retirement-time predicates and completion-time store ordering, allowing the core to enforce required ordering without conservative retirement serialization. TEMPO eliminates unnecessary retirement serialization at ordering instructions and speculative-load squash/replay. In our evaluation, TEMPO reduces geometric-mean normalized execution cycles by 7.9% on native four-thread workloads and improves geometric-mean IPC by 15.9% on an instrumented SPEC2017 dynamic binary translation (DBT) proxy for cross- ISA execution (e.g., x86-on-Arm), while adding only 262 bytes per core.

0.42

Nothing Is Shared Until You Synchronise: Reinterpreting Java for Data-Race Freedom

cs.PL ·2026-11-06 ·Luke Cheeseman, Elias Castegren, David Black-Schaffer, Erik Österlund, Tobias Wrigstad
similarity 0.57
Abstract · 30 pages, 11 figures

In mainstream shared-memory languages, programmers use synchronisation mechanisms such as locks to isolate shared data accesses across threads to avoid data races. Yet synchronisation enforces only a temporal ordering, while shared memory still communicates updates between threads at every ordinary read and write. To achieve isolation, programmers therefore need to understand the connection between ordering and communication, and to apply synchronisation correctly and consistently, while compilers and hardware optimise assuming they have. When programmers synchronise incorrectly, they lose isolation, and the semantics of their programs change without notice. We propose Sync-as-Share, a memory model built on isolation and communication rather than on the ordering of accesses to shared memory. We start from thread isolation, where each thread reads and writes a private view of memory, and reinterpret programs' existing synchronisation actions to also communicate updates explicitly. As nothing is communicated outside synchronisation actions, data races become impossible by construction. Instead, conflicting updates are detected at synchronisation points. Viewing synchronisation as explicit communication exposes the design decisions of what should be communicated, to whom, and what counts as a conflict. We propose two communication topologies with different trade-offs. We instantiate Sync-as-Share for Java by making the synchronisation actions already defined by its memory model the only points at which threads communicate, so Java programs can adopt Sync-as-Share unmodified. We formalise this instantiation as version-controlled memory, in which synchronisation actions push and pull updates between private views, and mechanise it in Rocq. We show that Java programs that are correctly synchronised under the Java memory model behave identically under shared memory and Sync-as-Share.

0.24

Extending concurrent separation logic to the hardware level to verify the xv6 OS kernel on RISC-V with AI agents

cs.LO cs.OS ·2026-09-03 ·M. Frans Kaashoek, Nickolai Zeldovich
theory similarity 0.56
Abstract

MachCSL is a framework for verifying system software, such as an OS kernel, on top of low-level semantics of a RISC-V computer, based on the Sail RISC-V semantics. The key idea behind MachCSL is to adapt concurrent separation logic, based on Iris, to reasoning about low-level hardware execution at the sub-instruction level: page-table translation, TLB, privilege levels, configuration registers, instruction fetch/decode/execute, traps and interrupts, DMA, shared memory, power failures, etc. Reasoning at this level of detail ensures that the system software correctly manages all of the hardware details. Verifying software at this low level of abstraction is tedious, but LLM-based agents are capable of reasoning about such low-level details. As a case study, we verify the xv6 OS kernel (6,657 lines of C and assembly code), which provides a traditional Unix system call interface (processes, file system, file descriptors, and preemptive scheduling) and has substantial internal concurrency (multi-core support with fine-grained locking, shared memory, interrupts, DMA, etc.). In the verification process, we uncovered 11 bugs in the xv6 implementation, as well as one bug in the Sail RISC-V semantics, and one bug in Sail's Lean extraction. The verification effort took us 102 days, including the time to develop the MachCSL framework. On top of the verified xv6 kernel, we prove a theorem about console-level behavior: e.g., if the user types echo hello world as input on the UART console, the only output the system can produce is hello world (if there are no crashes or other errors). This theorem covers both the kernel and the init, sh, echo, cat, grep, sync, and seccomp binaries in the initial file system image.

0.50

How Weight Encoding Affects Language Model Placement and Performance on the Apple Neural Engine

cs.LG cs.ARcs.PF ·2026-08-22 ·Shahir M A
similarity 0.55
Abstract · 10 pages, 2 figures, 7 tables. v2: corrected byte-traffic accounting, withdrew the 0.77 nominal-byte factor, and attributed normalization el…

Weight compression can alter accelerator placement as well as memory traffic, complicating the interpretation of inference speedups. We investigate this interaction on the Apple Neural Engine through the public Core ML deployment path. Five independently trained language-model checkpoints span two architectures and dense fp16, int8, and ternary weights encoded with two-bit lookup tables. We combine compiler device plans, synchronized memory-controller measurements, and compute-unit exclusion controls for a fixed single-token forward workload. On an M1, the smaller fp16 export executes on the CPU despite permitting ANE execution, whereas its compressed counterparts exhibit ANE activity. The int8 export reduces warm forward latency by a factor of 1.9. The larger fp16 export also uses the ANE, indicating that dense encoding alone does not determine placement. Separate M3 energy measurements support the same direction of change. These results establish encoding-dependent placement in the measured deployment stack and show that compression comparisons require joint measurement of backend selection, latency, and traffic.

0.20

Episodic Loops: Finitary Event Structures and Operational Semantics for C11 Programs with Retries

cs.PL ·2026-09-28 ·Christian Kissig, Jay Richards, Mark Batty
code/data similarity 0.55
Abstract · 115 pages (42 pages main text plus appendices), 19 figures, 2 tables. Reference implementation: https://github.com/christiankissig/mordor ; …

Lock-free synchronisation algorithms are often implemented with fallible operations, such as compare-and-swap (CAS), wrapped in unbounded retry loops. Verifying such algorithms requires considering arbitrarily many failing iterations, yielding large state spaces, compounded by the interleavings of concurrent threads. Prior work discarded failing iterations, arguing that they leave no trace in the post-loop state. Compilers and hardware reorder instructions, and load-store reorderings may cross the boundaries of failing iterations, introducing subtle concurrency bugs. We demonstrate one such bug, making use-after-free possible in a previously verified variant of Read-Copy-Update - a synchronisation primitive widely adopted in the Linux Kernel - and we provide and verify a fix. We find that practical retries in lock-free algorithms adhere to a common pattern. We introduce episodic loops, a semantic characterisation of unbounded retry loops which is syntactically recognisable in many practical cases, and synchronisation points, operations that bound both instruction reordering and state space within episodic loops. We show that SMRD - a symbolic event structure semantics for C11 programs which allows for load-store reordering - admits a finite representation in programs where unbounded loops are episodic. We further introduce a finitary operational semantics that allows safety properties to be verified in finitely many steps. For the use-after-free bug we demonstrate, verification takes a single pass over the program, linear in the program size. We provide a reference implementation of SMRD reproducing the bug and verifying the fix, and mechanise the operational semantics together with the minimal bug and its fix in Isabelle/HOL.

0.38

Byzantine-linearizable Single-Writer Multi-Reader Register in the GPU-Inspired Shared Memory Model

cs.DC ·2026-10-10 ·Chryssis Georgiou, Sathya Peri, Manaswani Piduguralla, Yashi Rastogi
similarity 0.53
Abstract

The construction of fault-tolerant atomic registers is a fundamental problem in distributed computing. GPUs, widely used in scientific computing and machine learning, face Byzantine thread behaviour, while their shared memory lacks access control, allowing any thread to modify shared objects. This raises the question of whether atomic register semantics can be maintained when any thread, including the designated writer, may behave Byzantine. We study this problem in the GPU-inspired shared-memory model of Georgiou et al. and present implementations of a Byzantine-linearizable single-writer multi-reader (SWMR) register. CAReg uses constant memory with a quantifiable probability of invalid reads, while SnapObject maintains a bounded window of authenticated writes, eliminating invalid reads and tolerating up to \(n-1\) Byzantine processes through lock-free and wait-free variants. Our results demonstrate how GPU phase-based, lock-step execution can partially compensate for the absence of access control.

0.23

A Unifying Metatheorem on Weak-Memory Robustness

cs.PL cs.LO ·2026-11-17 ·Giovanna Kobus Conrado, Stephan Spengler, Mohamed Faouzi Atig, Andreas Pavlogiannis
theory similarity 0.53
Abstract

Memory models specify the behaviors that concurrent programs may exhibit under compiler and hardware optimizations, which often deviate from Sequential Consistency (SC). Robustness is the property of a program P not exhibiting any weak behaviors when executing under a weak memory model MM, compared to SC. As such, the algorithmic problem of deciding whether $P$ is robust against MM has been studied extensively, and has been repeatedly shown to be in PSPACE for many memory models, such as TSO, PSO, and Release/Acquire. However, each model has required its own, dedicated proof, raising the natural question of whether robustness admits a unifying treatment across memory models. In this work, we answer this question affirmatively for a broad class of memory models definable in Kleene Algebra with Tests (KAT). We prove that robustness against any prefix-closed, KAT-definable memory model is in PSPACE. This metatheorem recovers nearly all prior PSPACE robustness results, and establishes PSPACE membership for several new models, including the full RC11 and the OCaml memory model. We have further formalized the correctness of our approach in Lean. On the other hand, we prove that robustness against the KAT-definable Relaxed model is undecidable, and thus prefix-closedness cannot be dropped, in general. Finally, we implement our algorithm in a prototype tool RoboKAT, and demonstrate its flexibility by checking robustness against nine memory models, several of which are not handled by prior work.

0.34

Where the SRAM Goes: Per-Symbol Attribution of Static Memory in FreeRTOS-C and Embassy-Rust IoT Firmware on a 64 KB RISC-V Microcontroller

cs.OS cs.ARcs.SE ·2026-10-15 ·Romi Fadli, Jan Everhard Riwurohi, Wahyu Ramadani Putri Utami, Zulfa Malika Amana
similarity 0.52
Abstract · 13 pages, 5 figures, 10 tables. Submitted to SN Computer Science

Selecting a firmware stack for a memory-constrained microcontroller is usually guided by aggregate binary sizes, which report how much SRAM a build consumes but not where it goes or why. We address that gap with a per-symbol attribution method that decomposes static RAM into architectural categories - scheduler heap, network buffers and pools, task stacks, and linker-reserved regions - by bounding sized ELF symbols to the .data, .bss and .stack section ranges. The method is validated by reconciling every category sum exactly against the size-based totals for all sixteen builds. We apply it to eight cumulative firmware milestones, from a bare task scaffold to a full MQTT-over-Ethernet client, implemented twice, in FreeRTOS-C and in Embassy-Rust, on the CH32V203RBT6, a RISC-V microcontroller with 64 KB SRAM and an on-chip Ethernet MAC and PHY, with functional parity verified on hardware at every milestone. The decomposition shows that both stacks spend a nearly identical share of their RAM on networking (63.8% versus 63.9%), yet the absolute cost differs by 4.4 times: 40,719 bytes for lwIP against 9,316 bytes for smoltcp. FreeRTOS task stacks grow linearly at roughly 1 KB per task while Embassy async state grows with state-machine complexity. We also report that lwIP could not be integrated under an all-static discipline on this platform, requiring a 20 KB arena that smoltcp does not. The measurement harness, the attribution tool, and the sixteen firmware implementations are released as artefacts.

0.39