The data-flow graph of OM takes three type parameters
vector
,
gauge
and
anot
, so does the Builder Monads.
vector
represents the dimension of the array (say, three-dimension,)
gauge
the type of the index of the array (say, Int,) and
anot
the annotations given to the graph for analysis and optimization purposes. The combination
vector gauge
represents an index vector (in this case, three-dimensional vector of Int) for accessing the arrays.
type Graph vector gauge anot = Gr (Node vector gauge anot) Edge
Paraiso programs are described by combining
Builder Monad
s, which are actually
State
monads each carrying a half-built data-flow graph. Builder Monads take a few vertices from the data-flow graph, and return (usually one) new vertex. The vertices are of type
Value
, which carry their
Realm
information --- whether they are
Array
or
Scalar
--- and their content type information.
-- | value type, with its realm and content type discriminated in
-- type level data
Value rea con =
-- | data obtained from the data-flow graph.
-- 'realm' carries a type-level realm information,
-- 'content' carries only type information and its ingredient is
-- insignificant and can be 'undefined'.
FromNode {realm :: rea, content :: con, node :: G.Node} |
-- | data obtained as an immediate value.
-- 'realm' carries a type-level realm information,
-- 'content' is the immediate value to be stored.
FromImm {realm :: rea, content :: con} deriving (Eq, Show)
The monadic building blocks we use in Paraiso are defined in
Language.Paraiso.OM.Builder module. Please go to the page, and tap the "Synopsis" tab.
bind trick
We have already seen several Paraiso programs, and you may have noticed the too frequent use of the term
bind
,
bind :: (Monad m, Functor m) => m a -> m (m a)
bind = fmap return
Like this:
x <- bind $ loadIndex (Axis 0)
y <- bind $ loadIndex (Axis 1)
z <- bind $ x*y
w <- bind $ x+y
The above program originally looked like this:
x <- loadIndex (Axis 0)
y <- loadIndex (Axis 1)
z <- return x * return y
w <- return x + return y
The right hand side expressions are built of
Builder
monads while the bound names at the left hand side like
x,y,z,w
are of type
Value
. So we need to convert pure values to monads using
return
s. This cannot be helped, because we cannot have
x
,
y
and
z
of the same type in such expressions like
z <- x*y
. However, there's a solution. By using
bind = fmap return
, we apply
return
only once at the binding timing, instead of everywhere else later on.
OM instructions
The instruction set of the Orthotope Machine is defined as algebraic data type
Inst
in
Language.Paraiso.OM.Graph
module, and
Language.Paraiso.OM.Builder
provides the (almost) corresponding Builder Monad combinators. Here is the table of them. Read
B
as the general monad symbol
m
. (The actual definition is
type B ret = forall v g a. Builder v g a ret
.)
Here is the instruction set:
data Inst vector gauge
= Load StaticIdx
| Store StaticIdx
| Reduce R.Operator
| Broadcast
| LoadIndex (Axis vector)
| LoadSize (Axis vector)
| Shift (vector gauge)
| Imm Dynamic
| Arith A.Operator
and the corresponding monad combinators:
-- options input nodes output nodes
load :: Named (StaticValue r c) -> B (Value r c)
store :: Named (StaticValue r c) -> B (Value r c) -> B ()
reduce :: Reduce.Operator -> B (Value TArray c) -> B (Value TScalar c)
broadcast :: B (Value TScalar c) -> B (Value TArray c)
loadIndex :: Axis v -> B (Value TArray g)
loadSize :: Axis v -> B (Value TScalar g)
shift :: v g -> B (Value TArray c) -> B (Value TArray c)
imm :: c -> B (Value r c)
In short,
Load
takes a static variable, and loads from it, starting the data-flow graph.
Store
ends the data-flow graph by storing the result to the specified static variable.
Reduce
turns an array into a scalar value by use of the specified reduction operator.
Broadcast
does the opposite and turns a scalar value into an array of the same type.
LoadIndex
is used to retrieve the array index in the specified direction. The result is always an array.
LoadSize
is used to retrieve the array size in the specified direction. The result is a scalar, of course.
Shift
is used to move an array by a certain vector v g
.
Imm
is to introduce an immediate value.
Arith
is for arithmetic operations.
We will gradually see the detail via examples.
Arithmetic
Where are the combinators for the
Arith
instructions? Well, thanks to algebraic type classes defiend in
numeric-prelude, we can write Builder expression using the usual arithmetic operators, in the same manner as writing ordinary expressions.
(+) :: B (Value r c) -> B (Value r c) -> B (Value r c)
sin :: B (Value r c) -> B (Value r c)
One important exception to this are Boolean operators. Since Haskell's Boolean operators are of type, say,
(==) :: Eq a => a -> a -> Bool
, we cannot construct a Builder of Bool out of them. Instead, use functions defined in modules
Language.Paraiso.OM.Builder.Boolean and
Language.Paraiso.Prelude. Also
if
cannot be re-used, so
select
instead.
eq :: B (Value r c) -> B (Value r c) -> B (Value r Bool)
ne :: B (Value r c) -> B (Value r c) -> B (Value r Bool)
select :: B (Value r Bool) -> B (Value r c) -> B (Value r c) -> B (Value r c)
And here's a
cast
operator for type conversion. Here,
c2
provides only the type information but its value is never used.
cast :: c2 -> B (Value r c1) -> B (Value r c2)