Paper Info
Title
Making nested parallel transactions practical using lightweight hardware support
Abstract
Transactional Memory (TM) simplifies parallel programming by supporting parallel tasks that execute in an atomic and isolated way. To achieve the best possible performance, TM must support the nested parallelism available in real-world applications and supported by popular programming models. A few recent papers have proposed support for nested parallelism in software TM (STM) and hardware TM (HTM). However, the proposed designs are still impractical, as they either introduce excessive runtime overheads or require complex hardware structures. This paper presents filter-accelerated, nested TM (FaNTM). We extend a hybrid TM based on hardware signatures to provide practical support for nested parallel transactions. In the FaNTM design, hardware filters provide continuous and nesting-aware conflict detection, which effectively eliminates the excessive overheads of software nested transactions. In contrast to a full HTM approach, FaNTM simplifies hardware by decoupling nested parallel transactions from caches using hardware filters. We also describe subtle correctness and liveness issues that do not exist in the non-nested baseline TM. We quantify the performance of FaNTM using STAMP applications and microbenchmarks that use concurrent data structures. First, we demonstrate that the runtime overhead of FaNTM is small (2.3% on average) when applications use only single-level parallelism. Second, we show that the incremental performance overhead of FaNTM is reasonable when the available parallelism is used in deeper nesting levels. We also demonstrate that nested parallel transactions on FaNTM run significantly faster (e.g., 12.4x) than those on a nested STM. Finally, we show how nested parallelism is used to improve the overall performance of a transactional microbenchmark.
Year
DOI
Venue
2010
10.1145/1810085.1810097
I4CS
Keywords
Field
DocType
lightweight hardware support,nested parallelism,software nested transaction,nested tm,hardware tm,nested parallel transaction,fantm simplifies hardware,fantm design,hybrid tm,nested stm,hardware filter,transactional memory,parallel programming,concurrent data structures,programming model,nested transaction
Programming paradigm,Computer science,Parallel computing,Nested parallelism,Correctness,Real-time computing,Transactional memory,Software,Computer hardware,Concurrent data structure,Nested transaction,Liveness
Conference
Citations 
PageRank 
References 
6
0.42
13
Authors
4
Name
Order
Citations
PageRank
Woongki Baek140225.85
Nathan Bronson240817.79
Christos Kozyrakis35817355.99
Kunle Olukotun44532373.50