CITI has stopped operations in 2014, to co-launch NOVA LINCS THIS SITE IS NOT BEING UPDATED SINCE 2013
citi banner
Home Page FCT/UNL UNL
  Home  \  Publications  \  Publication Page Login  
   
banner bottom
File Top
Tackling Weak-Atomicity in Multiversion Algorithms
Abstract:

Traditionally, multiversion algorithms for transactional memory maintain a version list for each managed memory location or object field, and all the read and write operations manipulate the data values in that list. This implies that all accesses to fields in shared objects must be redirected to the version list, and hence must be enclosed in a memory transaction. Therefore, multiversion algorithms require a strong atomicity model, which may be implemented by warping each non-transactional access in a small transaction, incurring in a non-negligible performance penalty. When using a weak atomicity model, updates made by non-transactional code to object fields are not seen by transactional code and, on the other way around, updates made by transactional code are not seen by non-transactional code. For instance, if an application programmer initializes a shared data-structure without wrapping the initialization procedure in a memory transaction, further transactional accesses, to such data-structure, will not see the initialization and the program may crash. In a previous work [1] we presented an extension of DeuceSTM that enables the efficient support of multiversion algorithms. DeuceSTM does not provide a strong atomicity model, and allows non-transactional accesses to fields of objects that were also accessed inside memory transactions. This hinders the usage of multiversion algorithms in DeuceSTM. In [1] we addressed this problem by rewriting the existing benchmarks to wrap all accesses to shared objects inside an atomic method. Such code changes, when feasible, are always a cumbersome and error prone process. In this work we present an adaptation of traditional multiversion algorithms to support a weak atomicity execution model. The key idea for our solution is to store the value of the latest version in the object’s field instead of in the node at the head of the version list. The commit algorithm must also be enhanced to guarantee the correctness of this approach, as it introduces an additional step of updating the object's field data and the head node of the version list, which must also be performed atomically. Our approach to support the weak atomicity model incurs in a negligible performance overhead, allowing efficient transactional and non-transactional interaction using multiversion algorithms. [1] Dias RJ, Vale TM, Lourenc ̧o JM. Efficient support for in-place metadata in transactional memory. Euro-Par 2012 Parallel Processing, Lecture Notes in Computer Science, vol. 7484, Kaklamanis C, Papatheodorou T, Spirakis P (eds.). Springer Berlin / Heidelberg; 589–600.


Description: Euro-TM Workshop on Transactional Memory (WTM 2013)

Date: April, 2013


Authors:
File Bottom