lunduniversity.lu.se

Computer Science

Faculty of Engineering, LTH

Denna sida på svenska This page in English

Google Research Award 2015

Supporting concurrent analyses in interactive programming tools

PI: Görel Hedin

Google sponsor: Emma Söderberg

PhD Student: Jesper Öqvist

In this project we are working on concurrent evaluation algorithms for reference attribute grammars. The algorithms are implemented in the open-source JastAdd metacompilation system.

Results so far

Updated 2016-08-16

  • Design of concurrent evaluation algorithms for all kinds of attributes in JastAdd: inherited, synthesized and parameterized attributes. Nonterminal attributes. Collection attributes. Circular attributes. Rewrites (based on CNTAs - circular nonterminal attributes).
  • Open-source implementation of the above algorithms in JastAdd (see http://jastadd.org).
  • The algorithms have been run successfully on a small compiler for a simple C-like language, with very promising results, obtaining speedup almost linear with the number of parallel processors. More thorough evaluation is ongoing.
  • The algorithms have been run successfully on the extensible Java compiler ExtendJ (http://extendj.org). This has entailed a number of improvements of ExtendJ:
    • Side-effects in attributes have been removed, making ExtendJ fully declarative.
    • Some attributes have been redesigned to improve both performance and readability.
    • A number of bugs have been fixed.
    So far we have not obtained any speedups, but the overhead has been reduced from x10 to around x2 through refactorings in ExtendJ, optimizations of the algorithms, and an improved cache configuration (see below). Being able to successfully run the algorithms on ExtendJ is a very valuable indication of the correctness of the algorithms, since ExtendJ makes extensive use of all types of attributes. Furthermore, the work has had the positive side effect that ExtendJ now is substantially improved, both concerning design and correctness, which will benefit all users of ExtendJ.
  • The algorithms have been run sucessfully on the compiler for Bloqqi, an open source diagram language (https://bitbucket.org/bloqqi/).
  • Ongoing investigations into RAG design principles to enable parallel evaluation to result in speedups. Experiments on ExtendJ and other compilers. Being able to obtain speedups for ExtendJ would be an important breakthrough, but might require substantial additional refactorings of ExtendJ.
  • Ongoing work on using a genetic algorithm for tuning attribute caching to improve parallel evaluation performance. So far, tuning has enabled us to reduce the overhead for running the parallel algorithms on ExtendJ from x4 to x2.