- data Op
- class ScanVectorMachine v s where
Scalar operations which may be performed on the elements of a vector, either elementwise or in prefix-scan form.
An instance of
ScanVectorMachine provides a scalar type
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
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
import qualified ScanVectorMachine as SVM so that these
may be referred to as, for example,
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
Also notice that only three operations involve communication
between different parts of the paralell context:
distribute operation performs
broadcast communication from the serial context to the parallel
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.
Elementwise less-than-or-equal-to comparison. Both vectors must be the same length.
Elementwise operations (see
Op). Both vectors must be the same length.
Prefix scan operations (see
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 v1 v2 returns a vector
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.
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.
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.
Creates a new vector;
distribute s n creates a vector of length
n whose elements are all
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|