Data.Array.Accelerate.AST

Scalar versus collective operations

The embedded array processing language is a two-level language. It combines a language of scalar expressions and functions with a language of collective array operations. Scalar expressions are used to compute arguments for collective operations and scalar functions are used to parametrise higher-order, collective array operations. The two-level structure, in particular, ensures that collective operations cannot be parametrised with collective operations; hence, we are following a flat data-parallel model. The collective operations manipulate multi-dimensional arrays whose shape is explicitly tracked in their types. In fact, collective operations cannot produce any values other than multi-dimensional arrays; when they yield a scalar, this is in the form of a 0-dimensional, singleton array. Similarly, scalar expression can -as their name indicates- only produce tuples of scalar, but not arrays.

There are, however, two expression forms that take arrays as arguments. As a result scalar and array expressions are recursively dependent. As we cannot and don't want to compute arrays in the middle of scalar computations, array computations will always be hoisted out of scalar expressions. So that this is always possible, these array expressions may not contain any free scalar variables. To express that condition in the type structure, we use separate environments for scalar and array variables.

Programs

Collective array programs comprise closed expressions of array operations. There is no explicit sharing in the initial AST form, but sharing is introduced subsequently by common subexpression elimination and floating of array computations.

Functions

The array expression language is first-order and only provides limited control structures to ensure that it can be efficiently executed on compute-acceleration hardware, such as GPUs. To restrict functions to first-order, we separate function abstraction from the main expression type. Functions are represented using de Bruijn indices.

Parametric and ad-hoc polymorphism

The array language features paramatric polymophism (e.g., pairing and projections) as well as ad-hoc polymorphism (e.g., arithmetic operations). All ad-hoc polymorphic constructs include reified dictionaries (c.f., module Types). Reified dictionaries also ensure that constants (constructor Const) are representable on compute acceleration hardware.

The AST contains both reified dictionaries and type class constraints. Type classes are used for array-related functionality that is uniformly available for all supported types. In contrast, reified dictionaries are used for functionality that is only available for certain types, such as arithmetic operations.

Typed de Bruijn indices

data Idx env t where

Constructors

ZeroIdx :: Idx (env, t) t

SuccIdx :: Idx env t -> Idx (env, s) t

Valuation environment

data Val env where

Constructors

Empty :: Val ()

Push :: Val env -> t -> Val (env, t)

Instances

Typeable1 Val

prj :: Idx env t -> Val env -> t

idxToInt :: Idx env t -> Int

Accelerated array expressions

class (Delayable arrs, Typeable arrs) => Arrays arrs where

Tuples of arrays (of type 'Array dim e'). This characterises the domain of results of Accelerate array computations.

Methods

arrays :: ArraysR arrs

Instances

Arrays ()

(Arrays arrs1, Arrays arrs2) => Arrays (arrs1, arrs2)

(Shape sh, Elt e) => Arrays (Array sh e)

data ArraysR arrs where

GADT reifying the Arrays class.

Constructors

ArraysRunit :: ArraysR ()

ArraysRarray :: (Shape sh, Elt e) => ArraysR (Array sh e)

ArraysRpair :: ArraysR arrs1 -> ArraysR arrs2 -> ArraysR (arrs1, arrs2)

data PreOpenAfun acc aenv t where

Function abstraction over parametrised array computations

Constructors

Abody :: acc aenv t -> PreOpenAfun acc aenv t

Alam :: (Arrays as, Arrays t) => PreOpenAfun acc (aenv, as) t -> PreOpenAfun acc aenv (as -> t)

type OpenAfun = PreOpenAfun OpenAcc

type PreAfun acc = PreOpenAfun acc ()

Parametrised array-computation function without free array variables

type Afun = OpenAfun ()

Vanilla array-computation function without free array variables

data PreOpenAcc acc aenv a where

Collective array computations parametrised over array variables represented with de Bruijn indices.

• Scalar functions and expressions embedded in well-formed array computations cannot contain free scalar variable indices. The latter cannot be bound in array computations, and hence, cannot appear in any well-formed program.
• The let-form is used to represent the sharing discovered by common subexpression elimination as well as to control evaluation order. (We need to hoist array expressions out of scalar expressions - they occur in scalar indexing and in determining an arrays shape.)

The data type is parameterised over the surface types (not the representation type).

We use a non-recursive variant parametrised over the recursive closure, to facilitate attribute calculation in the backend.

Constructors

