PRC: Phil Recompiles Code
Introduction
============
This repo is home to an experimental compiler for taking advantage of the
parallelism implicit in non-strict functional languages. You can write a
program in F-Lite (which is a subset of Haskell) and get out a parallelised
version of the program.
This idea is not new. In fact it's as old as functional languages themselves.
Lots of work was undertaken in the 1980's and early 1990's towards exploiting
implicit parallelism. It turned out to be a hard problem, much of the
complication was due to the *granularity problem*.
The Granularity Problem
-----------------------
Static analysis technique for non-strict and pure functional languages are
pretty powerful. Because of this, find the *safe* parallelism in a program is
not too hard. Things like strictness analysis, usage analaysis, and path
analysis can all help you determine what *could* be executed in parallel.
The problem: just because we *can* do something in parallel doesn't mean we
*should*.
Parallelism incurs cost. That cost comes from all sorts of sources;
communication through shared memory, message passing, worsened cache behavior
due to context switching etc. These costs are **very** difficult to predict
with static analysis.
If the benefit (how much a computation contributes towards the goal of the
program) of a parallel task is smaller than its cost (the time taken up by the
overheads of introducing and managing the parallel task) we actually slow down
our program by parallelising it!
So determining which parallel tasks would actually benefit the overall
computation is known as the granularity problem.
Our Approach
============
So while our static analysis can tell us where to evaluate something in
parallel, we're stuck using ugly heuristics and imperfect cost-semantics to
tell us whether we should. This is not ideal.
Instead, what if we actually *run* the program? This way we can profile the
parallelism in the program and determine which parallel tasks are not
worthwhile.
How we do it
============
Our approach has 3 main parts:
1. First we use some well-studied static analysis techniques to find the *safe*
parallelism in our program
2. We introduce `par` annotations in order to evaluate the safe parallel tasks
3. We run the program and determine what parallelism can be turned off. We keep
running the program until turning off any more parallelism slows the program
down