Institute for Software Research
School of Computer Science, Carnegie Mellon University


ÆMINIMUM Freeing Programmers from the Shackles of Sequentiality

Sven Stork

March 2013

Ph.D. Thesis

Joint Program
Institute for Software Research, Carnegie Mellon University
Department of Informatics Engineering, University of Coimbra, Portugal


Keywords: Access permissions, data groups, concurrency, programming language, dataflow

The aim of this doctoral thesis was to study the implications of having a concurrent-by-default programming language. This includes language design, runtime system, performance and software engineering considerations.

We conduct our study through the design of the concurrent-by-default Æminimum programming language. ÆMINIUM leverages the permission flow of object and group permissions through the program to validate the program's correctness and to automatically infer a possible parallelization strategy via a dataflow graph. ÆMINIUM supports regular parallelism (such as fork-join parallelism) as well as irregular parallelism (e.g., as dataflow).

In this thesis we present a formal system, called µÆMINIUM, modeling the core concepts of ÆMINIUM. µÆMINIUM static type system is based on "Featherweight Java" with ÆMINIUM specific extensions. Besides checking for correctness ÆMINIUM's type system it also uses the permission flow to compute a potential parallel execution strategy for the program. µÆMINIUM's dynamic semantics use a concurrent-by-default evaluation approach. Along with the formal system we present its soundness proof.

We provide a full description of the implementation along with the description of various optimization techniques we used. We implemented Æminium as an extension of the Plaid programming language, which has first-class support for permissions built-in. The ÆMINIUM implementation and all case studies are publicly available under the General Public License.

We use various case studies to evaluate ÆMINIUM's applicability and to demonstrate that ÆMINIUM parallelized code has some performance improvements compared to its sequential counterpart. We chose to use case studies of common domains or problems that are known to benefit from parallelization, to show that ÆMINIUM is powerful enough to encode them. We demonstrate through a webserver application, which evaluates ÆMINIUM's impact on latency-bound applications, that AEminium can achieve a 70% performance improvement over the sequential counter part. In another case study we chose to implement a dictionary function to evaluate ÆMINIUM's capabilities to express essential data structures. Our evaluation demonstrates that ÆMINIUM can be use to express parallelism in such data-structures and that the performance benefits scale with the amount of annotation effort which is put in to the implementation. We chose an integral computation example to evaluate pure functional programming and computational intensive use cases. Our experiments show that ÆMINIUM is capable of extracting parallelism from functional code and achieving performance improvements up to the limits of Plaid inherent performance bounds. We elaborate about our experience in developing and using ÆMINIUM and discuss potential shortcomings and potential areas of interest for future work.

Overall, we hope that the work helps to advance concurrent programming in modern programming environments.

206 pages

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by