Adaptive Just-In-Time Parallelisation (AJITPar)

A key element of the multicore software crisis is a lack of abstraction: most parallel code mixes coordination and computation, and assumptions about the architecture are often hard-coded, tying the code to a specific architecture. For problems with regular parallelism, i.e. where the number and size of subproblems can be statically predicted, good parallel performance on an architecture can be obtained using static techniques including static compilation. However, many problems are irregular and require dynamic techniques such as we propose.

This project aims to address the challenges of programs with irregular parallelism by sharing the burden of parallel coordination between the programmer and an adaptive runtime system. The approach can be summarised in the slogan "The programmer knows the problem, the runtime knows the hardware." That is, the programmer merely exposes the parallelism in the problem domain by means of architecture-independent declarative constructs, and the runtime system decides how to map the parallelism to a specific architecture. The project aims for a framework combining portable parallel performance across a range of architectures with "compile once, run anywhere" portable binaries. The project will test whether portable performance has been achieved by comparing the parallel performance of a suite benchmarks on several parallel architectures, from standard desktop workstations to high-end compute clusters.

The proposed research will advance the state-of-the-art in two areas.
(1) The development of runtime systems that tightly integrate dynamic scheduling of parallelism with dynamic trace-based just-in-time (JIT) compilation.
(2) The systematic investigation into how to specialise architecture-independent declarative parallelism to a specific architecture at runtime by means of declarative and modular code transformations.
Crucially, both novelties need to be combined; neither can deliver portable parallel performance on its own. The parallelising JIT runtime system may not find the "right" amount of parallelism without dynamically applying code transformations, and the transformations cannot in general be applied statically because they require knowledge of runtime timing data.

The research is timely in exploiting emergent trace-based JIT technology. Moreover, the project has enormous transformative potential. It investigates JIT parallelisation using Haskell because its pure functional context enables safe code transformation. If successful, however, the techniques established can be used to transform the parallel portability of software in many programming languages with JIT compilers, not least "functional second" languages like JavaScript, Python, Scala and C#. Moreover, a JIT compiler's innate ability to optimise traces spanning several layers of the software stack enables a parallelising JIT runtime to exploit potential parallelism uniformly across all software layers and components.

JIT compilers for languages like Java or JavaScript have spread widely in recent years, being deployed on a wide variety of architectures, from smart phones to desktop computers to web servers. Because of its transformative potential, the design and implementation of a parallelising JIT compiler for Haskell will be followed with interest by implementers of parallel languages in the UK and abroad, both academic and in industry, e.g. at Microsoft, Google, Mozilla.

This speculative project will be undertaken by an experienced and energetic team in a vibrant environment. The team will be led by Professor Phil Trinder, who has 20 year's experience in the field, delivering 13 successful research projects, and with over 100 publications. Dr. Maier contributes deep knowledge of parallel language implementation and program analysis.

The applicants have an excellent track record in maximising research impact, and some relevant examples are as follows. The SCSCP protocol developed in a series of multidisciplinary parallel Computer Algebra projects has become a de facto standard with implementations in 9 Computer Algebra Systems (including Maple and MATLAB) and several languages (including Java, C/C++, Haskell). The HLDTS EPSRC project evaluated Erlang for telecommunications servers in conjunction with Motorola UK Research Labs. The project produced 6 conference publications and 2 journal papers; slides comparing C++ with Erlang have had 16K views on Reddit; several product groups in Motorola started using Erlang; the DM prototype we constructed became a mission-critical Motorola product; two Erlang evangelists were established within Motorola. HLDTS lead to the 3.6M Euro FP7 RELEASE project that aims to improve the scalability of Erlang on large commodity servers. The project, coordinated by Prof Trinder, engages both multinationals like Ericsson and EDF, but also a UK SME, Erlang Solutions.

The project will develop a prototype Haskell compiler, and the technology may be incorporated in GHC. This would convey considerable economic benefits as the user bases of both Haskell and GHC are substantial and growing extremely rapidly. Even greater impact would follow if ``functional second'' languages with very large developer communities, like JavaScript, Python, Scala, and C#, took up the technology.

Software is of strategic importance in a technological economy. An example is the Digital Economy, which already requires software that delivers good parallel performance on evolving parallel architectures. If successful the proposed research will help alleviate the parallel software crisis that is impinging on all software. Specifically, the technology has the potential to reduce the time and costs for development, and for porting between architectures, hence reducing the cost of products and their time to market.

UK society is increasingly dependent on a technological infrastructure that incorporates distributed and embedded software systems in an essential way; examples include cloud services (£2.4bn/year, set to grow to £6.1bn/year by 2014), telecommunication networks (£5bn/year) and mobile devices (£4bn/year). However, complexity is exploding with the increasing number, diversity, and parallel capabilities of the hardware architectures these software systems are deployed on. A unifying software framework, such as a portable bytecode format and JIT compiler ensuring performance-preserving portability between architectures, would help bring complexity back under control. If successful the proposed research will provide such a framework, thereby facilitating continued cost-effective infrastructure development and maintenance. This will help the UK maintain its European lead in tech infrastructure, benefiting society as a whole.

Our impact strategy is to engage both industry and academia, maintaining a web 2.0 presence facing both communities, e.g. hosting academic publications, releasing open source software, and blogging/slide-sharing in industrial fora. We will present and debate at academic conferences, at industrial fora like Techmeetup, through networks of excellence like HiPEAC, and via web technology, e.g. appropriate Google groups, email lists, wikis, etc. We will also publish in premier journals and via Heriot-Watt web pages and press releases. We will exploit our close personal links with the GHC team at Microsoft Research Labs in Cambridge to disseminate our results.

The project will train a PhD student to become an expert engineer on programming language support for manycore architectures. Such engineers are in extremely short supply and can have significant economic impact. Additionally, we will expose students to the AJITPar compiler in courses on parallel programming, thereby disseminating our results and training future developers.