Let :: (Arrays bndArrs, Arrays bodyArrs) => acc aenv bndArrs -> acc (aenv, bndArrs) bodyArrs -> PreOpenAcc acc aenv bodyArrs

Let2 :: (Arrays bndArrs1, Arrays bndArrs2, Arrays bodyArrs) => acc aenv (bndArrs1, bndArrs2) -> acc ((aenv, bndArrs1), bndArrs2) bodyArrs -> PreOpenAcc acc aenv bodyArrs

PairArrays :: (Shape sh1, Shape sh2, Elt e1, Elt e2) => acc aenv (Array sh1 e1) -> acc aenv (Array sh2 e2) -> PreOpenAcc acc aenv (Array sh1 e1, Array sh2 e2)

Avar :: Arrays arrs => Idx aenv arrs -> PreOpenAcc acc aenv arrs

Apply :: (Arrays arrs1, Arrays arrs2) => PreAfun acc (arrs1 -> arrs2) -> acc aenv arrs1 -> PreOpenAcc acc aenv arrs2

Acond :: Arrays arrs => PreExp acc aenv Bool -> acc aenv arrs -> acc aenv arrs -> PreOpenAcc acc aenv arrs

Use :: Array dim e -> PreOpenAcc acc aenv (Array dim e)

Unit :: Elt e => PreExp acc aenv e -> PreOpenAcc acc aenv (Scalar e)

Reshape :: (Shape sh, Shape sh', Elt e) => PreExp acc aenv sh -> acc aenv (Array sh' e) -> PreOpenAcc acc aenv (Array sh e)

Generate :: (Shape sh, Elt e) => PreExp acc aenv sh -> PreFun acc aenv (sh -> e) -> PreOpenAcc acc aenv (Array sh e)

Replicate :: (Shape sh, Shape sl, Elt slix, Elt e) => SliceIndex (EltRepr slix) (EltRepr sl) co' (EltRepr sh) -> PreExp acc aenv slix -> acc aenv (Array sl e) -> PreOpenAcc acc aenv (Array sh e)

Index :: (Shape sh, Shape sl, Elt slix, Elt e) => SliceIndex (EltRepr slix) (EltRepr sl) co' (EltRepr sh) -> acc aenv (Array sh e) -> PreExp acc aenv slix -> PreOpenAcc acc aenv (Array sl e)

