vectorising

Characteristics

Accelerate

• Accelerate is split into a frontend, consisting of the Acc and Exp types, and various backends that may execute Acc terms.

• Acc terms are 'Array-valued collective computations'.

• Exp terms are 'Scalar expressions for plain array computations'.

• By construction, no Exp term may use an Acc term, motivated by the desire of a clear cut between parallel operations and sequential operations.

• Thus, all Accelerate programs may be thought of as an outer parallel execution of identical sequential procedures, i.e. flat data parallelism.

• Arrays are Repa-style; Regular with shapes.

• Segmented arrays are only supported via explicit, external segment descriptors in some functions of the language.

• The Acc/Exp division gives rise to dublication of functionality, e.g. an if construct for both Exp and Acc.

Nikola

• Typically, you just import "Data.Array.Nikola.Backend.CUDA" unqualified.

• Data.Array.Nikola.Language.Syntax defines the basic abstract expression syntax,

(For Data.Array.Nikola.Exp:)

• Data.Array.Nikola.Exp wraps the expression syntax, such that it is compatible with -XRebindableSyntax. It is tagged with a phantom type variable representing the dialect. Thus, Exp CUDA a is only nominally different from Exp t a. Maybe the distinction is motivated by the desire to have different primitive constructs available for different backends.

• In various places of Nikola we find obnoxious instances like this:

  instance Eq a => Eq (Exp t a) where _ == _ = error " (==) Exp: incomparable" _ /= _ = error " (/=) Exp: incomparable"

  So far these have only caused trouble, and seem rather unmotivated.

• There is a Lift/Unlift typeclass pair with an assoc type Lifted t a :: * They seem to serve the purpose of lifting constants into Exp, and unlifting nested expression types (that presumably occurs some places inherently) i.e. Exp t (Exp t a) -> Exp t a, but through the associated type.

• There is an IsElem typeclass, detailing what types may occur as scalars in arrays, and their on-device representation type

(For Data.Array.Nikola.Language.Syntax:)

• Data.Array.Nikola.Language.Syntax contains the unwrapped, untyped AST type Exp.

• It also contains data types on variable occurence in LetE-expressions, presumably to guide the inliner.

(Compiling to cuda code:)

• In Data.Array.Nikola.Backend.CUDA.Haskell we find the compile function, that can make as into bs, provided instances of (Compilable a b, Reifiable a Exp).

• The given instances of Compilable are able to compile Exp CUDA a to the corresponding Rep a (Associated type from IsElem typeclass). There is also some machinery to compile various array types.

• The compilation has roughly three major phases: Reification -> C expression rendering -> Nvcc compilation.

(Misc:)

• map in Nikola is implemented via the type class Map in Data.Array.Nikola.Operators.Mapping, and the default implementation is through Source and Target array classes.

Vectorising

Accelerate

Vectorising Accelerate would involve either tearing down the Acc/Exp wall, a very central part of the very structure of the language, or providing an embedAcc :: Acc a -> Exp a, making collective operations fit in where only scalar operations were previously permitted.

Either way, the language would have be extended to permit nested arrays, either in addition to or instead of shaped arrays, or possibly a hybrid (as shape is just an indexing-abstraction over a flat array).

Breaking down the Acc/Exp wall would quite possibly be much like rewriting the entire language.

Providing an embedAcc operation would render the distinction between Exp and Acc apparently redundant, although the distinction might be used to provide execution hints, i.e. that (unembedded) Exps be preferred to be executed in sequence. However, depending on how deeply the Acc/Exp distinction is reflected in assumptions in code generation, providing embedAcc might require a substantial rewrite of code generation.