Automatic SIMD Vectorization for Haskell and ICFP 2013

I had a great time at ICFP 2013 this year where I presented my paper “Automatic SIMD Vectorization for Haskell”, which was joint work with Leaf Petersen and Neal Glew of Intel Labs. The full paper and slides are available online. Our paper details the vectorization process in the Intel Labs Haskell Research Compiler (HRC) which gets decent speedups on numerical code (between 2-7x on 256-bit vector registers). It was nice to be able to talk about HRC and share the results. Paul (Hai) Liu also gave a talk at the Haskell Symposium which has more details about HRC than the vectorization paper (see the paper here with Neal Glew, Leaf Petersen, and Todd Anderson). Hopefully there will be a public release of HRC in future.  

Still more to do

It’s been exciting to see the performance gains in compiled functional code over the last few years, and its encouraging to see that there is still much more we can do and explore. HRC outperforms GHC on roughly 50% of the benchmarks, showing some interesting trade-offs going on in the two compilers. HRC is particularly good at compiling high-throughput numerical code, thanks to various strictness/unboxing optimisations (and the vectorizer), but there is still more to be done.

Don’t throw away information about your programs

One thing I emphasized in my talk was the importance of keeping, not throwing away, the information encoded in our programs as we progress through the compiler stack. In the HRC vectorizer project, Haskell’s Data.Vector library was modified to distinguish between mutable array operations and “initializing writes”, a property which then gets encoded directly in HRC’s intermediate representation. This makes vectorization discovery much easier. We aim to preserve as much effect information around as possible in the IR from the original Haskell source.

This connected nicely with something Ben Lippmeier emphasised in his Haskell Symposium paper this year (“Data Flow Fusion with Series Expressions in Haskell“, joint with Manuel Chakravarty, Gabriele Keller and Amos Robinson). They provide a combinator library for first-order non-recursive dataflow computations which is guaranteed to be optimised using flow fusion (outperforming current stream fusion techniques). The important point Ben made is that, if your program fits the pattern, this optimisation is guaranteed. As well as being good for the compiler, this provides an obvious cost model for the user (no more games trying to coax the compiler into optimising in a particular way).

This is something that I have explored in the Ypnos array language, where the syntax is restricted to give (fairly strong) language invariants that guarantee parallelism and various optimisations, without undecidable analyses. The idea is to make static as much effect and coeffect (context dependence) information as possible. In Ypnos, this was so successful that I was able to encode the Ypnos’ language invariant of no out-of-bounds array access directly in Haskell’s type system (shown in the DSL’11 paper; this concept was also discussed briefly in my short language design essay).

This is a big selling point for DSLs in general: restrict a language such that various program properties are statically decidable, facilitating verification and optimisation.

Ypnos has actually had some more development in the past year, so if things progress further, there may be some new results to report on. I hope to be posting again soon about more research, including the ongoing work with Tomas Petricek on coeffect systems, and various other things I have been playing with. – D

The Four Rs of Programming Language Design (revisited)

Following my blog post last year about the “four Rs of programming language design” I wrote a short essay expanding upon the idea which has now been included in the online post-proceedings of the ACM Onward ’11 essay track (part of the SPLASH conference).

The essay was a lot of fun to write (I somehow end up referencing books from the 19th century, a sci-fi novel, 1984, and The Matrix!) and is a kind of mission statement (at least for myself) for language design; it is available on my research page here. I hope that it provides some food-for-thought for others interested in, or working in, language design.

The four “R”s of programming language design

Because I have some serious work to do for an impending deadline I have become particularly good at inventing ways to not work that I can convince myself are “worthwhile”. To this end I have decided to post on my (dead) blog, which I am planning to revive with at least monthly posts.

Last year the Cambridge Computer Lab started an informal lecture course taught by PhD students aimed at final year undergraduates and MPhil students with the rough aim of providing lecturing experience to PhD students, and for disseminating more ideas from research to undergrads/MPhils/each other. In my group, the CPRG (Cambridge Programming Research Group), part of the bigger PLS (Programming, Logic, and Semantics Group), four of us decided to do a mini-series about aspects of programming language design. The slides/notes from our lectures can be found here on the dates of May 10th, 11th, 14th, and 24th.

To bind the mini-series together we prepared an informal, general summary of the ideas contained within which concludes with the summary:

The development of programming languages, and abstraction away from
machine code, has greatly aided software development. Programming lan-
guages are a conduit between man and machine, with much of programming
language research aiming to improve this interaction and to help us better
express our ideas. We can attempt to improve languages for ease of reading,
ease of writing, and ease of reasoning, and improve our evaluation systems
to use less resources (whether it be processor time, memory, power, etc.)
whilst still providing a predictable system. Such facets of programming
language design are often non-orthogonal, thus a language designer must
trade-off certain improvements for others. Often, a motivating application
domain or purpose can help distill which features of a language are most
important. This lecture series should give some food for thought in various
areas of general programming and programming language design.

From which I offered the following general slogan:

The four “R”s that programming language design must improve of programs: reading, ‘riting, reasoning, and running.

A bit of a generalisation perhaps, but hopefully a useful “elevator-pitch” slogan to get more people thinking about programming language design, and with a bit of humour (see The three Rs).