A competitive analysis for balanced transactional memory workloads

Gokarna Sharma, Costas Busch

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

We consider transactional memory contention management in the context of balanced workloads, where if a transaction is writing, the number of write operations it performs is a constant fraction of its total reads and writes. We explore the theoretical performance boundaries of contention management in balanced workloads from the worst-case perspective by presenting and analyzing two new polynomial time contention management algorithms. We analyze the performance of a contention management algorithm by comparison with an optimal offline contention management algorithm to provide a competitive ratio. The first algorithm Clairvoyant is O√s)-competitive, where s is the number of shared resources. This algorithm depends on explicitly knowing the conflict graph at each time step of execution. The second algorithm Non-Clairvoyant is O√vs .log n)-competitive, with high probability, which is only a O(log n) factor worse, but does not require knowledge of the conflict graph, where n is the number of transactions. Both of these algorithms are greedy. We also prove that the performance of Clairvoyant is close to optimal, since there is no polynomial time contention management algorithm for the balanced transaction scheduling problem that is better than O√vs) 1-e)-competitive for any constant e > 0, unless NP ZPP. To our knowledge, these results are significant improvements over the best previously known O(s) competitive ratio bound.

Original languageEnglish (US)
Pages (from-to)296-322
Number of pages27
JournalAlgorithmica
Volume63
Issue number1-2
DOIs
StatePublished - Jun 2012
Externally publishedYes

Keywords

  • Balanced workloads
  • Competitive ratios
  • Concurrency control
  • Contention management
  • Transaction scheduling
  • Transactional memory

ASJC Scopus subject areas

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'A competitive analysis for balanced transactional memory workloads'. Together they form a unique fingerprint.

Cite this