Department of Information Technology

Parallel Programming Language Design and Implementation

Projects for Bachelor and Masters Students

Projects under supervision of Dave Clarke and Tobias Wrigstad

About Us

The research group of Dave Clarke and Tobias Wrigstad are working on a new parallel programming language called Encore. Development has been underway for about a year now and there are many opportunities to contribute to the project: designing and implementing new language features, implementing library support, benchmarking, implementing compiler optimisations, developing case studies, and even formalisation.

About You

We are looking for strong bachelors and masters students who have many of the following characteristics:

  • You are a talented programmer, comfortable in both Haskell (or equivalent) and C. (Our compiler is written in Haskell, our backend is written in C.)
  • You want to do a challenging, research-oriented project.
  • You love parallel programming and/or programming languages.
  • You have a burning desire to make code run fast.
  • You have a burning desire to make code elegant.

Topics

We are offering a number of topics that will involve implementing and experimenting with new programming language features in the context of the Encore compiler or its backend. For some of these projects, there is substantial scope for forging your own direction, bringing your own ideas into the research and possibly
even publishing the results. Most projects are offered both at a bachelors and masters level.

Graph Analysis Framework in Encore

  • Description: The 'Pregel' framework (paper) defines a graph abstraction where vertices in a graph communicate via message passing, instead of synchronously updating their neighbours. The framework comes with a runtime that ensures that computations are executed in a way that guarantees determinism, but still provides a high level of parallelism. Pregel has had a large impact, implementations that deliver or support similar abstractions include Apache Giraph and the GraphX library (paper) of Apache Spark. See also High-Level Programming Abstractions for Distributed Graph Processing.
  • Expected Outcome: An implementation of a graph analysis framework that exposes convenient high level abstractions to programmers and will deliver good parallel performance.
  • Challenges: The project involves a wide range of topics, and ranges from high level API design to low level performance optimisation. It may be necessary to implement minor changes to encore's runtime or compiler.

MapReduce Framework in Encore

  • Description: Extend an existing MapReduce framework to be more performant and flexible.

Incremental Computation Framework in Encore

  • Description: Implement a framework supporting incremental computation in Encore, for instance, along the lines of Adaptation.
  • Expected Outcome: A framework, examples using the framework, benchmarks demonstrating its performance.
  • Challenges: Overcoming the challenge of integrating Encore's active objects with incremental abstractions.

Distributed Arrays in Encore

  • Description: Implement Julia's distributed arrays in Encore.
  • Expected Outcome: An abstraction similar to that offered by Julia, but implemented using active objects, along with a number of benchmarks demonstrating the strengths and weaknesses of the proposed implementation.

Type inference

  • Description: Improve the Encore type checker to better support type inference.
  • Challenges: Encore is becoming a large language and so handling all of its features will be required. In addition, the current type checker is a bit unweildy so quite some effort will be required to understand it.

Exceptions for Encore

  • Description: Exceptions are not currently supported in encore. Add exceptions, and the ability to catch them, to the language and implementation.
  • Expected outcome: Encore programmers should be able to throw and catch exceptions in their code.
  • Challenges: Compiling exceptions to efficient code is not trivial.
  • Desired skills/Interests: You should be interested in language runtimes, and be proficient in C, as well as Haskell.

Annotation support for Encore

  • Description: The Java programming language has support for programmer-defined annotations using a simple annotation language. Programmers write interfaces that correspond to annotations that can be used to decorate types and declarations in code. The open-endedness of the system is a key property: it is possible to define completely new keywords without breaking Java syntax. Unless a plugin is loaded to make use of some specific annotations, those specific annotations are ignored. See the Java Checker Framework and JSR 308 for details.
  • Expected outcome: Encore programmer should be able to add custom keywords in key places which are parsed and added as meta data to the AST. Making use of the annotations is possibly out of scope for this thesis, but evaluation should include some simple checker,
  • Challenges: Designing a system for programmers to define custom annotations.
  • Desired skills/Interests: You'll need to have a solid understanding of Haskell. Preferably you should have taken a compilers course. You'll need to understand parsing well, and also be interested in designing a mini-language for annotations.

