2014/05/22 by Dan Alistarh, Justin Kopinsky, Alistarh, Dan +7
Computer Science · Psychology · #Advanced Data Storage Technologies #Cognitive Functions and Memory #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1405.5689
openalex publication_date 2014/05/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Several Hybrid Transactional Memory (HyTM) schemes have recently been proposed to complement the fast, but best-effort, nature of Hardware Transactional Memory (HTM) with a slow, reliable software backup. However, the fundamental limitations of building a HyTM with nontrivial concurrency between hardware and software transactions are still not well understood. In this paper, we propose a general model for HyTM implementations, which captures the ability of hardware transactions to buffer memory accesses, and allows us to formally quantify and analyze the amount of overhead (instrumentation) of a HyTM scheme. We prove the following: (1) it is impossible to build a strictly serializable HyTM implementation that has both uninstrumented reads and writes, even for weak progress guarantees, and (2) under reasonable assumptions, in any opaque progressive HyTM, a hardware transaction must incur instrumentation costs linear in the size of its data set. We further provide two upper bound implementations whose instrumentation costs are optimal with respect to their progress guarantees. In sum, this paper captures for the first time an inherent trade-off between the degree of concurrency a HyTM provides between hardware and software transactions, and the amount of instrumentation overhead the implementation must incur.