Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2010-02-22
Computer Science
Distributed, Parallel, and Cluster Computing
13 pages
Scientific paper
We consider greedy contention managers for transactional memory for M x N execution windows of transactions with M threads and N transactions per thread. Assuming that each transaction conflicts with at most C other transactions inside the window, a trivial greedy contention manager can schedule them within CN time. In this paper, we show that there are much better schedules. We present and analyze two new randomized greedy contention management algorithms. The first algorithm Offline-Greedy produces a schedule of length O(C + N log(MN)) with high probability, and gives competitive ratio O(log(MN)) for C <= N log(MN). The offline algorithm depends on knowing the conflict graph. The second algorithm Online-Greedy produces a schedule of length O(C log(MN) + N log^2(MN)) with high probability which is only a O(log(NM)) factor worse, but does not require knowledge of the conflict graph. We also give an adaptive version which achieves similar worst-case performance and C is determined on the fly under execution. Our algorithms provide new tradeoffs for greedy transaction scheduling that parameterize window sizes and transaction conflicts within the window.
Busch Costas
Estrade Brett
Sharma Gokarna
No associations
LandOfFree
Window-Based Greedy Contention Management for Transactional Memory 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 Window-Based Greedy Contention Management for Transactional Memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Window-Based Greedy Contention Management for Transactional Memory will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-169078