False conflict reduction in the Swiss Transactional Memory (SwissTM) system

Software Transactional Memory (STM) is a programming paradigm that allows a programmer to write parallel programs, without having to deal with the intricacies of synchronization. That burden is instead borne by the underlying STM system. SwissTM is a lock-based STM, developed at EPFL, Switzerland. Memory locations map to entries in a lock table to detect conflicts. Increasing the number of locations that map to a lock reduces the number of locks to be acquired and improves throughput, while also increasing the possibility of false conflicts. False conflicts occur when a transaction that updates a location mapping to a lock, causes validation failure of another transaction, that reads a different location mapping to the same lock. In this paper, we present a solution for the false conflict problem and suggest an adaptive version of the same algorithm, to improve performance. Our algorithms produce significant throughput improvement in benchmarks with false conflicts.