Array-valued collective computations

Multi-dimensional arrays for array processing.

If device and host memory are separate, arrays will be transferred to the device when necessary (if possible asynchronously and in parallel with other tasks) and cached on the device if sufficient memory is available.

Scalars arrays hold a single element

Vectors are one-dimensional arrays

Segment descriptor (vector of segment lengths).

To represent nested one-dimensional arrays, we use a flat array of data values in conjunction with a segment descriptor, which stores the lengths of the subarrays.

Accelerate supports as array elements only simple atomic types, and tuples thereof. These element types are stored efficiently in memory, unpacked as consecutive elements without pointers.

This class characterises the types of values that can be array elements, and hence, appear in scalar Accelerate expressions.

Rank-0 index

Increase an index rank by one dimension. The :. operator is used to construct both values and types.

Shapes and indices of multi-dimensional arrays

Marker for entire dimensions in slice descriptors.

For example, when used in slices passed to replicate, the occurrences of All indicate the dimensions into which the array's existing extent will be placed, rather than the new dimensions introduced by replication.

Marker for arbitrary shapes in slice descriptors. Such arbitrary shapes may include an unknown number of dimensions.

Any can be used in the leftmost position of a slice instead of Z, for example (Any :. _ :. _). In the following definition Any is used to match against whatever shape the type variable sh takes:

repN :: (Shape sh, Elt e) => Int -> Acc (Array sh e) -> Acc (Array (sh:.Int) e)
repN n a = replicate (constant $ Any :. n) a

Slices, aka generalised indices, as n-tuples and mappings of slice indices to slices, co-slices, and slice dimensions

Expression form that extracts a scalar from an array

Expression form that extracts a scalar from an array at a linear index

Extraction of the element in a singleton array

Test whether an array is empty

Get the length of a vector

Expression form that yields the shape of an array

Expression form that yields the size of an array

The total number of elements in an array of the given Shape

Index an array with a generalised array index, supplied as the second argument. The result is a new array (possibly a singleton) containing the selected dimensions (Alls) in their entirety.

This can be used to cut out entire dimensions. The opposite of replicate. For example, if mat is a two dimensional array, the following will select a specific row and yield a one dimensional result:

slice mat (lift (Z :. (2::Int) :. All))

A fully specified index (with no Alls) would return a single element (zero dimensional array).

Yield all but the last element of the input vector. The vector must not be empty.

Yield all but the first element of the input vector. The vector must not be empty.

Yield the first n elements of the input vector. The vector must contain no more than n elements.

Yield all but the first n elements of the input vector. The vector must contain no fewer than n elements.

Yield a slit (slice) from the vector. The vector must contain at least i + n elements. Denotationally, we have:

slit i n = take n . drop i

Array inlet: makes an array available for processing using the Accelerate language.

Depending upon the backend used to execute array computations, this may trigger (asynchronous) data transfer.

Scalar inlet: injects a scalar (or a tuple of scalars) into a singleton array for use in the Accelerate language.

Construct a new array by applying a function to each index.

For example, the following will generate a one-dimensional array (Vector) of three floating point numbers:

generate (index1 3) (\_ -> 1.2)

Or, equivalently:

generate (constant (Z :. (3::Int))) (\_ -> 1.2)

Finally, the following will create an array equivalent to '[1..10]':

generate (index1 10) $ \ ix ->
         let (Z :. i) = unlift ix
         in fromIntegral i

NOTE:

Using generate, it is possible to introduce nested data parallelism, which will cause the program to fail.

If the index given by the scalar function is then used to dispatch further parallel work, whose result is returned into Exp terms by array indexing operations such as (!) or the, the program will fail with the error: './Data/Array/Accelerate/Trafo/Sharing.hs:447 (convertSharingExp): inconsistent valuation @ shared 'Exp' tree ...'.

Replicate an array across one or more dimensions as specified by the generalised array index provided as the first argument.

For example, assuming arr is a vector (one-dimensional array),

replicate (lift (Z :. (2::Int) :. All :. (3::Int))) arr

yields a three dimensional array, where arr is replicated twice across the first and three times across the third dimension.

Create an array where all elements are the same value.

Create an array of the given shape containing the values x, x+1, etc (in row-major order).

Create an array of the given shape containing the values x, x+y, x+y+y etc. (in row-major order).

Concatenate outermost component of two arrays. The extent of the lower dimensional component is the intersection of the two arrays.

Infix version of acond. If the predicate evaluates to True, the first component of the tuple is returned, else the second.

