Full flattening of nested data parallelism

嵌套数据并行的完全扁平化

The Futhark Programming Language Futhark 编程语言

Bottom line up front: this long blog post describes the culmination of a years-long effort that means that we can now, modulo compiler bugs and a few unimportant edge cases, compile any Futhark program to parallel GPU code. 核心结论先行： 这篇长博文描述了一项历时多年工作的结晶。这意味着，除了编译器漏洞和少数无关紧要的边缘情况外，我们现在可以将任何 Futhark 程序编译为并行 GPU 代码。

Introduction

引言

One of the most interesting implementation challenges in Futhark is how to map nested parallelism, in which parallel operations can contain other parallel operations, to flat parallelism. This challenge arises because much interesting hardware (such as GPUs) does not efficiently support nested parallelism, and even on CPUs, arbitrary nesting may have significant run-time costs. Futhark 最有趣的实现挑战之一是如何将嵌套并行（即并行操作中包含其他并行操作）映射为扁平并行。这一挑战的产生是因为许多主流硬件（如 GPU）并不高效支持嵌套并行，即使在 CPU 上，任意嵌套也可能带来显著的运行时开销。

Futhark has for a long time supported flattening only a limited (although important) subset of programs, called regular nested parallelism (as opposed to irregular), which meant that there were programs that we were unable to compile to GPU code. In 2022 I began an experimental implementation of “full flattening”, which as of this writing is the longest open pull request on the Futhark repository. I got far enough to build a proof of concept, but the sheer amount of effort involved led to the work stagnating - until now. 长期以来，Futhark 仅支持对程序中有限（尽管很重要）的子集进行扁平化，即“规则嵌套并行”（相对于不规则嵌套而言），这意味着有些程序我们无法将其编译为 GPU 代码。2022 年，我开始尝试实现“完全扁平化”，截至本文撰写时，这仍是 Futhark 仓库中开启时间最长的 Pull Request。我当时完成了概念验证，但由于工作量巨大，该项目一度停滞——直到现在。

Largely due to the efforts of students, we are now close to having a complete reimplementation of flattening in Futhark. The main contributions have been by Cornelius Sevald-Krause who implemented function and match lifting in his BSc thesis, and particularly by Amirreza Hashemi whose MSc work has been a whirlwind of finishing everything else. This includes various crucial optimisations in order to reach functionality and performance parity with the old flattener. 主要得益于学生们的努力，我们现在即将完成 Futhark 扁平化功能的全面重构。主要贡献者包括 Cornelius Sevald-Krause，他在学士论文中实现了函数和匹配提升（match lifting）；特别是 Amirreza Hashemi，他的硕士研究工作以惊人的速度完成了其余所有工作。这包括为了达到与旧版扁平化器功能和性能相当而进行的各种关键优化。

I cannot overstate how impressive it is to come up with a systematic and maintainable replacement for a ten-year-old compiler pass that is full of optimisation heuristics. This post will introduce the basic problem of flattening, go through some of the various challenges, and explain how we have resolved them in the soon-to-be-merged work on the Futhark compiler. 我无法用言语形容，为一个充满优化启发式算法、已有十年历史的编译器过程开发出一种系统且可维护的替代方案是多么令人印象深刻。本文将介绍扁平化的基本问题，梳理其中的各种挑战，并解释我们如何在即将合并到 Futhark 编译器的成果中解决这些问题。

Basics of flattening

扁平化的基础

To motivate flattening, we’ll be assuming a slightly caricatured view of what a GPU can do. Expanding to full GPU functionality does not fundamentally change the story; it just means I would need more convoluted examples. Also, despite this post focusing on GPUs, you can mentally substitute “efficient but restricted processors” instead - these concerns crop up with any kind of vector processing. 为了说明扁平化的动机，我们将假设 GPU 的功能处于一种略显简化的状态。扩展到完整的 GPU 功能并不会从根本上改变故事的本质，只是意味着我需要举出更复杂的例子。此外，尽管本文侧重于 GPU，你也可以在脑海中将其替换为“高效但受限的处理器”——这些问题在任何类型的向量处理中都会出现。

In the language of functional programming, we’ll start by assuming that a GPU can efficiently execute a map where the function contains sequential code, and where all memory for intermediate results can be allocated in advance. To avoid writing zip/unzip all the time, we’ll also suppose that our maps accept any number of arrays. This, for example, is something we can efficiently execute on a GPU: map (\x y -> x + y) xs ys 在函数式编程的语境下，我们首先假设 GPU 可以高效执行 map 操作，其中函数包含顺序代码，且所有中间结果的内存都可以预先分配。为了避免频繁编写 zip/unzip，我们假设我们的 map 可以接受任意数量的数组。例如，以下代码可以在 GPU 上高效执行：map (\x y -> x + y) xs ys

It is easy to imagine that this can be turned into a GPU program with one thread per iteration of the map. Apart from a single map with sequential code, we’ll also allow any nesting of maps. So this is also efficient: map (\xs ys -> map (\x y -> x + y) xs ys) xss yss 很容易想象，这可以转化为一个 GPU 程序，其中 map 的每次迭代对应一个线程。除了包含顺序代码的单个 map 外，我们还允许任意嵌套的 map。因此，以下代码也是高效的：map (\xs ys -> map (\x y -> x + y) xs ys) xss yss

It is similarly easy to imagine that these maps can be collapsed, with one GPU thread for every iteration of the innermost map. In addition to arbitrary sequential code, we will also allow the innermost operation to be a single parallel operation, such as a scan, a reduction, a transpose - the precise collection doesn’t really matter. Then this is also efficient: map (\xs -> reduce (+) 0 xs) xs 同样容易想象，这些 map 可以被合并，最内层 map 的每次迭代对应一个 GPU 线程。除了任意顺序代码外，我们还允许最内层操作是一个单一的并行操作，例如扫描（scan）、归约（reduction）或转置（transpose）——具体是什么操作并不重要。那么，以下代码也是高效的：map (\xs -> reduce (+) 0 xs) xs

Essentially, “efficient GPU code” means a tower of maps on top of some single parallel primitive operation (or sequential code). The reason these patterns are efficient is because we know how to generate efficient GPU kernels from these patterns. 本质上，“高效的 GPU 代码”意味着在某个单一并行原语操作（或顺序代码）之上的一系列 map 堆栈。这些模式之所以高效，是因为我们知道如何从这些模式中生成高效的 GPU 内核。