Optimization techniques for concurrent STM-based implementations: A concurrent binary heap as a case study
Authors:
- 1 May 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15302075,p. 1-8
Abstract
Much research has been done in the area of software transactional memory (STM) as a new programming paradigm to help ease the implementation of parallel applications. While most research has been invested for answering the question of how STM should be implemented, there is less work about how to use STM efficiently. This paper is focused on the challenge of how to use STM for efficient and scalable implementations of non-trivial applications. We present a fine-grained STM-based concurrent binary heap, an application of STM for a data structure that is notoriously difficult to parallelize. We describe extensions to the basic STM approach and also the benefits of our proposal. Our results show that the fine-grained STM-based binary heap provides very good scalability compared to the naive approach. Nevertheless, we reach a point where the complexity of some fine-grained techniques do not justify its use for the increase in performance that can be obtained.Keywords
This publication has 6 references indexed in Scilit:
- Delaunay Triangulation with Transactions and Barriers2007
- Language support for lightweight transactionsACM SIGPLAN Notices, 2003
- Software transactional memory for dynamic-sized data structures2003
- An efficient algorithm for concurrent priority queue heapsInformation Processing Letters, 1996
- Software transactional memory1995
- Linearizability: a correctness condition for concurrent objectsACM Transactions on Programming Languages and Systems, 1990