A Competitive Analysis for Balanced Transactional Memory Workloads

Computer Science – Distributed – Parallel – and Cluster Computing

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

18 pages, In submission for publication

Scientific paper

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 contention management algorithms. The first algorithm Clairvoyant is O(\surd s)-competitive, where s is the number of shared resources. This algorithm depends on explicitly knowing the conflict graph. The second algorithm Non-Clairvoyant is O(\surd s \cdot 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 tight since there is no contention management algorithm that is better than O((\surd s)^(1-\epsilon))-competitive for any constant \epsilon > 0, unless NP\subseteq ZPP. To our knowledge, these results are significant improvements over the best previously known O(s) competitive ratio bound.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

A Competitive Analysis for Balanced Transactional Memory Workloads does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Competitive Analysis for Balanced Transactional Memory Workloads, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Competitive Analysis for Balanced Transactional Memory Workloads will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-645706

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.