On the Performance of Window-Based Contention Managers for Transactional Memory

摘要

This paper considers a family of greedy contention managers for transactional memory for executing windows of transactions, which aim to provide both good theoretical and practical performance guarantees at the same time. The main approach behind window-based contention managers is to use random delays at the beginning of the window, which have the property that the conflicting transactions are shifted inside the window and their execution times may not coincide. Thus, conflicting transactions can execute at different time slots and potentially many conflicts are avoided. In this paper, window-based contention managers are considered for eager conflict management software transactional memory systems and evaluated using sorted link list, red-black tree, skip list, and vacation benchmarks. The performance of window-based contention managers is compared through experiments with Polka, the published best contention manager, Greedy, the first contention manager with provable theoretical and practical performance properties, and Priority, a simple priority based contention manager. The results show that window-based contention managers have comparable performance with Polka, and outperform Greedy and Priority, sometimes by significant margins. The evaluation results confirm their benefits in practical performance throughput and other transactional metrics such as aborts per commit, execution time overhead, etc., along with their non-trivial provable properties. This is a significant step toward the design of scalable transactional memory schedulers.