An array-level if-then-else construct.

An array-level while construct

Pipelining of two array computations.

Denotationally, we have

(acc1 >-> acc2) arrs = let tmp = acc1 arrs in acc2 tmp

Change the shape of an array without altering its contents. The size of the source and result arrays must be identical.

precondition: size ix == size ix'

Flattens a given array of arbitrary dimension.

Forward permutation specified by an index mapping. The result array is initialised with the given defaults and any further values that are permuted into the result array are added to the current value using the given combination function.

The combination function must be associative and commutative. Elements that are mapped to the magic value ignore by the permutation function are dropped.

Backward permutation specified by an index mapping from the destination array specifying which element of the source array to read.

Magic value identifying elements that are ignored in a forward permutation. Note that this currently does not work for singleton arrays.

Reverse the elements of a vector.

Transpose the rows and columns of a matrix.

Apply the given function element-wise to the given array.

Apply the given binary function element-wise to the two arrays. The extent of the resulting array is the intersection of the extents of the two source arrays.

Zip three arrays with the given function, analogous to zipWith.

Zip four arrays with the given function, analogous to zipWith.

Zip five arrays with the given function, analogous to zipWith.

Zip six arrays with the given function, analogous to zipWith.

Zip seven arrays with the given function, analogous to zipWith.

Zip eight arrays with the given function, analogous to zipWith.

Zip nine arrays with the given function, analogous to zipWith.

Combine the elements of two arrays pairwise. The shape of the result is the intersection of the two argument shapes.

Take three arrays and return an array of triples, analogous to zip.

Take four arrays and return an array of quadruples, analogous to zip.

Take five arrays and return an array of five-tuples, analogous to zip.

Take six arrays and return an array of six-tuples, analogous to zip.

Take seven arrays and return an array of seven-tuples, analogous to zip.

Take seven arrays and return an array of seven-tuples, analogous to zip.

Take seven arrays and return an array of seven-tuples, analogous to zip.

The converse of zip, but the shape of the two results is identical to the shape of the argument.

Take an array of triples and return three arrays, analogous to unzip.

Take an array of quadruples and return four arrays, analogous to unzip.

Take an array of 5-tuples and return five arrays, analogous to unzip.

Take an array of 6-tuples and return six arrays, analogous to unzip.

Take an array of 7-tuples and return seven arrays, analogous to unzip.

Take an array of 8-tuples and return eight arrays, analogous to unzip.

Take an array of 8-tuples and return eight arrays, analogous to unzip.

Drop elements that do not satisfy the predicate

Copy elements from source array to destination array according to an index mapping. This is a forward-permute operation where a to vector encodes an input to output index mapping. Output elements for indices that are not mapped assume the default vector's value.

For example:

default = [0, 0, 0, 0, 0, 0, 0, 0, 0]
to      = [1, 3, 7, 2, 5, 8]
input   = [1, 9, 6, 4, 4, 2, 5]

output  = [0, 1, 4, 9, 0, 4, 0, 6, 2]

Note if the same index appears in the index mapping more than once, the result is undefined. It does not makes sense for the to vector to be larger than the input vector.

Conditionally copy elements from source array to destination array according to an index mapping. This is a forward-permute operation where a to vector encodes an input to output index mapping. In addition, there is a mask vector, and an associated predicate function. The mapping will only occur if the predicate function applied to the mask at that position resolves to True. If not copied, the output array assumes the default vector's value.

For example:

default = [0, 0, 0, 0, 0, 0, 0, 0, 0]
to      = [1, 3, 7, 2, 5, 8]
mask    = [3, 4, 9, 2, 7, 5]
pred    = (>* 4)
input   = [1, 9, 6, 4, 4, 2, 5]

output  = [0, 0, 0, 0, 0, 4, 0, 6, 2]

Note if the same index appears in the mapping more than once, the result is undefined. The to and mask vectors must be the same length. It does not make sense for these to be larger than the input vector.

Copy elements from source array to destination array according to a map. This is a backpermute operation where a map vector encodes the output to input index mapping.

For example:

input  = [1, 9, 6, 4, 4, 2, 0, 1, 2]
from   = [1, 3, 7, 2, 5, 3]

output = [9, 4, 1, 6, 2, 4]

Conditionally copy elements from source array to destination array according to an index mapping. This is a backpermute operation where a from vector encodes the output to input index mapping. In addition, there is a mask vector, and an associated predication function, that specifies whether an element will be copied. If not copied, the output array assumes the default vector's value.