Default parameters

  • Description: Many languages support default parameters, i.e., where method parameters have some default values if not provided explicitly at the call-site. For example, C++ and Python support this by declaring something similar to "int foo = 4" in the argument list.
  • Expected outcome: Encore methods should have the ability to use default parameters in method declarations.
  • Challenges: Understanding the compiler.
  • Desired skills/Interests: You'll need to have a solid understanding of Haskell and C. Preferably you should have taken a compilers course.

Support for C#-style properties

  • Description: In C#, instance variables are abstracted into properties which can be configured as read-only/writeable/public etc., and from which accessor methods can be automatically generated.
  • Expected outcome: Encore programs should have a new construct for declaring properties similar to C# properties.
  • Challenges: Interaction with asynchronous semantics of Encore's active objects. Also, getting into the compiler.
  • Desired skills/Interests: You'll need to have a solid understanding of Haskell and C. Preferably you should have taken a compilers course.

Ongoing Projects and Completed Projects

The following projects are currently being taken by students or have been completed by
past students. If these sound interesting to you, a follow-on project may be possible.

Reagents in Encore

  • Description: Reagents are a high-level set of constructs useful for implementing lock-free algorithms. These hide low-level CAS operations from programmers and make reasoning about programs easier.
  • Expected Outcome: A library similar to Reagents.
  • Challenges: The programming model of Encore is quite different from that expected by reagents.
  • Desired Skills/Interests: High resilience to bugs.

SAT Solver in Encore

  • Description: Improve the implementation of an existing SAT solver written in Encore. Find the performance bottlenecks and eliminate them, find limitations in Encore and eliminate them (by implementing new language features), implement new heuristics, and so forth.
  • Expected Outcome: A SAT solver that is demonstrably more efficient than the current one. An extensive collection of benchmarks, including ones focussing on low-level aspects such as cache performance, amount of message passing, memory usage and so forth.
  • Desired Skills/Interests: Depending on the direction you want the project to go, either skill at benchmarking and improving program performance or interest in developing language features.

Add support for access modifiers

  • Description: Access modifiers exist in various forms in various programming languages. Java-style access modifiers, originating from Simula, allow controlling the visibility of methods etc. to other classes in a system. Eiffel supports a more fine-grained visibility protection with selective export. C++ has a friend construct, etc.
  • Expected outcome: Surveying existing access modifiers and selecting a subset and add them to Encore.
  • Challenges: Understanding the compiler. Interaction with the traits system.
  • Desired skills/Interests: You'll need to have a solid understanding of Haskell and C. Preferably you should have taken a compilers course.

DTrace

  • Description: DTrace allows the tracking of all sorts of events in program, which allows detailed benchmarking of many events of interest (number of calls to GC, amount of memory allocated and deallocated, etc). The aim of this project is to extend the Encore compiler to spit out DTRace code.
  • Desired Skills/Interests: Compiler hacking and C skills are essential. Note that DTrace will only work on Linux.

Package Manager for Encore

  • Description: Encore needs a package manager to manage 3rd party libraries. Taking inspiration from the likes of apt-get, AUR/packman, homebrew, but also gems, cabal, Racket's package manager etc., we want a way for programmers to download and also distribute Encore packages (as source) in a way that facilitates importing them in Encore programs, including version management and dependencies.
  • Expected outcome: An infrastructure for sharing, downloading, compiling and importing Encore source code.
  • Challenges: Mostly engineering
  • Desired skills/Interests: Preferable to have worked enough with software development to have at least once seen the kind of problems a package manager intends to handle

Implementing CRDTs (Convergent/Commutative Replicated Data Types) in Encore

  • Description: CRDTs are a kind of data types, typically found in a distributed setting, that have good properties in the presence of operations being performed out of order and failures. A simplified version of these should be useful for parallel computing applications.
  • Expected Outcome: A library of CRDTs and benchmarks demonstrating their (non)effectiveness.

If there's something else you are interested in that isn't on this list, send us an email or drop by for a chat.

Updated  2017-02-07 08:38:39 by Elias Castegren.