{-# LANGUAGE TypeFamilies, MultiParamTypeClasses #-} module Control.Parallel.ScanVectorMachine.ScanVectorMachine where -- | Scalar operations which may be performed on the elements of a -- vector, either elementwise or in prefix-scan form. data Op = And | Or | Min | Max | Plus | Times -- -- | 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. -- class ScanVectorMachine v s where -- | Scalar negation all of the elements of the vector. neg :: v s -> v s -- | Elementwise less-than-or-equal-to comparison. Both vectors must be the same length. leq :: v s -> v s -> v s -- | Elementwise operations (see @Op@). Both vectors must be the same length. op :: Op -> v s -> v s -> v s -- | Prefix scan operations (see @Op@). scan :: Op -> 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. select :: v s -> 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. permute :: v s -> v 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. insert :: v s -> s -> s -> v 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. extract :: v s -> s -> 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. distribute :: s -> s -> v 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. length :: v s -> s