POP : Parallel Object Programming
- 2014-03 The group will grow with the addition of Mingkun Yang (PhD student) and Dave Clarke (associate professor).
- 2014-02 The UPSCALE project launches. UPSCALE's vision is to provide programming language support to efficiently develop applications that seamlessly scale to the available parallelism of multi- and manycore chips without abandoning the object-oriented paradigm and the associated software engineering methodologies. UPSCALE is a collaboration between Uppsala University, Imperial College London, University of Oslo, and CWI in Amsterdam.
- 2014-01 A very important milestone in the (non-prototype) development of the Joelle compiler has been reached! Joelle now fully type checks and verifies isolated active objects and executes them in parallel.
Mainstream languages like Java and C++ were not designed for a reality where parallel and concurrent programming was ubiquitous. The inherent statefulness in combination with aliasing makes parallel programming in imperative languages difficult, and control mechanisms like locks and monitors do not scale or breaks composition, especially in object-oriented languages. Furthermore, there is little or no support in such languages for guarding properties useful for correct or efficient programming. For example, there is no support in either language for making objects thread-local, and useful features like asynchronous method calls and futures are provided in libraries whose correct usage is hard to enforce, difficult and prone to errors.
Transitioning mainstream languages into the multicore reality of the future is restricted from imposing substantial changes on programming, as a well-developed, well-understood mindset already exists in the respective programming communities. Furthermore, the value of mainstream languages really reside in existing code bases that cannot be rendered unusable due to changes to the languages.
This project aims at providing mainstream languages with facilities for concurrent and parallel programming without breaking compatibility with existing code or programming practices. The facilities can be in the form of tools, language extensions, compilers and run-times, etc. and the target audience is the working programmer.
Long Term Goal
The long-term goals of the project is the development of language constructs, languages and tools (compilers, checkers, IDEs, etc.) that simplify the construction of parallel and concurrent programs by allowing relevant properties (such as thread-locality, race and deadlock freedom, etc.) to be checked statically, or facilitated by e.g., resource-aware schedulers. In addition to programmer convenience, we have performance and energy-efficiency as a side-goal.
One very specific artefact is the (currently named) Joelle programming language, compiler and virtual machine. Joelle is an extension of Java centered around the active object pattern, where various flavours of ownership types are used to partition the heap (to protect the sequential invariant of active object code), and to allow both coarse-grain and fine-grain parallel execution of statements with non-overlapping computational effects. The Joelle language will (at least initially) run on stock Java virtual machines for uptake reasons, and employ standard schemes for efficient parallel programming on the Java platform employed by several other languages and libraries.
An internal presentation of one of our long-term goals can be found here.
Part of our ongoing work focus on simplifying parallel programming in Java. We have developed a set of annotations for expressing thread-locality in Java programs, and developed a tool for checking their correctness. Currently, we are studying the actual degree of thread-locality in Java programs (smaller benchmarks suggest about 80%). One of the goals here is to investigate whether Loci can be used to improve cache utilisation by not synchronising thread-local values in the caches. Garbage collection threads complicate this matter.
New programming languages, language constructs and tools that fit in the current toolbox and is usable with existing mainstream languages such as Java and C++, including existing code bases with minimal or no modifications.
To facilitate industrial uptake, and for practical evaluation, we aim to develop prototype implementations (demonstrators) or proper implementations of several of our constructs and languages. These will take the form of tools or plug-and-play extensions, or occasionally as stand-alone programming systems.
- The Joelle language, compiler and VM
- The Loci tool suite (annotation specification, pluggable type checker, thread-locality analyser, etc.)
- Programming constructs for expressing memory regions, disjointness and nesting of regions (in particular improvement of ownership type technology to further partition the heap)
- Cache coherence protocols that take into consideration thread-locality, immutability, and other language constructs from Joelle and Loci
- The ENCORE "inverted object-oriented programming language" (part of the [http://upscale-project.eu|UPSCALE project)
So far, this project has produced results within the realm of Java-like languages. In particular:
- A novel interpretation of ownership which allows static checking of deterministic parallel operations on shared data (submitted)
- A minimal, unobtrusive programming system (checkers, possibly with IDE support) for expressing and statically checking thread-locality of objects in Java
- A Java extension based on active objects that guarantees isolation of active objects with a minimum of copying, and also safe transfer of ownership
- An extension to ownership types which allows multiple bridge objects to the same aggregate without weakening encapsulation
- Amanj Sherwany completed his thesis work on Loci 2.0. His presentation can be found here. Amanj is now a PhD student in Lugano, Switzerland.
- Nosheen Zaza completed her thesis work on applying Loci to real-world programs and measuring the accuracy and workload. Nosheen is now a PhD student in Lugano, Switzerland.
Work continues along these lines. Recently, a minimal language description for Java-like languages was developed much in the same spirit as Featherweight Java but focusing on the imperative nature of Java, rather than encoding Java in a functional style. Work on encapsulation systems for Java-like languages is also undergoing, especially combining virtual classes and dependent types in a way that provides pluggable encapsulation.
A prototype implementation of the Java extension (Joelle) was developed by Johan Östlund.
- Integrating Typed and Untyped Code in a Scripting Language. Appeared at POPL 2010. Tobias Wrigstad, Francesco Zappa Nardelli, Sylvain Lebresne, Johan Östlund and Jan Vitek.
- Loci: Simple Thread-Locality for Java. Appeared at ECOOP 2009. Tobias Wrigstad, Filip Pizlo, Fadi Meawad, Lei Zhao and Jan Vitek.
- Minimal Ownership for Active Objects. Appeared at APLAS 2008. Dave Clarke, Tobias Wrigstad, Johan Östlund and Einar Broch-Johnsen.
- Ownership, Uniqueness and Immutability. Appeared at TOOLS Europe 2008. Johan Östlund, Tobias Wrigstad, Dave Clarke, Beatrice Åkerblom.
- Minimal Ownership for Active Objects. CWI Tech Report 2008, SEN-R0803, ISSN 1386-369X. Dave Clarke, Tobias Wrigstad, Johan Östlund and Einar Broch-Johnsen.
We develop minimal and often pragmatic type systems and other lightweight verification methods for mainstream languages, as well as investigate alternative models for concurrency and parallelism for (predominantly object-oriented) mainstream languages. In particular, we are focusing on:
- Analysing useful concurrency properties for correct usage of libraries for concurrent and parallel programming with the goal of checking such properties statically
- Compositional techniques for controlling shared access to data without risking deadlocks or data-races
- Migration paths for legacy code to use our developed techniques
Events and Presentations
2013-03 Stephan Brandauer defended his Masters thesis on scheduling parallel objects in Joelle.
2012-09 Elias Castegren defended his Masters thesis on flexible aliasing protocols.
2012-09 Nosheen Zaza defended her Masters thesis on capturing thread-locality in Java programs using Loci.
2012-06 Tobias Wrigstad gave a keynote on "Structured Aliasing" at ECOOP'12 in Beijing.
2011-05-12 Tobias Wrigstad presented parts of the planned work for on the Joelle fork for the KoF'11 panel.