Contents
Atomic section (pessimistic concurrent control)
Some useful information on transactions can be
obtained from the links below:
http://www.cs.wisc.edu/trans-memory/biblio/index.html
http://www.cs.washington.edu/homes/djg/publications.html
1.
Herb Sutter and James Larus. Software
and the concurrency revolution. ACM Queue, 3(7):54~62, Sep. 2005.
[
Paper: pdf ]
2.
Ali-Reza Adl-Tabatabai,
Christos Kozyrakis, Bratin Saha. Unlocking concurrency.
ACM Queue, 4(10), pages 24-33,
December/January 2006-2007. [
Paper: pdf ]
The papers listed below mainly focus on
transactions implementation classified into three categories: software
transaction memory (STM) ,hardware transaction memory (HTM) and hybrid
transaction memory(HYTM)
Michael
L. Scott Virendra J. Marathe (RSTM)
Maurice Herlihy
(DSTM&DSTM2)
3. Nir Shavit and Dan Touitou. Software transactional memory. In Proceedings
of 14th Annual ACM
Symposium on Principles
of Distributed Computing(PDC’95),
pages 204-213, 1995. [ Paper: pdf ] (First paper of STM)
[Description] Propose the concept of software transaction memory; give an
implementation based on k-word compare&swap.
4.
M. Herlihy, V. Luchangco, and
M. Moir. A flexible framework for
implementing software transactional memory. In OOPSLA 2006. [ Paper: pdf ]
[Description] This paper describe DSTM2, a software
library that provides a framework for implementing object-based STM. It uses
transactional factories to transform sequential classes into atomic ones and
also provides several organizations of shared objects, such as obstruct-free
and shadow.
5. Virendra
J. Marathe, William N. Scherer III, and Michael L. Scott. Adaptive software transactional memory. In Proceedings of 19th International Symposium on Distributed Computing(DISC’05),
[Description] This paper presents an Adaptive
STM (ASTM) system which is more flexible than
DSTM or OSTM; it can be adjusted to the offered workload for its methods of
versioning and conflict detection.
6. Maurice
Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer III. Software
transactional memory for dynamic-sized data structures. In Proceedings of 22nd ACM Symposium on
Principles of Distributed Computing(PDC’03),
[Description] This paper proposes DSTM, a STM system
that can support dynamic-sized data structures, that is, the granularity of
conflict detection is on object level. The DSTM is obstruction-free, and it is
also the first to apply the ”early release” technique.
7. T. Harris, M.
Plesko, A. Shinnar, and D. Tarditi. Optimizing
memory transactions. In Proceedings of ACM
SIGPLAN 2006 Conference on Programming Language Design and Implementation(PLDI’06),
[Description] This paper describes several
approaches to improve the performance of word-based STM:
1) A “direct access” technique for reducing the number of redirect
when accessing shared memory; 2) a compiler optimization for reducing the
amount of thread-local log; 3) a runtime filtering for detecting duplicate log
entries that are missed statically, and 4)a series of GC-time techniques to
compact the logs generated by long-running atomic blocks.
8. Bratin
Saha, Ali-Reza Adl-Tabatabai, Richard L. Hudson, Chi Cao Minh, and Benjamin
Hertzberg. McRT-STM: a high performance
software transactional memory system for a multi-Core runtime. In Proceedings 11th ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming (PPoPP’06),
[Description] This paper describes McRT-STM, which holds
some new features of nested transactions with partial abort, conditional
signaling within a transaction. There are quite a few performance comparisons
between different features of STM implementation on multi-processor system,
concerning “reader-writer locking” versus “Read versioning
and write locking”, “write buffering” versus “undo
logging”, and object versus cache-line conflict detection.
9. Ali-Reza Adl-tabatabai, Brian
T. Lewis, Vijay Menon, et al. Compiler and
runtime support for efficient software transactional memory. In Proceedings of ACM
SIGPLAN 2006 Conference on Programming Language Design and Implementation (PLDI’06),
[Description] This paper presents some details about the compiler and runtime support
for McRT-STM.
10. Virendra
J. Marathe, William N. Scherer III, and Michael L. Scott. Adaptive software transactional memory. In Proceedings of 19th International Symposium on Distributed Computing(DISC’05),
[Description] As described above.
N/A
11. Keir Fraser and Tim Harris. Concurrent programming without locks. In Proceedings of ACM Transactions on Computer Systems (TOCS), Volume 25, Issue 2, May 2007. [ Paper:
pdf ]
[Description] N/A.
12. Luke Dalessandro and Virendra
J. Marathe and Michael F. Spear and Michael L. Scott. Capabilities
and Limitations of Library-Based Software Transactional Memory in C++. In Proceedings
of the 2nd ACM SIGPLAN Workshop on Transactional Computing, Aug 2007.[Paper: pdf]
[Description]
This paper describes a library-based transactional memory API for C++. Designed to address the limitations of an earlier API with similar functionality.
13. Robert Ennals. Software transactional memory should not be
obstruction-free. Technical Report
Nr. IRC-TR-06-052. Intel Research
[Description] N/A.
14.
David
Dice, Ori Shalev, and Nir Shavit. Transactional locking II. In Proceedings of 20th International Symposium on Distributed Computing(ISDC’06),
[Description] N/A.
15. Adam
Welc,
[Description] This paper shows how lock and transaction memory can work together when
implementing the monitor of Java. It builds a simple Java-like language and the
operation semantics, and proves that this language satisfies the propertys of
isolation, atomicity, and mutex-safty.
16. A.
Welc, S. Jagannathan, and A. L. Hosking. Transactional
monitors for concurrent objects. In Proceedings
of 18th European Conference on Object-Oriented Programming (ECOOP), LNCS 3086,
pages 519-542, 2004. [ Paper: pdf ]
[Description] This paper proposes a new idea to implement the monitor of Java by using
transaction memory for high concurrency.
17. Virendra
J. Marathe, William N. Scherer III, and Michael L. Scott. Design tradeoffs in modern software transactional memory systems.
In Proceedings of 7th Workshop on
Languages, Compilers, and Run-time Support for Scalable Systems
(LCR’04), 2004. [ Paper: pdf ]
[Description] This paper analyzes two STM implementations of DSTM and OSTM, comparing
with each other the versioning strategies and metadata organizations.
http://www.cs.wisc.edu/multifacet/ logTM
http://supertech.csail.mit.edu/xaction.html UTM
http://wasp.cs.washington.edu/ WASP
18. Luke Yen, Jayaram Bobba,
Michael R. Marty, Kevin E. Moore, Haris Volos, Mark D. Hill, Michael M. Swift,
and David A. Wood. LogTM-SE: Decoupling Hardware Transactional Memory
from Caches.
In Proceedings of International Symposium on High Performance Computer
Architecture (HPCA), February 2007. [ Paper: pdf, Talk: ppt, pdf ]
19.
Colin
Blundell, Joe Devietti, E Christopher Lewis, and
permissions-only cache
ONETM(ONETM-Serialized,
ONETM-Concurrent)
20. Naveen
Neelakantam,
To propose that microprocessors provide architecturally-visible hardware
primitives for atomic execution. These primitives provide to the compiler the
ability to optimize the program’s hot path in isolation, allowing the use
of non-speculative formulations of optimization passes to perform speculative
optimizations.
21.
Austen
McDonald, JaeWoong Chung, Brian D. Carlstrom, Chi
support to implement functionality such as conditional synchronization,
system calls, I/O, runtime exceptions
ISA for TM
systems：1) two-phase commit; 2) support for SW handlers on commit, violation and
abort; 3) full support for open- and closed-nested transactions with
independent rollback
22. Lance Hammond, Vicky Wong, Mike Chen, et al. Transactional memory coherence and
consistency. In Proceedings of 31st
Annual International Symposium on Computer Architecture (ISCA’04),
lazy version
management and lazy conflict detection
23. Colin Blundell, Joe Devietti,
E Christopher Lewis, and Milo Martin. Making the Fast Case Common and the
Uncommon Case Simple in Unbounded Transactional Memory. In International
Symposium on Computer Architecture, June 2007. [ Paper: pdf
]
24. C. Scott Ananian, Krste
Asanović, Bradley C. Kuszmaul, Charles E. Leiserson, and Sean Lie. Unbounded transactional memory. In Proceedings
of 11th International
Symposium on High-Performance Computer Architecture(HPCA’05), San Franscisco,
first TM proposal to support unbounded transactions (in both size and
duration)
maintains its transactional
state in a single, shared, memory-resident data structure called the
xstate(single, shared, memory-resident data structure): logs(transactions;
blocks in memory)
UTM: eager
version management; eager conflict detection
LTM: lazy
version management; eager conflict detection
overflow:
25.
XADT(tracks overflowed transactional state, shared data structure èthe virtual address space)
lazy version
management; eager conflict detection
two caching
mechanisms to reduce expensive walks of the XADT:
1)
counting-Bloom-filter-based table (the XF) accessed on cache misses to quickly
rule out conflicts with other transactions. 2) XADC, to cache XADT entries for
blocks that have been accessed by the current transaction
26.
W.
Chuang, S. Narayanasamy, G. Venkatesh, J. Sampson, M. V. Biesbrouck, G. Pokam,
B. Calder, and O. Colavin. Unbounded
Page-Based Transactional Memory. In Proceedings
of the 12th International Conference on Architectural Support for Programming Languages
and Operating Systems(ASPLOS’06), pages 347–358, Oct. 2006. [ Paper: pdf ]
associating state with physical addresses at the block granularity but
allocating/reallocating this shadow state on a per-page basis; Transaction
Access Vector (TAV) lists track data for an entire page
27. Michelle J. Moravan, Jayaram
Bobba, Kevin E. Moore, Luke Yen, Mark D. Hill, Ben Liblit, Michael M. Swift and
David A. Wood. Supporting Nested
Transactional Memory in LogTM. In
Proceedings of
International Conference on Architectural Support for Programming Languages and
Operating Systems
(ASPLOS), October 2006. [ Paper: pdf; Talk: pdf, ppt ]
28. Kevin
E. Moore, Jayaram Bobba, Michelle J. Moravan, Mark D. Hill and David A. Wood. LogTM: Log-based Transactional Memory. In Proceedings of the 12th International Symposium on High Performance
Computer Architecture (HPCA), February 2006. [Paper: pdf; Talk: ppt,
pdf ]
eager version management; eager conflict detection
a per-thread
transaction log in cacheable virtual memory,
29. Jayaram Bobba, Kevin E. Moore,
Haris Volos, Luke Yen, Mark D. Hill, Michael M. Swift, and David A. Wood. Performance Pathologies in
Hardware Transactional Memory. In
Proceedings of International Symposium on Computer Architecture (ISCA), June
2007. [ Paper:
pdf ]
30. Colin
Blundell, E Christopher Lewis, and
31.
Maurice
Herlihy and J. Eliot B. Moss. Transactional
memory: architectural support for lock-free data structures. In Proceedings of International Symposium on Computer Architecture(ISCA’93), pages 289-300, 1993.
[ Paper: pdf
] (First
paper of TM)
leverage the
existing on-chip caches and cache coherence protocol
detecting
conflicts at cache-block granularity
32.
Sanjeev Kumar, Michael Chu,
Christopher J. Hughes, Partha Kundu, Anthony Nguyen. Hybrid transactional Memory. In Proceedings of 11th ACM SIGPLAN 2006 Symposium on
Principles and Practice of Parallel Programming (PPoPP’06),
33. Mark
Moir. HybridTM: integrating hardware and
software transactional memory. Technical
Report, Archivist 2004-0661, Sun Microsystems Research, August 2004. [ Paper: pdf
]
34.
Yang Ni, Vijay
Menon, Ali-Reza Adl-Tabatabai et.al. Open
Nesting in Software Transactional Memory. In Proceedings of 12th
ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP’07), San Jose, California, USA, March 2007. [ Paper:
pdf]
Open nesting
35. Tatiana
Shpeisman, Vijay Menon, Ali-Reza Adl-Tabatabai, Steve Balensiefer, Dan
Grossman, Richard Hudson, Katherine F. Moore, Bratin Saha. Enforcing
Isolation and Ordering in STM. In Proceedings
of ACM Conference on Programming Language Design and Implementation (PLDI’07),
Weak atomicityàStrong atomicity
add read or
write barriers into a nontransactional code,
use dynamic
escape analysis, whole program analysis techniques to optimize the barriers
36. B. McCloskey, F.
Zhou, D. Gay, and E. Brewer. Autolocker:
synchronization inference for atomic sections. In Proceedings of 33rd Annual ACM SIGPLAN Symposium on Principles
of Programming Languages
(POPL’06),
37.
Yuan
Zhang, Joseph Manzano and Guang R. Gao. Atomic
section: concept and implementation. In Proceedings
of Mid-Atlantic Student Workshop on Programming Languages and Systems
(MASPLAS '05),
The
papers listed below mainly focus on the semantics of transactions classified
into three categories: formalization of TM, atomicity of TM and isolation of
TM.
38.
Katherine F. Moore and Dan
Grossman. High-level small-step
operational semantics for transactions. In The Second ACM SIGPLAN Workshop on Transactional Computing,
[Description] Moore and Grossman have presented type systems the study the behaviors of
spawning threads in transactional programs and made assurance that if each
mutable memory location is used outside transactions or inside transactions
(but not both) then strong and weak atomicity are indistinguishable. They
present the semantics of transactions for a λ-calculus. However, their
model for transaction is too simple (allows at most one transaction executing
at a time), and they use two type system to deal with threads spawning and
atomicity comparing respect. Also they do not mention how to deal with the
problems occur due to weak atomicity.
39. Ben Liblit. An Operational Semantics for
LogTM.
[Description] Liblit defines
a detailed operational semantics for the LogTM hardware. This semantics models
the creation and termination of threads, the execution of transactional and
non-transactional memory accesses, and the use of open-nested and closed-nested
transactions. The semantics implements strong atomicity. A memory access is not
permitted to execute if it would conflict with a concurrent transaction;
non-transacted operations are “stalled” until they may run without
conflict. Commit and roll-back are both modeled as single transitions. Liblit
models the interleaving of memory accesses within transactions , but no formal results are shown.
40. Michael L. Scott. Sequential specification of transactional
memory semantics. In Proceedings of
1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for
Transactional Computing(TRANSACT), held in conjunction with PLDI,
[Description]Michael L. Scott presents a framework for transactional semantics that makes inconsistent reads
and writes explicit (requiring a correct implementation to abort transactions
performing such operations). This detail allows definitions regarding when a
transaction must succeed. Scott considers only a total order on all memory
operations, i.e., sequential consistency.
41.
Tim
Harris and Simon Peyton Jones. Transactional
memory with data invariants. In The
First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for
Transactional Computing (TRANSACT’06),
[Description] Tim Harris and Simon Peyton Jones introduce a mechanism for asserting invariants that are maintained by a program that uses atomic memory transactions. The idea is simple: a programmer writes check E where E is an expression that should be preserved by every atomic update for the remainder of the program’s execution. They have extended STM Haskell to
dynamically evaluate check statements atomically with the user’s updates: the result is that we can identify precisely
which update is the
first one to break an invariant.
42. Tim Harris, Maurice Herlihy, Simon Marlow, and Simon Peyton- Jones. Composable memory transactions. In Proceedings of the ACM Symposium on Principles and Practice of Parallel Programming, pages 48–60, Jun 2005. [ Paper: pdf ]
[Description] Harris et al. present an
operational semantics for STM Haskell. Like Dan Grossman’s work, it is
high-level, with only one transaction executing at a time. However, the
semantics is layered such that an entire transaction occurs as one step at the
outer layer, essentially using a large-step model for transactions that does
not lend itself to investigating nested parallelism nor weak isolation. In this
idealized semantics, only one thread executes at a time, which precludes
considering a memory model weaker than sequential consistency.
43.
Paweł
T. Wojciechowski. Isolation-only
transactions by typing and versioning. In Proceedings of the 7th ACM SIGPLAN international conference on
Principles and practice of declarative programming, pages 70–81,
[Description] Wojciechowski proves isolation for a formal language where transactions
with nested parallelism (called tasks in the work) explicitly acquire locks
before accessing data and the beginning of the task must declare all the locks
it might acquire. Explicit locking and version counters leads to a lower-level
model and an effect system that is an extension of lock types. The main theorem
essentially proves a particular low-level rollback-free transaction mechanism
correct.
44.
Suresh
Jagannathan, Jan Vitek, Adam Welc, and
Jan Vitek, Suresh Jagannathan,
Adam Welc, and
[Description] Jagannathan et al. define
TFJ an extension to Featherweight Java. They model a richer source language
where transactions include internal fork-join parallelism, and they explore two
implementations based on optimistic concurrency control and on two-phase
locking. Although steps of the executions of transactions can be interleaved,
all TFJ memory accesses are made transactionally, so the problems produced by
interleaving between transactional and non-transactional code do not occur.
45.
Colin Blundell, E Christopher
Lewis and Milo M. K. Martin. Subtleties
of Transactional Memory Atomicity Semantics. IEEE Computer Architecture Letters. 5(2), 2006. [ Paper: pdf ]
[Description]
Blundell et al.
coined the terms strong and weak to distinguish whether non-transactional code could
examine midtransaction state. They showed that neither semantics subsumes the
other (e.g., each allows some programs to terminate that the other does not).
46. Colin
Blundell, E Christopher Lewis and Milo M. K. Martin. Deconstructing transactional semantics: the
subtleties of atomicity. In Proceedings
of Annual Workshop on Duplicating, Deconstructing, and Debunking
(WDDD’05), June 2005.
[ Paper: pdf ]
Performance Isolation:
describes the degree to which a machine can prevent the behavior of one thread
(or process) from impacting the performance of another thread.
47. B.
Verghese, A. Gupta, and M. Rosenblum. Performance
isolation: Sharing and isolation in shared-memory multiprocessors. In Proceedings
of the Eighth International Conference on Architectural Support for Programming
Languages and Operating Systems, pages 181-192, Oct. 1998. [ Paper: pdf ]
48. Craig Zilles and David H.
Flint. Challenges to Providing
Performance Isolation in Transactional Memories. In Proceedings of Annual Workshop on Duplicating, Deconstructing, and
Debunking (WDDD’05), June 2005. [ Paper: pdf ]
49.
Brian
D. Carlstrom, Austen McDonald, Hassan Chafi et
al. The Atomos transactional
programming language. In Proceedings
of ACM SIGPLAN 2006 Conference on
Programming Language Design and Implementation(PLDI’06),
50. Report
on the experimental language X10.
Draft V 1.01,
Dec.
2006. [ Paper: pdf ]
51.
Cray Inc. Chapel
specification 0.4. Feb. 2005. [ Paper: pdf ]
52.
Eric Allen, David Chase, et al. The Fortress language specification(v1.0 b), Sun
Microsystems, Inc., March 6, 2006. [ Paper: pdf ]
53. Tim Sweeney. The next mainstream programming
language: a game developer's perspective.
In 33rd Annual ACM SIGPLAN Symposium on Principles of Programming
Languages(POPL’06),
Invited talk,
54. P.
Wojciechowski. Isolation-only
Transactions by Typing and Versioning. In Proceedings of the 7th ACM
SIGPLAN international conference on Principles and Practice of Declarative
Programming (PPDP), pages 70–81, July 2005.
Maintained by Yu Zhang, Ming Fu, and Lei Zhao
Last Modified: 8/6/2007 1:25 PM