Transactional memory
In
Motivation
In concurrent programming, synchronization is required when parallel threads attempt to access a shared resource. Low-level thread synchronization constructs such as locks are pessimistic and prohibit threads that are outside a critical section from running the code protected by the critical section. The process of applying and releasing locks often functions as an additional overhead in workloads with little conflict among threads. Transactional memory provides optimistic concurrency control by allowing threads to run in parallel with minimal interference.[2] The goal of transactional memory systems is to transparently support regions of code marked as transactions by enforcing atomicity, consistency and isolation.
A transaction is a collection of operations that can execute and commit changes as long as a conflict is not present. When a conflict is detected, a transaction will revert to its initial state (prior to any changes) and will rerun until all conflicts are removed. Before a successful commit, the outcome of any operation is purely speculative inside a transaction. In contrast to lock-based synchronization where operations are serialized to prevent data corruption, transactions allow for additional parallelism as long as few operations attempt to modify a shared resource. Since the programmer is not responsible for explicitly identifying locks or the order in which they are acquired, programs that utilize transactional memory cannot produce a deadlock.[2]
With these constructs in place, transactional memory provides a high-level programming abstraction by allowing programmers to enclose their methods within transactional blocks. Correct implementations ensure that data cannot be shared between threads without going through a transaction and produce a
def transfer_money(from_account, to_account, amount):
"""Transfer money from one account to another."""
with transaction():
from_account.balance -= amount
to_account.balance += amount
In the code, the block defined by "transaction" is guaranteed atomicity, consistency and isolation by the underlying transactional memory implementation and is transparent to the programmer. The variables within the transaction are protected from external conflicts, ensuring that either the correct amount is transferred or no action is taken at all. Note that concurrency related bugs are still possible in programs that use a large number of transactions, especially in software implementations where the library provided by the language is unable to enforce correct use. Bugs introduced through transactions can often be difficult to debug since breakpoints cannot be placed within a transaction.[2]
Transactional memory is limited in that it requires a shared-memory abstraction. Although transactional memory programs cannot produce a deadlock, programs may still suffer from a livelock or resource starvation. For example, longer transactions may repeatedly revert in response to multiple smaller transactions, wasting both time and energy.[2]
Hardware vs. software
The abstraction of atomicity in transactional memory requires a hardware mechanism to detect conflicts and undo any changes made to shared data.
Owing to the more limited nature of hardware transactional memory (in current implementations), software using it may require fairly extensive tuning to fully benefit from it. For example, the dynamic memory allocator may have a significant influence on performance and likewise structure padding may affect performance (owing to cache alignment and false sharing issues); in the context of a virtual machine, various background threads may cause unexpected transaction aborts.[10]
History
One of the earliest implementations of transactional memory was the gated store buffer used in Transmeta's Crusoe and Efficeon processors. However, this was only used to facilitate speculative optimizations for binary translation, rather than any form of speculative multithreading, or exposing it directly to programmers. Azul Systems also implemented hardware transactional memory to accelerate their Java appliances, but this was similarly hidden from outsiders.[11]
In 2009, AMD proposed the Advanced Synchronization Facility (ASF), a set of x86 extensions that provide a very limited form of hardware transactional memory support. The goal was to provide hardware primitives that could be used for higher-level synchronization, such as software transactional memory or lock-free algorithms. However, AMD has not announced whether ASF will be used in products, and if so, in what timeframe.[11]
More recently,
As of GCC 4.7, an experimental library for transactional memory is available which utilizes a hybrid implementation. The PyPy variant of Python also introduces transactional memory to the language.
Available implementations
- Hardware:
- Software:
See also
- Memory semantics
- Automatic mutual exclusion
References
- ISSN 1935-3235.
- ^ a b c d "Transactional Memory: History and Development". Kukuruku Hub. Retrieved 2016-11-16.
- ^ ISBN 978-1-4822-1118-4.
- ^ a b Herlihy, Maurice; Moss, J. Eliot B. (1993). "Transactional memory: Architectural support for lock-free data structures" (PDF). Proceedings of the 20th International Symposium on Computer Architecture (ISCA). pp. 289–300.
- S2CID 11017196.
- .
- ISBN 0-7695-2275-0.
- ^ "LogTM: Log-based transactional memory" (PDF). WISC.
- ^ "The ATOMOΣ Transactional Programming Language" (PDF). Stanford. Archived from the original (PDF) on 2008-05-21. Retrieved 2009-06-15.
- ISBN 978-1-4799-0555-3.
- ^ a b c d e David Kanter (2012-08-21). "Analysis of Haswell's Transactional Memory". Real World Technologies. Retrieved 2013-11-19.
- ^ "Arm releases SVE2 and TME for A-profile architecture - Processors blog - Processors - Arm Community". community.arm.com. 18 April 2019. Retrieved 2019-05-25.
- ^ "Transactional Memory Extension (TME) intrinsics". Retrieved 2020-05-05.
- ^ "IBM plants transactional memory in CPU". EE Times.
- ISBN 978-0-7384-3972-3.
- ^ Wei Li, IBM XL compiler hardware transactional memory built-in functions for IBM AIX on IBM POWER8 processor-based systems
- ^ "Power ISA Version 3.1". openpowerfoundation.org. 2020-05-01. Retrieved 2020-10-10.
- YouTube
- ^ "Control.Monad.STM". hackage.haskell.org. Retrieved 2020-02-06.
- ^ "STMX Homepage".
- ^ Wong, Michael. "Transactional Language Constructs for C++" (PDF). Retrieved 12 Jan 2011.
- ^ "Brief Transactional Memory GCC tutorial".
- ^ "C Dialect Options - Using the GNU Compiler Collection (GCC)".
- ^ "TransactionalMemory - GCC Wiki".
- ^ Rigo, Armin. "Using All These Cores: Transactional Memory in PyPy". europython.eu. Retrieved 7 April 2015.
- ^ "picotm - Portable Integrated Customizable and Open Transaction Manager".
- ^ "Concurrent::TVar".
Further reading
- Harris, Tim; Larus, James R.; Rajwar, Ravi (December 2010), Transactional Memory, 2nd edition, Synthesis Lectures on Computer Architecture, vol. 5, Morgan & Claypool, pp. 1–263,
- McKenney, Paul E.; Michael, Maged M.; Triplett, Josh; Walpole, Jonathan (July 2010). "Why the grass may not be greener on the other side: a comparison of locking vs. transactional memory". SIGOPS Oper. Syst. Rev. 44 (3). New York, NY, USA: S2CID 1917393.
- Dave Dice, Yossi Lev, Mark Moir, Dan Nussbaum, and Marek Olszewski. (2009) "Early experience with a commercial hardware transactional memory implementation." Sun Microsystems technical report (60 pp.) SMLI TR-2009-180. A short version appeared at ASPLOS’09
- Amy Wang, Matthew Gaudet, Peng Wu, José Nelson Amaral, Martin Ohmacht, Christopher Barton, Raul Silvera, and Maged Michael. "Evaluation of Blue Gene/Q hardware support for transactional memories Archived 2013-06-27 at the Wayback Machine". In Proceedings of the 21st international conference on Parallel architectures and compilation techniques, pp. 127–136. ACM, 2012.
- Jacobi, C., Slegel, T., & Greiner, D. (2012, December). "Transactional memory architecture and implementation for IBM System z Archived 2016-03-04 at the Wayback Machine". In Microarchitecture (MICRO), 2012 45th Annual IEEE/ACM International Symposium on (pp. 25–36). IEEE.
- Harold W. Cain, Maged M. Michael, Brad Frey, Cathy May, Derek Williams, and Hung Le. "Robust Architectural Support for Transactional Memory in the Power Architecture." In ISCA '13 Proceedings of the 40th Annual International Symposium on Computer Architecture, pp. 225–236, ACM, 2013.
External links
- Michael Neuling (IBM), "What's the deal with Hardware Transactional Memory!?!" introductory talk at linux.conf.au 2014
- Transactional Memory Online: Categorized bibliography about transactional memory