Fork me on GitHub

Docs

The Futhark documentation is divided into several parts. The in-progress book Parallel Programming in Futhark can be read freely online, and is the starting point for learning Futhark. The Futhark User's Guide contains detailed instructions on how to use the compilers, as well as the language reference and instructions on how to install the Futhark compiler.

There is also automatically generated documentation for the Futhark Basis Library. The basis library is very small, so in most cases you will want to use external packages.

If there is something you believe should be documented, but is not, you are very welcome to report the omission as a bug on our bug tracker. See the page Get Involved for more information.

We also have some Haddock-generated documentation of the compiler internals which is automatically updated every night.

Tools

Publications

We have published a number of papers on Futhark, and hopefully more will follow in the future. They are presented below in reverse chronological order.

Static Interpretation of Higher-Order Modules in Futhark

Presented at ICFP '18 (pdf, bib)

This paper discusses the higher-order ML-style module system available in Futhark. Most of the discussion is a theoretical treatment, including a formally-verified implementation in Coq. The implementation in the Futhark compiler does not use this verified implementation for a variety of reasons, but it does almost exactly follow the semantic object definitions given in the paper.

Modular Acceleration: Tricky Cases of Functional High-Performance Computing

Presented at FHPC '18 (pdf, bib)

This case study examines the data-parallel functional implementation of three algorithms: generation of quasi-random Sobol numbers, breadth-first search, and calibration of Heston market parameters via a least-squares procedure. We show that while all these problems permit elegant functional implementations, good performance depends on subtle issues that must be confronted in both the implementations of the algorithms themselves, as well as the compiler that is responsible for ultimately generating high-performance code. In particular, we demonstrate a modular technique for generating quasi-random Sobol numbers in an efficient manner, study the efficient implementation of an irregular graph algorithm without sacrificing parallelism, and argue for the utility of nested regular data parallelism in the context of nonlinear parameter calibration.

Design and Implementation of the Futhark Programming Language

Troels Henriksens PhD thesis (revised), defended in November of 2017 (pdf, bib)

This PhD thesis describes the overall background and motivation behind the development of Futhark, as well as a collection of some of the core implementation techniques (size-dependent typing, fusion, moderate flattening, tiling). The treatment is high level, and the technicalities of the concrete compiler implementation is not discussed in great detail. The first part of the thesis describes the overall philosophy behind the design and implementation of Futhark, and is fairly readable. The latter part of the thesis, which discusses concrete program transformations, is a more difficult read, and probably only of interest to academics. The empirical evaluation chapter is a good description of what Futhark does well, and what it does not so well (at least as of the time the thesis was written).

Strategies for Regular Segmented Reductions on GPU

Presented at FHPC '17 (pdf, bib)

A description of an implementation technique for regular segmented reductions on GPU. The technique is based on having three different strategies for dealing with different problem classes. This is the technique currently used by the Futhark compiler, but it is presented in a general setting, and could be used by other libraries and languages that make use of regular segmented reductions.

Futhark: Purely Functional GPU-Programming with Nested Parallelism and In-Place Array Updates

Presented at PLDI '17 (pdf, bib)

A general and self-contained description of the main points of the design and implementation of Futhark, including pieces of fusion, a formalisation of the uniqueness typing rules, and our mechanism for kernel extraction. The latter is the main novelty, as it allows the Futhark compiler to exploit regular nested parallelism in a more efficient (albeit also more restricted) manner than full flattening, while still being more powerful than approaches that support only flat parallelism. The accompanying benchmark suite is freely accessible.

APL on GPUs - A TAIL from the Past, Scribbled in Futhark

Presented at FHPC '16 (pdf, bib)

A paper describing an APL compiler (apltail) that operates by translating APL into a typed array intermediate language (TAIL), and from there into Futhark. While the Futhark details are light, the paper demonstrates a simple use of Futhark as a target language for a compiler. We succeed in achieving decent speedup on several (small) APL programs. The accompanying benchmark suite may be worth a look.

Design and GPGPU Performance of Futhark’s Redomap Construct

Presented at ARRAY '16 (pdf, bib)

A detailed presentation of one of Futhark’s internal language constructs - redomap - which is used to represent various forms of map-reduce-fusion. We present some microbenchmarks implemented in both Thrust and Futhark and discuss their relative performance.

Size Slicing - A Hybrid Approach to Size Inference in Futhark

Presented at FHPC '14 (pdf, bib)

Futhark supports automatic size inference of arrays, and this paper describes our approach, which is based on slicing. The descriptions are still up-to-date, although the Futhark source language has since grown support for user-defined size annotations, which can sometimes enable the compiler to make better assumptions about the shapes of arrays.

Bounds Checking: An Instance of Hybrid Analysis

Presented at ARRAY '14 (pdf, bib)

We implemented a novel form of bounds checking by extracting predicate functions from programs with array indexing. These predicates functioned as sufficient conditions for all bounds checks in the original program: if the extracted predicates evaluated to true, then every array index was guaranteed to be in bounds. The idea is that this produces an efficient alternative to precise bounds checking even for very complicated accesses (such as indirect indexing). The idea works, but was hard to implement and maintain and thus distracted us from our core work, so it is no longer used in the Futhark compiler. Instead, we provide an unsafe keyword that one can use to remove bounds checks that would otherwise hinder parallelisation. In the future, we might return to this work.

A T2 Graph-Reduction Approach To Fusion

Presented at FHPC '13 (pdf, bib)

A presentation of the core of the producer-consumer fusion algorithm in the Futhark compiler (although the language was called L0 at the time). The description of the fundamental algorithm is still correct, although it does not cover some of the newer language additions, nor does it describe horisontal fusion.

Selected Student Projects