Safe Haskell | Safe-Infered |
---|

- data Op
- class ScanVectorMachine v s where

# Documentation

Scalar operations which may be performed on the elements of a vector, either elementwise or in prefix-scan form.

class ScanVectorMachine v s whereSource

An instance of `ScanVectorMachine`

provides a scalar type `s`

,
vectors of type `v s`

over that scalar of type, and the full
suite of Scan Vector Machine (SVM) operations (Blelloch'90,
page 60) on those vectors. The SVM instruction set is sometimes
referred to as *VCODE* (CMU tech report CMU-CS-90-146-R).

Only two changes have been made: (1) booleans are encoded as
scalars (zero is false, nonzero is true) and (2) Belloch's
elementwise subtraction has been replaced with a unary `neg`

operation; this way the set of elementwise and scan operations are
the same (subtraction is not associative).

Many of the names below overlap with those in the Prelude; we
recommend `import qualified ScanVectorMachine as SVM`

so that these
may be referred to as, for example, `SVM.length`

.

Notice that there is no `map :: (s -> s) -> v s -> v s`

; this is
essential to keeping *closures* and *uncontained recursion* out of the
parallel context. See Blelloch 10.6.2 for the definition of
contained recursion.

Also notice that only three operations involve communication
between different parts of the paralell context: `distribute`

,
`scan`

, and `permute`

. The `distribute`

operation performs
broadcast communication from the serial context to the parallel
context. The `scan`

operation performs prefix scans, which have
very efficient communication patterns (do a local scan, then a
global tree reduction, then a local distribution, then an
elementwise operation). Only the `permute`

operation involves
complicated communication patterns. This is mitigated to some
extent by the requirement that `permute`

must be a *permutation* of
the vector; it is an error to send two elements to the same
destination index, or to have a destination index to which no
element is sent.

Scalar negation all of the elements of the vector.

leq :: v s -> v s -> v sSource

Elementwise less-than-or-equal-to comparison. Both vectors must be the same length.

op :: Op -> v s -> v s -> v sSource

Elementwise operations (see `Op`

). Both vectors must be the same length.

scan :: Op -> v s -> v sSource

Prefix scan operations (see `Op`

).

select :: v s -> v s -> v s -> v sSource

If-then-else; `select b x y`

returns a vector whose `i`

^th element is `if b[i] then x[i] else y[i]`

.
All three vectors must be the same length.

permute :: v s -> v s -> v sSource

Permutation: `permute v1 v2`

returns a vector `v3`

where `v3[v2[i]] = v1[i]`

for all `i`

. Both vectors
must be the same length and the elements of `v2`

must all be distinct, non-negative, and
less than the lengths of the vectors.

insert :: v s -> s -> s -> v sSource

Replaces an element of a vector; `insert v s i e`

sets `i`

^th element of the vector to `s`

. The scalar `i`

must be
nonnegative and less than the length of the vector. This instruction implements unicast communication from the
serial context to the parallel context.

extract :: v s -> s -> sSource

Extracts an element of a vector; `extract v i`

yields `v[i]`

. The scalar `i`

must be nonnegative and less than
the length of the vector. This instruction implements communication from the parallel context to the serial context.

distribute :: s -> s -> v sSource

Creates a new vector; `distribute s n`

creates a vector of length `n`

whose elements are all `s`

.
This instruction implements communication from the parallel context to the serial context.

Returns the length of a parallel vector. These can be cached in the serial context since the length of a vector
never depends on data from the paralell context; as a result `length`

does not actually involve communication.

(Enum e, Ix e, Ord e, Num e) => ScanVectorMachine SSVM e | |

ScanVectorMachine v s => ScanVectorMachine SegVec (v s) | Default implementation of segments using an auxiliary segment-length vector |

(ScanVectorMachine v s, ScanVectorMachine v' (v s)) => ScanVectorMachine VecPair (v' (v s)) | |

IsScalar s => ScanVectorMachine (Array DIM1) s |