Concurrent assemblies: a model for concurrent program execution

We present Concurrent Assemblies, an abstract model for modeling shared memory parallel programs. In particular Concurrent Assemblies is targeted to irregular parallel applications such as those manipulating mutable pointer-based data structures. Typically in these applications, there is no a priori bound on the available parallelism. The Concurrent Assemblies abstract execution model addresses dynamism and locality through the unifying abstraction of an concurrent assembly: a local region in a shared data structure equipped with a short-lived, speculative thread of control. The thread of control in an assembly can only access objects within the assembly. While objects can migrate from assembly to assembly, such migration is local—i.e., objects only move from one assembly to a neighboring one—and does not lead to aliasing. Programming primitives include a merge operation, by which an assembly merges with an adjacent assembly, and a split operation, which splits an assembly into smaller ones. Our abstractions are race-free and inherently data-centric. In addition to the formal definition of the Concurrent Assemblies abstract model, we show the usefulness of such an abstract model by presenting two different programming languages that can be modeled as instances of the Concurrent Assemblies abstract model. The first one is JCHORUS, a high-level parallel programming language built on top of the sequential subset of Java, suitable for irregular, heap-manipulating applications like mesh refinement and epidemic simulations. One goal of JC HORUS is to express the dynamic and instance-dependent patterns of memory access that are common in typical irregular applications. Its other focus is locality of effects: the property that in many of the same applications, typical imperative commands only affect small, local regions in the shared heap. The second is HABANERO-CHORUS, a parallel subset of the HABANERO-JAVA programming language. Here concurrency is expressed as asynchronous software transactions. We present implementation of JCHORUS and HABANERO -CHORUS as well as report on the performance numbers.