Flocc (Functional language on compute clusters) compiler prototype.
Web: http://www.flocc.net/ Author: Tristan Aubrey-Jones 2010 Email: developer at flocc dot net
This code is a experimental prototype compiler for a data-parallel programming language called Flocc, which stands for "Functional language on Compute clusters". As the name suggests Flocc is a functional programming language, which is designed for writing high-level data-parallel algorithms to run on clusters.
How does it work? Flocc programs use a simple minimal functional language (e.g., it doesn't even support currying currently) and data-parallel operators implemented as higher-order functions (or "combinators"), which are just functions that take functions as arguments. Each of these data-parallel combinators can be implemented in different ways, with different data-distributions, on a machine with distributed-memory, like a cluster. Internally, the compiler therefore has multiple implementations of each high-level combinator which distribute their inputs and outputs in different ways. The compiler searches, considering using different implementations for each combinator function call, and generating code (in C++ using MPI) for each. These C++ implementations are compiled, executed, and their runtime is measured. These runtimes are fed back into the search, so that the compiler tries to find the fastest implementation of the original program - completely automatically!
What's under the hood? Behind the scenes the compiler uses types and type inference (very similar to the let-polymorphic types in ML) to encode the data distributions of the different distributed-memory implementations of the combinators, and to automatically synthesize approprate data distributions for candidate implementations. When no data distribution types can be inferred, "redistribution functions" (that perform communications like Scatter or AlltoAllv on the cluster) are inserted to make the types unify. The search algorithms that have been most successful in finding the fastest implementations without considering all possible variants, are various genetic search algorithms. For more information please read our paper in the International Journal of Parallel Programming 2015 (T. Aubrey-Jones and B. Fischer) at http://www.flocc.net/hlpp14/
The Caveats: This code was developed for a PhD thesis (see http://www.flocc.net/thesis/), rather than for public use, and so is a very preliminary proof of concept. The planner currently performs and exhaustive search, and then uses the runtimes collected, to simulate how fast different search algorithms would converge to find the fastest implementation, rather than actually use that search algorithm to find a real implementation. The back end only supports key-value maps, and lists, and more back-end templates need to be written to support array-based algorithms. Furthermore, unfortunately, the code is currently in an inconsistant state. It was successfully used to generate code for several example programs, but since then the redistribution insertion code has been altered, and doesn't currently work. This needs to be re-implemented to fully implement algorithm 2 presented at the end of Chapter 5 of this PhD thesis. Furthermore, the current DDL type inference algorithm (in Compiler.Types2) needs to be checked to make sure it properly conforms to the one given in Chapter 5. In particular, the normalization function must implement the down-arrow algorithm in Chapter 5. If you are interested in forking, using, adapting the code, please do get in touch by emailing developer at flocc dot net.
More information: For more information please see http://www.flocc.net/ and particularly my PhD thesis, which explains the concepts behind Flocc, its compilation mechanism, and implementation, in detail.
Whats in the name? Functional languages involve anonymous functions called "lambda-abstractions". When run on clusters, Flocc programs conceptually evaluate many lambda-abstractions in parallel, and therefore resemble a "Flocc of lambdas". (Yeah I know, it's the best I could come up with!)