Nikola Architecture

Here we attempt to document the architecture of Nikola, yielding both an overview and an understanding of the details.

Protip: use graphmod from hackage to generate a graphwiz file of Nikola source, and a tool such as zgrviewer to inspect it (both are in the dybberplc dropbox folder)

The module name qualifications used here are summarised in Common Qualifiers.

Overview

User programming

Use import Data.Array.Nikola.Backend.CUDA to get a version of Exp specialised for CUDA. Then, import Data.Array.Nikola.Backend.CUDA.Haskell as H or import Data.Array.Nikola.Backend.CUDA.TH as TH for code generation, either at runtime (H.compile) or at compile time (TH.compile). Note that the same-module restrictions of Template Haskell apply when using TH, requiring the Nikola Exp values to be defined in a separate module from the one issuing TH.compile.

Code generation

Nikola AST is three-tiered (see below for name qualification): S.Exp, E.Exp t a and C.Exp a (= E.Exp CUDA a).

S.Exp is an untyped, first order AST, containing low-level instructions such as allocation instructions.

E.Exp t a is a newtype wrapper on top of S.Exp. All client Nikola code is E.Exp values. Nikola is a deep embedding, thus function E.Exp t a -> E.Exp t b are also considered Nikola terms).

At compilation, Nikola relies on the typeclass R.Reifiable to reify E.Exps (and functions thereof) to their corresponding first-order S.Exp representation.

Module details

Language definitions; Abstract Syntax

Module Data.Array.Nikola.Language.Syntax as S

This module defines the first-order AST, S.Exp. Consider it a Nikola internal module.

Module Data.Array.Nikola.Exp as E

This module defines a thin newtype wrapper E.Exp t a around S.Exp. t,a are phantom types with t refering to target (eg. CUDA) and a refering to the expected type resulting from evaluating the E.Exp.

We suspect that this is to permit the writing of both backend agnostic nikola programs and backend sensitive nikola programs.

Module Data.Array.Nikola.Language.Monad as LM

This module defines the LM.R monad (though mostly imported unqualified in Nikola as just R). The name R is probably meant to suggest Reification, based on that R.reify :: a -> R b b

LM.R implements MonadState, MonadCont and MonadIO, and is defined by:

newtype R r a = R { unR :: REnv -> (REnv -> a -> IO (REnv, r)) -> IO (REnv, r) }

(Where the REnv contains a typing environment for variables, an expression cache and a 'sharing cache)

Peculiar to the continuation aspect of LM.R are the functions:

• reset :: R a a -> R r a
• shift :: ((a -> R r r) -> R r r) -> R r a

These work in tandem as reset α (shift $ \k -> β), and are best regarded as control structures that substitute applications of k in β with the surrounding environment up to the nearest dynamically enclosing reset.

Andrzej explains that this may be used in code generation to for instance transform

(n + (if .. then .. else ..)) ==> if .. then n + .. else n + ..

by means of expressing the above as

(reset $ n + (shift \k -> if .. then k .. else k ...))

which lends itself better to constant folding. (Note however that in Haskell, shift/reset are monadic!.)

Module Data.Array.Nikola.Language.Reify as R

Compiler backend

C part

The C part (modules inside Data.Array.Nikola.Backend.C) are called by the CUDA backend and not used directly by client programs.

• Data.Array.Nikola.Backend.C.Codegen

  Actual C code generation happens here through compileProgram. CUDA is treated as a variant of C, as determined by a Dialect enum type. Still, only host code is compiled, but with the (dialect extension?) ability to call cuda kernels.

  Code generation happens inside the C monad, described below:

• Data.Array.Nikola.Backend.C.Monad

  ...

Cuda part

• Data.Array.Nikola.Backend.CUDA as C

  This module exports C.Exp a = E.Exp CUDA a.

Haskell sub-part

• Data.Array.Nikola.Backend.CUDA.Haskell

  Compilable typeclass and datatype data PreEx a

• Data.Array.Nikola.Backend.CUDA.Haskell.Ex

Device<->Host data exchange