Sagnak Tasirlar, Concurrent Collections : A new parallel programming model

Parallel computing paradigm has welcomed various programming models that strived for taking the paradigm to mainstream, nevertheless most have been adopted exclusively by experts in the field. Concurrent Collections (CnC) introduce a new programming model with the promise of abstracting away the intricacies of parallelism and provide a blueprint for designing domain specific languages. CnC can be described as a two-level programming model, where the first level is the responsibility of the domain expert, who describes the problem as collection of serial kernels and a graph that describes the dependency relations between these kernels. The second level is the responsibility of the tuning expert who maps these kernels to the hardware and ensures correct and efficient data communication, synchronization and task scheduling. CnC abstracts away the data storage by using "collections" of data items, which obey the dynamic single assignment rule, eliminating common parallel programming errors such as data races. We have built a CnC implementation on top of Habanero-Java(HJ), an extension of Java with constructs for supporting portable parallelism. We address the scheduling aspect of HJ-CnC where we have implemented a non-blocking scheduling on top of a work-sharing runtime with a conditional parallel construct called "delayed async". We have also implemented a rollback-and-replay scheduling scheme where data drives the scheduling, replaying the kernels that were waiting on data. We have shown promising results on data-parallel benchmarks and benchmarks incorporating task, pipeline and loop parallelism.