Paper Info
Title
Optimization techniques for concurrent STM-based implementations: A concurrent binary heap as a case study
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.
Year
DOI
Venue
2009
10.1109/IPDPS.2009.5161153
IPDPS
Keywords
Field
DocType
optimization technique,concurrent binary heap,parallel application,basic stm approach,non-trivial application,concurrent stm-based implementation,good scalability,fine-grained stm-based concurrent binary,new programming paradigm,fine-grained technique,naive approach,case study,data structure,fine-grained stm-based binary heap,probability density function,indexing,concurrent computing,parallel programming,transaction processing,data mining,tree data structures,software transactional memory,debugging,hardware,scalability,pediatrics,data structures,application software
Data structure,Software transactional memory,Programming paradigm,Computer science,Parallel computing,Binary heap,Concurrent computing,Application software,Scalability,Debugging,Distributed computing
Conference
ISSN
Citations 
PageRank 
1530-2075
3
0.45
References 
Authors
6
2
Name
Order
Citations
PageRank
Kristijan Dragicevic1171.75
Daniel Bauer230.45