事务存储中的一种自适应冲突检测算法

事务存储被认为是极具前景的多核处理器并行编程的手段,但存在开销过大的问题。采用Bloom Filter对事务间访问共享变量进行冲突检测,能够有效地降低开销,但其存在误判会导致不必要的事务作废,因此要尽可能减少。简要介绍了Bloom Filter和事务存储,提出了一种事务存储的自适应冲突检测算法ACDA,根据事务读写集合大小自适应地调整Bloom Filter的位串大小,在较低开销的情况下,保持误判率不增加。分析了软件事务存储中实现ACDA的特点,初步实现ACDA,与主流软件事务存储实现RSTM相比,在事务存储测试程序STAMP中,开销可接受的前提下,减少因误判而作废的事务最高达93%。给出了对ACDA哈希函数进一步优化的思路。

An Adaptive Conflict Detection Algorithm in Transactional Memory

Transactional memory is a promising parallel programming way for multi-core processors, however it costs a lot Using Bloom Filter to detect shared variable access conflicts between transactions is an effective way to lower cost over-head. False positives in Bloom Filter can leads to unnecessary transaction roll-back, so it must be reduced. We introduce Bloom Filter and transactional memory briefly, and come up with an adaptive conflict detection algorithm (ACDA) adjusting the length of the Bloom Filter bit vector due to the size of read and write set of transactions. With lower overhead, the false positives are kept stable. We also analyze how to realize ACDA in software transactional memory, and realize it Compared with RSTM in the test of the STAMP bench mark, ACDA lowers the aborted transactions to 93% at most. We discuss how to optimize ACDA as well.