ByteSTM
Transactional memory (TM) is a promising alternative to lock-based concurrency control. It is an alternative model for accessing shared memory data objects, without exposing locks in the programming interface to avoid the drawbacks of locks (e.g., deadlocks, livelocks, lock convoying, non-composability). With TM, programmers organize code that read/write shared memory objects as transactions. A transaction executes speculatively, logging changes to shared objects that it modifies in an undo-log, or by using a write-buffer to make the changes, and maintains its read set and write set. When the transaction ends, it checks for read/write or write/write conflicts (using the read/write sets). If no conflict occurs, the changes are made permanent (i.e., the transaction commits). Otherwise, a contention manager resolves the conflict by allowing one transaction to commit; the other is aborted, its changes are rolled-back (using the undo-log or by discarding the write-buffer), and it is re-executed, yielding the (illusion) of atomicity. In addition to a simple programming model, TM provides performance comparable to highly concurrent, fine-grained locking implementations and is composable.
TM originated as a hardware solution (HTM). Examples include TCC, UTM, OneTM, and LogSPoTM. They often extend multiprocessor cache coherence protocols, or modify hardware to support transactions. Later, it was extended in software, called STM. Example STM implementations include DSTM2, RSTM, and Deuce. STM often uses basic atomic hardware primitives (e.g., compare-and-swap) to implement the commit operation, and thread-local memory locations are used to provide consistent view of memory. TM has also been provided in hardware/software combination, called hybrid TM. Example hybrid TM implementations include LogTM and HyTM.
In ByteSTM, we use STM to detect and resolve memory conflicts between parallel threads. As mentioned here, we follow an optimistic approach in splitting code into parallel sections to reduce the overhead of online profiling. Thus, we need an STM implementation to handle possible memory conflicts. ByteSTM is an STM implementation at the virtual machine-level, which yields the following benefits:
- Significant implementation flexibility in handling memory access at low-level (e.g., registers, thread stack) and for transparently manipulating bytecode instructions for transactional synchronization and recovery
- Higher performance due to implementing all TM building blocks (e.g., versioning, conflict detection, contention management) at bytecode-level
- Easy integration with other modules of HydraVM
Implementation
In HydraVM, super blocks executing in threads run as transactions. For each super block, we create a syntactic method that contains the code for the block. This method accepts two parameters: 1) the super block's entry point and 2) variables accessed by the super block, and returns an integer that represents the exit point of the super block. Thus, each transaction has its own memory that it accesses or modifies. When the transaction is invoked, a copy of all variables is made and sent to the method. Upon successful completion of the transaction, this copy is then merged back with the master memory version. In short, our memory model is lazy-commit with write-buffer implementation. To identify multiple copies of an object, an identifier is added to the header of the object, which is unique in all copies of the object.
In contrast to other STM implementations, in ByteSTM, at commit time, a transaction scans the thread stack and registers to collect the addresses of the accessed objects. Objects identifiers are retrieved from the copies and a signature is created, which represents the memory addresses accessed by the transaction. Transactional conflict is detected using the intersection of transaction signatures.
To preserve the program order, each transaction must wait till a certain point of time to commit, or otherwise its changes are exposed to the outside world. Thus, ByteSTM suspends completed transactions till their valid commit times are reached. Aborted transactions discard their changes, and are either terminated (i.e., a program flow violation or a misprediction) or re-executed (i.e., to resolve a data-dependency conflict).
Download
The source code is available online at the following link.
Download ByteSTM
This work is supported in part by AFOSR under grant FA9550-14-1-0187. Any opinions, findings, and conclusions or recommendations expressed in this site are those of the author(s) and do not necessarily reflect the views of AFOSR.
