基于依赖图的硬件事务存储技术研究

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.