Map :: (Shape sh, Elt e, Elt e') => PreFun acc aenv (e -> e') -> acc aenv (Array sh e) -> PreOpenAcc acc aenv (Array sh e')

ZipWith :: (Shape sh, Elt e1, Elt e2, Elt e3) => PreFun acc aenv (e1 -> e2 -> e3) -> acc aenv (Array sh e1) -> acc aenv (Array sh e2) -> PreOpenAcc acc aenv (Array sh e3)

Fold :: (Shape sh, Elt e) => PreFun acc aenv (e -> e -> e) -> PreExp acc aenv e -> acc aenv (Array (sh :. Int) e) -> PreOpenAcc acc aenv (Array sh e)

Fold1 :: (Shape sh, Elt e) => PreFun acc aenv (e -> e -> e) -> acc aenv (Array (sh :. Int) e) -> PreOpenAcc acc aenv (Array sh e)

FoldSeg :: (Shape sh, Elt e) => PreFun acc aenv (e -> e -> e) -> PreExp acc aenv e -> acc aenv (Array (sh :. Int) e) -> acc aenv Segments -> PreOpenAcc acc aenv (Array (sh :. Int) e)

Fold1Seg :: (Shape sh, Elt e) => PreFun acc aenv (e -> e -> e) -> acc aenv (Array (sh :. Int) e) -> acc aenv Segments -> PreOpenAcc acc aenv (Array (sh :. Int) e)

Scanl :: Elt e => PreFun acc aenv (e -> e -> e) -> PreExp acc aenv e -> acc aenv (Vector e) -> PreOpenAcc acc aenv (Vector e)

Scanl' :: Elt e => PreFun acc aenv (e -> e -> e) -> PreExp acc aenv e -> acc aenv (Vector e) -> PreOpenAcc acc aenv (Vector e, Scalar e)

Scanl1 :: Elt e => PreFun acc aenv (e -> e -> e) -> acc aenv (Vector e) -> PreOpenAcc acc aenv (Vector e)

Scanr :: Elt e => PreFun acc aenv (e -> e -> e) -> PreExp acc aenv e -> acc aenv (Vector e) -> PreOpenAcc acc aenv (Vector e)

Scanr' :: Elt e => PreFun acc aenv (e -> e -> e) -> PreExp acc aenv e -> acc aenv (Vector e) -> PreOpenAcc acc aenv (Vector e, Scalar e)

Scanr1 :: Elt e => PreFun acc aenv (e -> e -> e) -> acc aenv (Vector e) -> PreOpenAcc acc aenv (Vector e)

Permute :: (Shape sh, Elt e) => PreFun acc aenv (e -> e -> e) -> acc aenv (Array sh' e) -> PreFun acc aenv (sh -> sh') -> acc aenv (Array sh e) -> PreOpenAcc acc aenv (Array sh' e)

Backpermute :: (Shape sh, Shape sh', Elt e) => PreExp acc aenv sh' -> PreFun acc aenv (sh' -> sh) -> acc aenv (Array sh e) -> PreOpenAcc acc aenv (Array sh' e)

Stencil :: (Elt e, Elt e', Stencil sh e stencil) => PreFun acc aenv (stencil -> e') -> Boundary (EltRepr e) -> acc aenv (Array sh e) -> PreOpenAcc acc aenv (Array sh e')

Stencil2 :: (Elt e1, Elt e2, Elt e', Stencil sh e1 stencil1, Stencil sh e2 stencil2) => PreFun acc aenv (stencil1 -> stencil2 -> e') -> Boundary (EltRepr e1) -> acc aenv (Array sh e1) -> Boundary (EltRepr e2) -> acc aenv (Array sh e2) -> PreOpenAcc acc aenv (Array sh e')

newtype OpenAcc aenv t

Constructors

OpenAcc (PreOpenAcc OpenAcc aenv t)

Instances

Typeable2 OpenAcc

Show (OpenAcc aenv a)

Show instances ---------------

Show (OpenExp env aenv t)

Show (OpenFun env aenv f)

type Acc = OpenAcc ()

Closed array expression aka an array program

class (Shape sh, Elt e, IsTuple stencil) => Stencil sh e stencil where

Operations on stencils.

Methods

stencil :: StencilR sh e stencil

stencilAccess :: (sh -> e) -> sh -> stencil

Instances

Elt e => Stencil DIM1 e (e, e, e)

Elt e => Stencil DIM1 e (e, e, e, e, e)

Elt e => Stencil DIM1 e (e, e, e, e, e, e, e)

Elt e => Stencil DIM1 e (e, e, e, e, e, e, e, e, e)

(Stencil (:. sh Int) a row1, Stencil (:. sh Int) a row2, Stencil (:. sh Int) a row3) => Stencil (:. (:. sh Int) Int) a (row1, row2, row3)

(Stencil (:. sh Int) a row1, Stencil (:. sh Int) a row2, Stencil (:. sh Int) a row3, Stencil (:. sh Int) a row4, Stencil (:. sh Int) a row5) => Stencil (:. (:. sh Int) Int) a (row1, row2, row3, row4, row5)

(Stencil (:. sh Int) a row1, Stencil (:. sh Int) a row2, Stencil (:. sh Int) a row3, Stencil (:. sh Int) a row4, Stencil (:. sh Int) a row5, Stencil (:. sh Int) a row6, Stencil (:. sh Int) a row7) => Stencil (:. (:. sh Int) Int) a (row1, row2, row3, row4, row5, row6, row7)

(Stencil (:. sh Int) a row1, Stencil (:. sh Int) a row2, Stencil (:. sh Int) a row3, Stencil (:. sh Int) a row4, Stencil (:. sh Int) a row5, Stencil (:. sh Int) a row6, Stencil (:. sh Int) a row7, Stencil (:. sh Int) a row8, Stencil (:. sh Int) a row9) => Stencil (:. (:. sh Int) Int) a (row1, row2, row3, row4, row5, row6, row7, row8, row9)

data StencilR sh e pat where

GADT reifying the Stencil class.

Constructors

StencilRunit3 :: Elt e => StencilR DIM1 e (e, e, e)

StencilRunit5 :: Elt e => StencilR DIM1 e (e, e, e, e, e)

StencilRunit7 :: Elt e => StencilR DIM1 e (e, e, e, e, e, e, e)

StencilRunit9 :: Elt e => StencilR DIM1 e (e, e, e, e, e, e, e, e, e)

StencilRtup3 :: (Shape sh, Elt e) => StencilR sh e pat1 -> StencilR sh e pat2 -> StencilR sh e pat3 -> StencilR (sh :. Int) e (pat1, pat2, pat3)

StencilRtup5 :: (Shape sh, Elt e) => StencilR sh e pat1 -> StencilR sh e pat2 -> StencilR sh e pat3 -> StencilR sh e pat4 -> StencilR sh e pat5 -> StencilR (sh :. Int) e (pat1, pat2, pat3, pat4, pat5)

StencilRtup7 :: (Shape sh, Elt e) => StencilR sh e pat1 -> StencilR sh e pat2 -> StencilR sh e pat3 -> StencilR sh e pat4 -> StencilR sh e pat5 -> StencilR sh e pat6 -> StencilR sh e pat7 -> StencilR (sh :. Int) e (pat1, pat2, pat3, pat4, pat5, pat6, pat7)

StencilRtup9 :: (Shape sh, Elt e) => StencilR sh e pat1 -> StencilR sh e pat2 -> StencilR sh e pat3 -> StencilR sh e pat4 -> StencilR sh e pat5 -> StencilR sh e pat6 -> StencilR sh e pat7 -> StencilR sh e pat8 -> StencilR sh e pat9 -> StencilR (sh :. Int) e (pat1, pat2, pat3, pat4, pat5, pat6, pat7, pat8, pat9)

Scalar expressions

data PreOpenFun acc env aenv t where

Parametrised open function abstraction

Constructors

Body :: PreOpenExp acc env aenv t -> PreOpenFun acc env aenv t

Lam :: Elt a => PreOpenFun acc (env, EltRepr a) aenv t -> PreOpenFun acc env aenv (a -> t)

Instances

Show (OpenFun env aenv f)

type OpenFun = PreOpenFun OpenAcc

Vanilla open function abstraction

type PreFun acc = PreOpenFun acc ()

Parametrised function without free scalar variables

type Fun = OpenFun ()

Vanilla function without free scalar variables

data PreOpenExp acc env aenv t where

Parametrised open expressions using de Bruijn indices for variables ranging over tuples of scalars and arrays of tuples. All code, except Cond, is evaluated eagerly. N-tuples are represented as nested pairs.

The data type is parametrised over the surface types (not the representation type).

Constructors

Var :: Elt t => Idx env (EltRepr t) -> PreOpenExp acc env aenv t

Const :: Elt t => EltRepr t -> PreOpenExp acc env aenv t

Tuple :: (Elt t, IsTuple t) => Tuple (PreOpenExp acc env aenv) (TupleRepr t) -> PreOpenExp acc env aenv t

Prj :: (Elt t, IsTuple t) => TupleIdx (TupleRepr t) e -> PreOpenExp acc env aenv t -> PreOpenExp acc env aenv e

IndexNil :: PreOpenExp acc env aenv Z

IndexCons :: (Slice sl, Elt a) => PreOpenExp acc env aenv sl -> PreOpenExp acc env aenv a -> PreOpenExp acc env aenv (sl :. a)

IndexHead :: (Slice sl, Elt a) => PreOpenExp acc env aenv (sl :. a) -> PreOpenExp acc env aenv a

IndexTail :: (Slice sl, Elt a) => PreOpenExp acc env aenv (sl :. a) -> PreOpenExp acc env aenv sl

IndexAny :: Shape sh => PreOpenExp acc env aenv (Any sh)

Cond :: PreOpenExp acc env aenv Bool -> PreOpenExp acc env aenv t -> PreOpenExp acc env aenv t -> PreOpenExp acc env aenv t

PrimConst :: Elt t => PrimConst t -> PreOpenExp acc env aenv t

PrimApp :: (Elt a, Elt r) => PrimFun (a -> r) -> PreOpenExp acc env aenv a -> PreOpenExp acc env aenv r

IndexScalar :: (Shape dim, Elt t) => acc aenv (Array dim t) -> PreOpenExp acc env aenv dim -> PreOpenExp acc env aenv t

Shape :: (Shape dim, Elt e) => acc aenv (Array dim e) -> PreOpenExp acc env aenv dim

Size :: (Shape dim, Elt e) => acc aenv (Array dim e) -> PreOpenExp acc env aenv Int

Instances

Show (OpenExp env aenv t)

type OpenExp = PreOpenExp OpenAcc

Vanilla open expression

type PreExp acc = PreOpenExp acc ()

Parametrised expression without free scalar variables

type Exp = OpenExp ()

Vanilla expression without free scalar variables

data PrimConst ty where

Primitive GPU constants

Constructors

PrimMinBound :: BoundedType a -> PrimConst a

PrimMaxBound :: BoundedType a -> PrimConst a

PrimPi :: FloatingType a -> PrimConst a

data PrimFun sig where

Primitive scalar operations

Constructors

PrimAdd :: NumType a -> PrimFun ((a, a) -> a)

PrimSub :: NumType a -> PrimFun ((a, a) -> a)

PrimMul :: NumType a -> PrimFun ((a, a) -> a)

PrimNeg :: NumType a -> PrimFun (a -> a)

PrimAbs :: NumType a -> PrimFun (a -> a)

PrimSig :: NumType a -> PrimFun (a -> a)

PrimQuot :: IntegralType a -> PrimFun ((a, a) -> a)

PrimRem :: IntegralType a -> PrimFun ((a, a) -> a)

PrimIDiv :: IntegralType a -> PrimFun ((a, a) -> a)

PrimMod :: IntegralType a -> PrimFun ((a, a) -> a)

PrimBAnd :: IntegralType a -> PrimFun ((a, a) -> a)

PrimBOr :: IntegralType a -> PrimFun ((a, a) -> a)

PrimBXor :: IntegralType a -> PrimFun ((a, a) -> a)

PrimBNot :: IntegralType a -> PrimFun (a -> a)

PrimBShiftL :: IntegralType a -> PrimFun ((a, Int) -> a)

PrimBShiftR :: IntegralType a -> PrimFun ((a, Int) -> a)

PrimBRotateL :: IntegralType a -> PrimFun ((a, Int) -> a)

PrimBRotateR :: IntegralType a -> PrimFun ((a, Int) -> a)

PrimFDiv :: FloatingType a -> PrimFun ((a, a) -> a)

PrimRecip :: FloatingType a -> PrimFun (a -> a)

PrimSin :: FloatingType a -> PrimFun (a -> a)

PrimCos :: FloatingType a -> PrimFun (a -> a)

PrimTan :: FloatingType a -> PrimFun (a -> a)

PrimAsin :: FloatingType a -> PrimFun (a -> a)

PrimAcos :: FloatingType a -> PrimFun (a -> a)

PrimAtan :: FloatingType a -> PrimFun (a -> a)

PrimAsinh :: FloatingType a -> PrimFun (a -> a)

PrimAcosh :: FloatingType a -> PrimFun (a -> a)

PrimAtanh :: FloatingType a -> PrimFun (a -> a)

PrimExpFloating :: FloatingType a -> PrimFun (a -> a)

PrimSqrt :: FloatingType a -> PrimFun (a -> a)

PrimLog :: FloatingType a -> PrimFun (a -> a)

PrimFPow :: FloatingType a -> PrimFun ((a, a) -> a)

PrimLogBase :: FloatingType a -> PrimFun ((a, a) -> a)

PrimAtan2 :: FloatingType a -> PrimFun ((a, a) -> a)

PrimTruncate :: FloatingType a -> IntegralType b -> PrimFun (a -> b)

PrimRound :: FloatingType a -> IntegralType b -> PrimFun (a -> b)

PrimFloor :: FloatingType a -> IntegralType b -> PrimFun (a -> b)

PrimCeiling :: FloatingType a -> IntegralType b -> PrimFun (a -> b)

PrimLt :: ScalarType a -> PrimFun ((a, a) -> Bool)

PrimGt :: ScalarType a -> PrimFun ((a, a) -> Bool)

PrimLtEq :: ScalarType a -> PrimFun ((a, a) -> Bool)

PrimGtEq :: ScalarType a -> PrimFun ((a, a) -> Bool)

PrimEq :: ScalarType a -> PrimFun ((a, a) -> Bool)

PrimNEq :: ScalarType a -> PrimFun ((a, a) -> Bool)

PrimMax :: ScalarType a -> PrimFun ((a, a) -> a)

PrimMin :: ScalarType a -> PrimFun ((a, a) -> a)

PrimLAnd :: PrimFun ((Bool, Bool) -> Bool)

PrimLOr :: PrimFun ((Bool, Bool) -> Bool)

PrimLNot :: PrimFun (Bool -> Bool)

PrimOrd :: PrimFun (Char -> Int)

PrimChr :: PrimFun (Int -> Char)

PrimBoolToInt :: PrimFun (Bool -> Int)

PrimFromIntegral :: IntegralType a -> NumType b -> PrimFun (a -> b)