Full flattening of nested data parallelism
The Futhark Programming Language
High-performance purely functional data-parallel array programming
Overview<br>Examples<br>Docs<br>Publications<br>Gotta Go Fast!<br>Get Involved<br>Blog
Fork me on GitHub
Full flattening of nested data parallelism
Posted on July 31, 2026
Bottom line up front: this long blog post describes the culmination of a<br>years-long effort that means that we can now, modulo compiler bugs and a few<br>unimportant edge cases, compile any Futhark program to parallel GPU code.
Introduction
One of the most interesting implementation challenges in Futhark is how to map<br>nested parallelism, in which parallel operations can contain other parallel<br>operations, to flat parallelism. This challenge arises because much<br>interesting hardware (such as GPUs) does not efficiently support nested<br>parallelism, and even on CPUs, arbitrary nesting may have significant run-time<br>costs. Futhark has for a long time supported flattening only a limited (although<br>important) subset of programs, called regular nested parallelism (as opposed<br>to irregular), which meant that there were programs that we were unable to<br>compile to GPU code. In 2022 I began an experimental implementation of “full<br>flattening”, which as of this<br>writing is the longest open pull request on the Futhark repository. I got far<br>enough to build a proof of concept, but the sheer amount of effort involved led<br>to the work stagnating - until now. Largely due to the efforts of students, we<br>are now close to having a complete reimplementation of flattening in Futhark.
The main contributions have been by Cornelius<br>Sevald-Krause who<br>implemented function and match lifting in his BSc<br>thesis, and<br>particularly by Amirreza Hashemi whose MSc work has been a whirlwind of<br>finishing everything else. This includes various crucial optimisations in<br>order to reach functionality and performance parity with the old<br>flattener.<br>I cannot overstate how impressive it is to come up with a systematic and<br>maintainable replacement for a ten-year-old compiler pass that is full of<br>optimisation heuristics.
This post will introduce the basic problem of flattening, go through some of the<br>various challenges, and explain how we have resolved them in the<br>soon-to-be-merged work on the Futhark compiler. Flattening has a long academic<br>pedigree, and I will try to link relevant other work, but this post is not a<br>systematic survey of prior work. I will ignore most of the nontrivial<br>bookkeeping that a compiler needs to do to actually implement all of this stuff,<br>and instead focus on the intuition of how programs are transformed.
I should mention up front what the goal is of this work: the new flattening<br>transformation should not reduce performance for programs that already worked<br>with the old implementation, but we are less concerned with the performance of<br>programs that did not work before. As we shall see, achieving truly good<br>performance on arbitrarily irregular nested parallelism is a major research<br>problem in itself, and one that we intend to address incrementally in the time<br>to come.
Also, this is a long post. I have tried to make everything here relatively<br>high-level, but you may want to skip to the reflections at the bottom if things<br>drag on too much for your taste.
Basics of flattening
To motivate flattening, we’ll be assuming a slightly caricatured view of what a<br>GPU can do. Expanding to full GPU functionality does not fundamentally change<br>the story; it just means I would need more convoluted examples. Also, despite<br>this post focusing on GPUs, you can mentally substitute “efficient but<br>restricted processors” instead - these concerns crop up with any kind of vector<br>processing.
In the language of functional programming, we’ll start by assuming that a GPU<br>can efficiently execute a map where the function contains sequential code, and<br>where all memory for intermediate results can be allocated in advance. To avoid<br>writing zip/unzip all the time, we’ll also suppose that our maps accept<br>any number of arrays. This, for example, is something we can efficiently execute<br>on a GPU:
map (\x y -> x + y) xs ys
(Incidentally, when describing the transformations to follow, it would be much<br>simpler if map accepted its arrays before the lambda, like we do in<br>Futhark’s IR - but I didn’t want to go that far in a blog post.)
It is easy to imagine that this can be turned into a GPU program with one thread<br>per iteration of the map. Apart from a single map with sequential code,<br>we’ll also allow any nesting of maps. So this is also efficient:
map (\xs ys -> map (\x y -> x + y)<br>xs ys)<br>xss yss
It is similarly easy to imagine that these maps can be collapsed, with one GPU<br>thread for every iteration of the innermost map.
In addition to arbitrary sequential code, we will also allow the innermost<br>operation to be a single parallel operation, such as a scan, a reduction, a<br>transpose - the precise collection doesn’t really matter. Then this is also<br>efficient:
map (\xs -> reduce...