fusion.rst

Fusion and List Homomorphisms

In this chapter, we outline the general SOAC reasoning principles that lie behind both the philosophy of programming with arrays in Futhark and the techniques used for allowing certain programs to have efficient parallel implementations. We shall discuss the reasoning principles in terms of Futhark constructs but introduce a few higher-order concepts that are important for the reasoning.

We first discuss the concept of fusion, which aims at eliminating intermediate arrays while still allowing the Futhark programmer to express an algorithm using simple SOACs and their associated reasoning principles.

We then introduce the concept of list homomorphism through a few examples.

Fusion

Fusion aims at reducing the overhead of unnecessary repeated control-flow or unnecessary temporary storage. In essence, fusion is defined in terms of a number of fusion rules, which specify how a Futhark (intermediate) expression can be transformed into a semantically equivalent expression.

The rules make use of the auxiliary higher-order functions for, for instance, function composition, presented in :numref:`higher-order-functions`.

The first fusion rule, F1, which says that the result of mapping an arbitrary function f over the result of mapping another arbitrary function g over some array a is identical to mapping the composed function f <-< g over the array a. The first fusion rule is also called map-map fusion and can simply be written

map f <-< map g = map (f <-< g)

Given that f and g denote the Futhark functions \x -> e and \y -> e', respectively (possibly after renaming of bound variables), the function product of f and g, written f <*> g, is defined as \(x,y) -> (f x, g y).

Now, given functions f:a->b and g:a->c, the second fusion rule, F2, which denotes horizontal fusion, is given by the following equation:

(map f <*> map g) <-< dup = map ((f <*> g) <-< dup)

Here dup is the Futhark function \x -> (x,x).

The fusion rules that we have presented here generalise to functions that take multiple arguments by applying zipping, unzipping, currying, and uncurrying strategically. Notice that due to Futhark's strategy of automatically transforming arrays of tuples into tuples of arrays, the applications of zipping, unzipping, currying, and uncurrying have no effect at runtime.

Futhark applies a number of other fusion rules, which are based on the fundamental property that Futhark's internal representation is based on a number of composed constructs (e.g., named scanomap and redomap). These constructs turn out to fuse well with map.

Parallel Utility Functions

For use by other algorithms, a set of utility functions for manipulating and managing arrays is an important part of the tool box. We present a number of utility functions here, ranging from finding elements in an array to finding the maximum element and its index in an array.

Finding the Index of an Element in an Array

We device two different functions for finding an index in an array for which the content is identical to some given value. The first function, find_idx_first, takes a value e and an array xs and returns the smallest index i into xs for which xs[i] = e:

.. literalinclude:: src/find_idx.fut
   :lines: 4-8

The second function, find_idx_last, also takes a value and an array but returns the largest index i into xs for which xs[i] = e:

.. literalinclude:: src/find_idx.fut
   :lines: 10-13

The above two functions make use of the auxiliary functions i32.max and i32.min.

Finding the Largest Element and its Index in an Array

Futhark allows for reduction operators to take tuples as arguments. This feature is exploited in the following function, which implements a homomorphism for finding the largest element and its index in an array:

.. literalinclude:: src/maxidx.fut
   :lines: 4-8

The function is a homomorphism :cite:`BirdListTh`: For any x and y, and with ++ denoting array concatenation, there exists an associative operator \oplus such that

\kw{maxidx}(x \pp y) = \kw{maxidx}(x) \oplus \kw{maxidx}(y)

The operator \oplus = \kw{mx}. We will leave it up to the reader to verify that the maxidx function will operate efficiently on large inputs.

Radix Sort Revisited

A simple radix sort algorithm was presented already in :numref:`radixsort`. In this section, we present two generalized versions of radix sort, one for ascending sorting and one for descending sorting. As a bonus, the sorting routines return both the sorted array and an index array that can be used to sort an array with respect to a permutation obtained by sorting another array. The generalised ascending radix sort is as follows:

.. literalinclude:: src/rsort_idx.fut
   :lines: 14-31

And the descending version as follows:

.. literalinclude:: src/rsort_idx.fut
   :lines: 33-49

Notice that in case of identical elements in the source vector, one cannot simply implement the ascending version by reversing the arrays resulting from calling the descending version.

Finding the Longest Streak

In this section, we shall demonstrate how to write a function for finding the longest streak of increasing numbers. Here is one possible implementation of the function:

.. literalinclude:: src/streak.fut
   :lines: 22-35

The following derivation shows how the algorithm works for a particular input, namely when stream is given the argument array [1,5,3,4,2,6,7,8], in which case the algorithm should return the value 3:

Variable
xs	=	1	5	3	4	2	6	7	8
ys	=	5	3	4	2	6	7	8	1
is	=	1	0	1	0	1	1	1
ss	=	1	1	2	2	3	4	5
ss	=	0	1	0	2	0	0	0
ss2	=	0	1	1	2	2	2	2
ss3	=	1	0	1	0	1	2	3
res	=	3

In :numref:`finding-the-longest-streak-segmented-scan` we present a simpler algorithm, which builds directly on the concept of a so-called segmented scan.