Department of Information Technology
Department of Information Technology
Uppsala UniversityInformation TechnologyResearchUPMARCResearchEase of ProgrammingParallel Object Programming
Listen

NEW

UPMARC Posters
4posters-200x146.jpg

POP : Parallel Object Programming

News

  • 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.

Motivation

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.

Expected Results

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)

Achievements

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.

Publications

Ownership Types: A Survey. Dave Clarke, Johan Östlund, Ilya Sergey, and Tobias Wrigstad. In Aliasing in Object-Oriented Programming: Types, Analysis, and Verification, volume 7850 of Lecture Notes in Computer Science, pp 15-58, Springer Berlin/Heidelberg, 2013. (DOI).
Structured Aliasing. Tobias Wrigstad. In Aliasing in Object-Oriented Programming: Types, Analysis, and Verification, volume 7850 of Lecture Notes in Computer Science, pp 512-513, Springer Berlin/Heidelberg, 2013. (DOI).
Multiple Aggregate Entry Points for Ownership Types. Johan Östlund and Tobias Wrigstad. In ECOOP 2012 – Object-Oriented Programming, volume 7313 of Lecture Notes in Computer Science, pp 156-180, Springer Berlin/Heidelberg, 2012. (DOI).
The Joelle Programming Language: Evolving Java Programs Along Two Axes of Parallel Eval. Johan Östlund, Stephan Brandauer, and Tobias Wrigstad. 2012 International Workshop on Languages for the Multi-core Era, 2012.
Is the World Ready for Ownership Types? Is Ownership Types Ready for the World?. Tobias Wrigstad and Dave Clarke. International Workshop on Aliasing, Confinement and Ownership in object-oriented programming: IWACO at ECOOP (Vetenskapsrådet), 2011.
Regions as Owners: A Discussion on Ownership-based Effects in Practice. Johan Östlund and Tobias Wrigstad. International Workshop on Aliasing, Confinement and Ownership in object-oriented programming: IWACO at ECOOP, 2011.
Owners as Ombudsmen: Multiple Aggregate Entry Points for Ownership Types. Tobias Wrigstad and Johan Östlund. International Workshop on Aliasing, Confinement and Ownership in object-oriented programming: IWACO at ECOOP (Vetenskapsrådet), 2011.
Tribal ownership. Nicholas Cameron, James Noble, and Tobias Wrigstad. In Proc. 1st International Conference on Systems, Programming, Languages, and Applications: Software for Humanity, volume 45:10 of ACM SIGPLAN Notices, pp 618-633, ACM Press, New York, 2010. (DOI).
Welterweight Java. Johan Östlund and Tobias Wrigstad. In Objects, Models, Components, Patterns, volume 6141 of Lecture Notes in Computer Science, pp 97-116, Springer-Verlag, Berlin, 2010. (DOI).

Approach

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-06 Elias Castegren and Stephan Brandauer present posters at the UPMARC summer school.

e-pres.jpg http://wrigstad.com/posters/s-pres.jpg

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-23 Amanj Sherwany recently defended his Master thesis on Loci 2.0.
The presentation

2011-05-12 Tobias Wrigstad presented parts of the planned work for on the Joelle fork for the KoF'11 panel.

Updated  2014-01-28 22:12:55 by Tobias Wrigstad.