Control.Parallel.ScanVectorMachine.ScanVectorMachine

Documentation

data Op

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

Constructors

And

Or

Min

Max

Plus

Times

class ScanVectorMachine v s where

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.

Methods

neg :: v s -> v s

Scalar negation all of the elements of the vector.

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

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

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

Elementwise operations (see Op). Both vectors must be the same length.

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

Prefix scan operations (see Op).

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

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 s

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 s

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 -> s

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 s

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.

length :: v s -> s

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.

Instances

(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