Window-based greedy contention management for transactional memory: theory and practice

• DOI: 10.1007/s00446-012-0159-7
• Publication Date: 2012-02-01T16:25:09Z
• Authors: Gokarna Sharma; Costas Busch
• Keywords: Online algorithm; Competitive Analysis

We consider greedy contention managers for transactional memory for M × N execution windows of transactions with M threads and N transactions per thread. We present, formally analyze, and experimentally evaluate three new randomized greedy contention management algorithms for transaction windows. Assuming that each transaction has duration τ and conflicts with at most C other transactions inside the window, the first algorithm Offline-Greedy produces a schedule of length O(τ· (C + N· log(MN))) with high probability. The offline algorithm depends on knowing the conflict graph which evolves while the execution of the transactions progresses. The second algorithm Online-Greedy produces a schedule of length that is only a logarithmic factor worse than Offline-Greedy, but does not require knowledge of the conflict graph. The third algorithm Adaptive-Greedy is the adaptive version of the previous algorithms which produces a schedule of length asymptotically the same as with online algorithm by adaptively guessing the value of C. All of the algorithms exhibit competitive ratio very close to O(s), where s is the number of shared resources, and at the same time, our algorithms provide new non-trivial tradeoffs for greedy transaction scheduling that parameterize window sizes and transaction conflicts within the execution window. We evaluate these window-based algorithms experimentally using the sorted link list, red-black tree, skip list, and vacation benchmarks. The evaluation results confirm their benefits in practical performance throughput and other metrics such as aborts per commit ratio and execution time overhead, along with the non-trivial provable properties of the algorithms.