This paper investigates adding transactions with nestedparallelism and nested transactions to a dynamically multithreaded parallel programming language that generates only series-parallel programs. We describe XConfl...
详细信息
ISBN:
(纸本)9781595939609
This paper investigates adding transactions with nestedparallelism and nested transactions to a dynamically multithreaded parallel programming language that generates only series-parallel programs. We describe XConflict, a data structure that facilitates conflict detection for a software transactional memory system which supports transactions with nestedparallelism and unbounded nesting depth. For languages that use a Cilk-like work-stealing scheduler, XConflict answers concurrent conflict queries in O(1) time and can be maintained efficiently. In particular, for a program with T-1 work and a span (or critical-path length) of T, the running time on p processors of the program augmented with XConflict is only O(T-1/Tp+p). Using XConflict, we describe CWSTM, a runtime-system design for software transactional memory which supports transactions with nestedparallelism and unbounded nesting depth of transactions. The CWSTM design provides transactional memory with eager updates, eager conflict detection, strong atomicity, and lazy cleanup on aborts. In the restricted case when no transactions abort and there are no concurrent readers, CWSTM executes a transactional computation on p processors also in time O(T-1/Tp+p). Although this bound holds only under rather optimistic assumptions, to our knowledge, this result is the first theoretical performance bound on a TM system that supports transactions with nestedparallelism which is independent of the maximum nesting depth of transactions.
暂无评论