An efficient transactional memory algorithm for computing minimum spanning forest of sparse graphs
Authors:
Open Access
- 14 February 2009
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 44 (4) , 15-24
Abstract
Due to power wall, memory wall, and ILP wall, we are facing the end of ever increasing single-threaded performance. For this reason, multicore and manycore processors are arising as a new paradigm to pursue. However, to fully exploit all the cores in a chip, parallel programming is often required, and the complexity of parallel programming raises a significant concern. Data synchronization is a major source of this programming complexity, and Transactional Memory is proposed to reduce the difficulty caused by data synchronization requirements, while providing high scalability and low performance overhead. The previous literature on Transactional Memory mostly focuses on architectural designs. Its impact on algorithms and applications has not yet been studied thoroughly. In this paper, we investigate Transactional Memory from the algorithm designer's perspective. This paper presents an algorithmic model to assist in the design of efficient Transactional Memory algorithms and a novel Transactional Memory algorithm for computing a minimum spanning forest of sparse graphs. We emphasize multiple Transactional Memory related design issues in presenting our algorithm. We also provide experimental results on an existing software Transactional Memory system. Our algorithm demonstrates excellent scalability in the experiments, but at the same time, the experimental results reveal the clear limitation of software Transactional Memory due to its high performance overhead. Based on our experience, we highlight the necessity of efficient hardware support for Transactional Memory to realize the potential of the technology.Keywords
This publication has 21 references indexed in Scilit:
- The limits of software transactional memory (STM)2008
- Optimistic parallelism benefits from data partitioning2008
- Modeling optimistic concurrency using quantitative dependence analysis2008
- An effective hybrid transactional memory system with strong isolation guarantees2007
- Making the fast case common and the uncommon case simple in unbounded transactional memory2007
- STMBench72007
- Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphsJournal of Parallel and Distributed Computing, 2006
- Transactional Locking II2006
- Adaptive Software Transactional Memory2005
- LEDA: a platform for combinatorial and geometric computingCommunications of the ACM, 1995