Delegated isolation
- 22 October 2011
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- Vol. 46 (10), 885-902
- https://doi.org/10.1145/2048066.2048133
Abstract
Isolation---the property that a task can access shared data without interference from other tasks---is one of the most basic concerns in parallel programming. In this paper, we present Aida, a new model of isolated execution for parallel programs that perform frequent, irregular accesses to pointer-based shared data structures. The three primary benefits of Aida are dynamism, safety and liveness guarantees, and programmability. First, Aida allows tasks to dynamically select and modify, in an isolated manner, arbitrary fine-grained regions in shared data structures, all the while maintaining a high level of concurrency. Consequently, the model can achieve scalable parallelization of regular as well as irregular shared-memory applications. Second, the model offers freedom from data races, deadlocks, and livelocks. Third, no extra burden is imposed on programmers, who access the model via a simple, declarative isolation construct that is similar to that for transactional memory. The key new insight in Aida is a notion of delegation among concurrent isolated tasks (known in Aida as assemblies). Each assembly A is equipped with a region in the shared heap that it owns---the only objects accessed by A are those it owns, guaranteeing race-freedom. The region owned by A can grow or shrink flexibly---however, when A needs to own a datum owned by B, A delegates itself, as well as its owned region, to B. From now on, B has the responsibility of re-executing the task A set out to complete. Delegation as above is the only inter-assembly communication primitive in Aida. In addition to reducing contention in a local, data-driven manner, it guarantees freedom from deadlocks and livelocks. We offer an implementation of Aida on top of the Habanero Java parallel programming language. The implementation employs several novel ideas, including the use of a union-find data structure to represent tasks and the regions that they own. A thorough evaluation using several irregular data-parallel benchmarks demonstrates the low overhead and excellent scalability of Aida, as well as its benefits over existing approaches to declarative isolation. Our results show that Aida performs on par with the state-of-the-art customized implementations of irregular applications and much better than coarse-grained locking and transactional memory approaches.Keywords
This publication has 27 references indexed in Scilit:
- Habanero-JavaPublished by Association for Computing Machinery (ACM) ,2011
- Hierarchical Place Trees: A Portable Abstraction for Task Parallelism and Data MovementLecture Notes in Computer Science, 2010
- Parallel programming with object assembliesPublished by Association for Computing Machinery (ACM) ,2009
- Software Transactional Memory: Why Is It Only a Research Toy?Queue, 2008
- On the Scalability of an Automatically Parallelized Irregular ApplicationLecture Notes in Computer Science, 2008
- Concurrent programming without locksACM Transactions on Computer Systems, 2007
- Individual‐based Computational Modeling of Smallpox Epidemic Control StrategiesAcademic Emergency Medicine, 2006
- Advanced contention management for dynamic software transactional memoryPublished by Association for Computing Machinery (ACM) ,2005
- Concurrency control for high contention environmentsACM Transactions on Database Systems, 1992
- Data structures and algorithms for disjoint set union problemsACM Computing Surveys, 1991