For example:

default = [6, 6, 6, 6, 6, 6]
from    = [1, 3, 7, 2, 5, 3]
mask    = [3, 4, 9, 2, 7, 5]
pred    = (>* 4)
input   = [1, 9, 6, 4, 4, 2, 0, 1, 2]

output  = [6, 6, 1, 6, 2, 4]

Reduction of the innermost dimension of an array of arbitrary rank. The first argument needs to be an associative function to enable an efficient parallel implementation.

Variant of fold that requires the reduced array to be non-empty and doesn't need an default value. The first argument needs to be an associative function to enable an efficient parallel implementation.

Reduction of an array of arbitrary rank to a single scalar value.

Variant of foldAll that requires the reduced array to be non-empty and doesn't need an default value.

Segmented reduction along the innermost dimension. Performs one individual reduction per segment of the source array. These reductions proceed in parallel.

The source array must have at least rank 1. The Segments array determines the lengths of the logical sub-arrays, each of which is folded separately.

Variant of foldSeg that requires all segments of the reduced array to be non-empty and doesn't need a default value.

The source array must have at least rank 1. The Segments array determines the lengths of the logical sub-arrays, each of which is folded separately.

Check if all elements satisfy a predicate

Check if any element satisfies the predicate

Check if all elements are True

Check if any element is True

Compute the sum of elements

Compute the product of the elements

Yield the minimum element of an array. The array must not be empty.

Yield the maximum element of an array. The array must not be empty.

Data.List style left-to-right scan, but with the additional restriction that the first argument needs to be an associative function to enable an efficient parallel implementation. The initial value (second argument) may be arbitrary.

Data.List style left-to-right scan without an initial value (aka inclusive scan). Again, the first argument needs to be an associative function. Denotationally, we have

scanl1 f e arr = tail (scanl f e arr)

Variant of scanl, where the final result of the reduction is returned separately. Denotationally, we have

scanl' f e arr = (init res, unit (res!len))
  where
    len = shape arr
    res = scanl f e arr

Right-to-left variant of scanl.

Right-to-left variant of scanl1.

Right-to-left variant of scanl'.

Left-to-right prescan (aka exclusive scan). As for scan, the first argument must be an associative function. Denotationally, we have

prescanl f e = Prelude.fst . scanl' f e

Left-to-right postscan, a variant of scanl1 with an initial value. Denotationally, we have

postscanl f e = map (e `f`) . scanl1 f

Right-to-left prescan (aka exclusive scan). As for scan, the first argument must be an associative function. Denotationally, we have

prescanr f e = Prelude.fst . scanr' f e

Right-to-left postscan, a variant of scanr1 with an initial value. Denotationally, we have

postscanr f e = map (e `f`) . scanr1 f

Segmented version of scanl

Segmented version of scanl1.

Segmented version of scanl'

The first element of the resulting tuple is a vector of scanned values. The second element is a vector of segment scan totals and has the same size as the segment vector.

Segmented version of prescanl.

Segmented version of postscanl.

Segmented version of scanr.

Segmented version of scanr1.

Segmented version of scanr'.

Segmented version of prescanr.

Segmented version of postscanr.

Map a stencil over an array. In contrast to map, the domain of a stencil function is an entire neighbourhood of each array element. Neighbourhoods are sub-arrays centred around a focal point. They are not necessarily rectangular, but they are symmetric in each dimension and have an extent of at least three in each dimensions — due to the symmetry requirement, the extent is necessarily odd. The focal point is the array position that is determined by the stencil.

For those array positions where the neighbourhood extends past the boundaries of the source array, a boundary condition determines the contents of the out-of-bounds neighbourhood positions.

Map a binary stencil of an array. The extent of the resulting array is the intersection of the extents of the two source arrays.

Boundary condition specification for stencil operations.

Call a foreign function. The form the function takes is dependent on the backend being used. The arguments are passed as either a single array or as a tuple of arrays. In addition a pure Accelerate version of the function needs to be provided to support backends other than the one being targeted.

Call a foreign function with foreign implementations for two different backends.

Call a foreign function with foreign implementations for three different backends.

Call a foreign expression function. The form the function takes is dependent on the backend being used. The arguments are passed as either a single scalar element or as a tuple of elements. In addition a pure Accelerate version of the function needs to be provided to support backends other than the one being targeted.

Call a foreign function with foreign implementations for two different backends.

Call a foreign function with foreign implementations for three different backends.

Scalar expressions for plain array computations.

All scalar type