A Best-Effort Hardware Transactional Memory Based on Dependency Graph

In recent years, transactional memory has attracted much attention, which can greatly simplify concurrent accesses to the shared memory. Most hardware-based transactional memory systems employ concurrency control protocols that are based on conflict detection and resolution, in which if two transactions conflict with each other, one of them must be aborted and restarted to ensure the semantics of serializability. Based on the detailed analysis of “conflict”, we propose the concept of “weak conflict” to capture the situation in which two conflicting transactions may commit normally without violating the semantics of serializability. Furthermore, this paper proposes hardware transactional memory based on dependency graph, which allows transactions that are weak conflict with each other to commit. More specifically, the dependency graph is a graph which tracks the dependency relationship among active transactions. The existence of dependency circles indicates the violation of serializability. Instead of detecting conflicts, dependency-graph-based hardware transactional memory maintains the dependency graph of the active transactions and detects the dependency circles. If a dependency circle is detected, one of the transactions in the dependency circle should be aborted and restarted to ensure serializability. Simulation results show that dependency-graph-based transactional memory outperforms the transactional memory systems based on conflict detection and resolution.