The flattening transformation is an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

that transforms nested

data parallelism Data parallelism is parallelization across multiple processors in parallel computing environments. It focuses on distributing the data across different nodes, which operate on the data in parallel. It can be applied on regular data structures like ...

into flat data parallelism. It was pioneered by Guy Blelloch as part of the NESL programming language. The flattening transformation is also sometimes called vectorization, but is completely unrelated to

automatic vectorization Automatic vectorization, in parallel computing, is a special case of automatic parallelization, where a computer program is converted from a scalar implementation, which processes a single pair of operands at a time, to a vector implementatio ...

. The original flattening algorithm was concerned solely with first-order multidimensional arrays containing primitive types, but was extended to handle higher-order and recursive data types in the work on Data Parallel Haskell.

Overview

Flattening works by ''lifting'' functions to operate on arrays instead of on single values. For example, a function

f : A \rightarrow B

is lifted to a function

f' : \rightarrow /math>.  This means an expression map~f~x can be replaced with an application of the lifted function: f'~x .  Intuitively, flattening thus works by replacing all function applications with applications of the corresponding lifted function.

After flattening, arrays are represented as single-dimensional value vector ''V'' containing scalar elements, alongside auxiliary information recording the nested structure, typically in the form of a boolean flag vector ''F''.  The flag vector indicates, for the corresponding element in the value vector, whether it is the beginning of a new ''segment''.   For example, the two-dimensional irregular array A= 1,2,3,5 [], [6 can be represented as the data vector V = [1,2,3,4,5,6,7] alongside the flag vector F = [1, 0, 0, 1, 0, 1, 1] .

This flag vector is necessary in order to correctly flatten nested parallelism.  For example, it is used in the flattening of

prefix sum In computer science, the prefix sum, cumulative sum, inclusive scan, or simply scan of a sequence of numbers is a second sequence of numbers , the summation, sums of Prefix (computer science), prefixes (running totals) of the input sequence: : : : ...

to segmented scan. Flattening can increase the asymptotic work and space complexity of the original program, leading to a much less efficient result.

Usage

Flattening was originally developed for vector machines such as the

Connection Machine The Connection Machine (CM) is a member of a series of massively parallel supercomputers sold by Thinking Machines Corporation. The idea for the Connection Machine grew out of doctoral research on alternatives to the traditional von Neumann arch ...

, and often produces code that is not a good fit for modern

multicore A multi-core processor (MCP) is a microprocessor on a single integrated circuit (IC) with two or more separate central processing units (CPUs), called ''cores'' to emphasize their multiplicity (for example, ''dual-core'' or ''quad-core''). Ea ...

CPUs. However, the principles underlying its simpler cases can be found in constructs such as the vmap in

Google Jax JAX is a Python library for accelerator-oriented array computation and program transformation, designed for high-performance numerical computing and large-scale machine learning. It is developed by Google with contributions from Nvidia and other c ...

References

{{Reflist Compiler optimizations Parallel computing