Arm Community
Arm Community
  • Site
  • User
  • Site
  • Search
  • User
  • Groups
    • Arm Research
    • DesignStart
    • Education Hub
    • Innovation
    • Open Source Software and Platforms
  • Forums
    • AI and ML forum
    • Architectures and Processors forum
    • Arm Development Platforms forum
    • Arm Development Studio forum
    • Arm Virtual Hardware forum
    • Automotive forum
    • Compilers and Libraries forum
    • Graphics, Gaming, and VR forum
    • High Performance Computing (HPC) forum
    • Infrastructure Solutions forum
    • Internet of Things (IoT) forum
    • Keil forum
    • Morello Forum
    • Operating Systems forum
    • SoC Design and Simulation forum
    • 中文社区论区
  • Blogs
    • AI and ML blog
    • Announcements
    • Architectures and Processors blog
    • Automotive blog
    • Graphics, Gaming, and VR blog
    • High Performance Computing (HPC) blog
    • Infrastructure Solutions blog
    • Innovation blog
    • Internet of Things (IoT) blog
    • Mobile blog
    • Operating Systems blog
    • Research Articles
    • SoC Design and Simulation blog
    • Smart Homes
    • Tools, Software and IDEs blog
    • Works on Arm blog
    • 中文社区博客
  • Support
    • Open a support case
    • Documentation
    • Downloads
    • Training
    • Arm Approved program
    • Arm Design Reviews
  • Community Help
  • More
  • Cancel
Arm Research
Arm Research
Research Articles Concurrent Programming, Transactions and Weak Memory
  • Research Articles
  • Leaderboard
  • Resources
  • Arm Research Events
  • Members
  • Mentions
  • Sub-Groups
  • Tags
  • Jump...
  • Cancel
Arm Research requires membership for participation - click to join
More blogs in Arm Research
  • 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

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
  • How about a short walk?

    Ilias Vougioukas
    Ilias Vougioukas
    Current solutions to improve virtual to physical translation performance are impractical. We present an alternative, where a small change has a significant impact.
    • March 10, 2022
  • SpiNNaker: Next-level thinking

    Charlotte Christopherson
    Charlotte Christopherson
    SpiNNaker1 connected a million mobile phone processors, operating in some ways like a brain. SpiNNaker2 will drive the next generation of AI.
    • January 31, 2022
  • Sparking potential for community development: Arm Education Kits now available on GitHub

    Dipesh Patel
    Dipesh Patel
    University Program materials are now even easier to access via GitHub. Use our resources, tools and more to spark the potential of your students.
    • January 24, 2022