Arm Community
Arm Community
  • Site
  • User
  • Site
  • Search
  • User
Research Collaboration and Enablement
Research Collaboration and Enablement
Research Articles Concurrent Programming, Transactions and Weak Memory
  • Research Articles
  • Arm Research - Most active
  • Arm Research Events
  • Members
  • Mentions
  • Sub-Groups
  • Tags
  • Jump...
  • Cancel
Research Collaboration and Enablement requires membership for participation - click to join
More blogs in Research Collaboration and Enablement
  • Research Articles

Tags
  • Arm Research
  • Architecture
  • Security
  • Memory
  • Computer Architecture
Actions
  • RSS
  • More
  • Cancel
Related blog posts
Related forum threads

Concurrent Programming, Transactions and Weak Memory

Nathan Chong
Nathan Chong
July 9, 2018
3 minute read time.

This is the first in a two-part post from Arm Principal Researcher Dr Nathan Chong on his joint research with Tyler Sorensen (Imperial College London) and Dr John Wickerson (Research Fellow, Imperial College London). This research was published as a PLDI 2018 Distinguished Paper: 'The Semantics of Transactions and Weak Memory in x86, Power, Arm, and C++'. In this post, we introduce the ideas of transactions and weak memory in the context of concurrent programs.

"Concurrency is about dealing with lots of things at once." (Pike, Concurrency is not Parallelism)

Karlheinz Stockhausen’s "Gruppen" is a piece of music involving three orchestras and over one hundred musicians, at the same time! Simon Rattle, one of the conductors interviewed in a June 29, 2018 New York Times article about performing this piece, remarks: "Each orchestra is very complicated on its own, but when you put the three together, it’s like this dizzying tessellation of rhythms and sounds." The challenge is in "coordinating all these desperately complicated rhythms and cues, and not losing your head." What a great description of the challenges of concurrent programming too!

Concurrent Programming

Concurrent programming is about the useful interaction of multiple processes over shared resources. Here is a simple example. Imagine you have a bank account with £100 inside. Today, (1) you'll be paid £100 but (2) you also need to withdraw £100. In other words, your bank account should finish the day even at £100.

But what if each account update is split into two actions: (a) reading the balance and (b) writing the balance; and furthermore, the bank interleaves the actions like so:

(1a) Reads current balance of £100
(2a) Reads current balance of £100
(1b) Adds £100 and writes a balance of £200
(2b) Subtracts £100 and writes a balance of £0!

Something has gone terribly wrong! The problem is the interleaving of the actions of the account updates. We need the updates to be atomic so that all the actions of one account update are indivisible with respect to other account updates. In this case, we are concerned with the useful interaction (ensuring atomicity) of multiple processes (account updates) over shared resources (our bank account).

It turns out that ensuring atomicity is just one of the challenges that we face when programming concurrently. The fundamental difficulty is that concurrent programs can have many behaviors due to subtle interactions between multiple components; and the programmer must reason about all of these possible behaviors. Lu et al. (ASPLOS 2008) give a detailed discussion of concurrency problems that occur in real-world codebases.

Transactions and Weak Memory

"A transaction is a sequence of actions that appears indivisible and instantaneous to an outside observer." (Harris et al., Transactional Memory)

"Although the question of how consistent memory must be seems simple, it is remarkably complicated." (Hennessy and Patterson, Computer Architecture: A Quantitative Approach)

The architecture of a computer is the foundational contract between hardware and software: the envelope of behavior that all hardware must conform to, and hence, all software can rely on. So, the concurrency model of an architecture defines the concurrent behavior that software can rely on. Transactions and weak memory are two potential features of this concurrency model.

  • Transactions are a sequence of machine instructions that guarantee atomicity and other properties, such as isolation, in order to give the programmer an easier interface, similar to that of a database, for concurrent programming. The idea is to avoid the complexities of fine-grain locking and rely on the optimistic concurrency of transactions for correctness and performance.
  • Weak memory (also known as memory consistency) is the specification that governs the ordering requirements of load and store instructions, which may differ from the order specified by the programmer. This is the case for several architectures, including x86, Power, and Armv8.

What makes these two characters interesting to study together is that their aims are at odds with one another. Transactions want to make your life as a programmer simpler whereas weak memory demands that you understand how the machine may reorder your code. We can characterise this tension by saying that transactions reduce the behaviours of a concurrent program (and therefore make reasoning about the program easier); whereas weak memory increase the behaviors (and therefore make reasoning about the program harder).

Each of these features, individually, is complex. How can we deal with the complexity when they are combined? Read my next post where we tackle this problem.

Anonymous
Research Articles
  • HOL4 users' workshop 2025

    Hrutvik Kanabar
    Hrutvik Kanabar
    Tue 10th - Wed 11th June 2025. A workshop to bring together developers/users of the HOL4 interactive theorem prover.
    • March 24, 2025
  • TinyML: Ubiquitous embedded intelligence

    Becky Ellis
    Becky Ellis
    With Arm’s vast microprocessor ecosystem at its foundation, the world is entering a new era of Tiny ML. Professor Vijay Janapa Reddi walks us through this emerging field.
    • November 28, 2024
  • To the edge and beyond

    Becky Ellis
    Becky Ellis
    London South Bank University’s Electrical and Electronic Engineering department have been using Arm IP and teaching resources as core elements in their courses and student projects.
    • November 5, 2024