Changes between Version 15 and Version 16 of DataParallel/Regular

Timestamp:

01/11/10 20:37:58 (3 years ago)

Author:

gckeller

Comment:

--

DataParallel/Regular

@@ -159 +159 @@
 }}}
 
+=== Shape Polymorphic Computations on Arrays ===
+
+
+The library provides a range of operation where the dimensionality of
+the result depends on the dimensionality of the argument in a
+non-trivial manner, which we want to be reflected in the type system. 
+Examples of such functions are generalised selection, which allows for 
+extraction of subarrays of arbitrary dimension, and generalised replicate,
+which allows replication of an array in any dimension (or dimensions). For example,
+given a three dimensional matrix, we can use select to extract scalar element values,
+rows, columns, as well as two dimensional matrices along any of the three axes.
+
+For selection, we can informally state the relationship between dimensionality of
+the argument, the selector, and the result as follows:
+{{{
+select:: Array dim e -> <select dim' of dim array> -> Array dim' e
+}}}
+
+Another example for such a generalised function would be a generalised
+`map`, which can apply a function to all elements, all rows, all
+columns, or submatrices of different orientation of a multidimensional
+array.
+
+For the former example, we need a way to express the relationship between the
+shape of the argument and the shape and orientation of the result, as well as
+the numerical position of the structure (i.e., first, second, third element). 
+In case of the generalised `map`, we don't need the numerical information, since
+the operation will be applied to all elements, rows, columns etc. 
+
+To express this dependency between input and output shape and orientation,
+as well as possibly a concrete position,  the library provides the `Index` GADT, 
+which expresses a relationship between the source and the projected dimension. 
+It is defined as follows:
+{{{
+data Index a initialDim projectedDim where
+  IndexNil   :: Index a initialDim initialDim
+  IndexAll   :: (Shape init, Shape proj) =>      
+                   Index a init proj -> Index a (init :*: Int) (proj :*: Int)
+  IndexFixed :: (Shape init, Shape proj) => a -> 
+                   Index a init proj -> Index a (init :*: Int)  proj
+}}}
+To refer to a specific element, the type parameter `a` is instantiated with the type `Int`, otherwise
+with the unit type:
+{{{
+type SelectIndex = Index Int
+type MapIndex    = Index ()
+}}}
+Given this definition, the type of `select` now becomes
+{{{
+select:: (U.Elt e, Shape dim, Shape dim') => Array dim e -> SelectIndex dim dim'  -> Array dim' e
+}}}
+Example:
+{{{
+arr:: Array (() :*: Int :*: Int :*: Int) Double
+
+arr' :: () :*: Int :*: Int
+arr' = select arr (IndexFixed 3 (IndexAll (IndexAll IndexNil))) 
+}}}
+We could generalise this further, to extract from any array `arr` which is at least one dimensional 
+the third element:
+{{{
+arr:: Shape dim => Array (dim :*: Int) Double
+
+arr' :: Array dim Double
+arr' = select arr (IndexFixed 3 IndexNil)
+}}}
+
+
+The index type is also used to express the type of generalised replicate
+{{{
+replicate:: Array dim' e -> SelectIndex dim dim'  -> Array dim e
+}}}
+which, given an array, can be used to expand it along any dimension. For example,
+{{{
+simpleReplicate:: (U.Elt e, Shape dim) => Array dim e -> Int -> Array (dim :*: Int) e
+simpleReplicate arr n =
+  replicate arr (IndexFixed n IndexNil)
+}}}
+replicates the argument array (which can of any dimensionality) `n` times and behaves
+thus similarly to list replicate, whereas 
+{{{
+elementwiseReplicate:: (U.Elt e, Shape dim) => 
+  Array (dim :*: Int) e -> Int -> Array (dim :*: Int :*: Int) e
+elementwiseReplicate arr n =
+  replicate arr (IndexAll (IndexFixed n IndexNil))
+}}}
+replicates each element of an array `n` times (similarly to `map (replicate n)` on lists).
+
+
+Even though the index type serves well to express the relationship
+between the selector/multiplicator and the dimensionality of the
+argument and the result array, it is inconvenient to use, as the
+examples demonstrate. We therefore do need to add another layer to
+improve the usability of the library.
+
+Note that the library provides no way to statically check the pre- and
+postconditions on the actual size of arguments and results. This has
+to be done at run time using assertions.
+
 
 === Reordering, Shifting, Tiling ===
@@ -184 +283 @@
 }}}
 
-=== Shape Polymorphic Computations on Arrays ===
-
-The array operations described in this and the following subsection
-are available on both strict and delayed arrays, and yield the same
-result, with the exception that in case of delayed arrays, the result
-is only calculated once its forced by calling `fromDArray` or `forceDArray`. No
-intermediate array structures are ever created.
-
-The library provides a range of operation where the dimensionality of
-the result depends on the dimensionality of the argument in a
-non-trivial manner, which we want to be reflected in the type system. 
-Examples of such functions are generalised selection, which allows for 
-extraction of subarrays of arbitrary dimension, and generalised replicate,
-which allows replication of an array in any dimension (or dimensions). 
-
-For selection, we can informally state the relationship between dimensionality of
-the argument, the selector, and the result as follows:
-{{{
-select:: Array dim e -> <select dim' of dim array> -> Array dim' e
-}}}
-
-To express this relationship, the library provides the index GADT,
-which expresses a relationship between the inital and the projected
-dimensionality. It is defined as follows:
-
-{{{
-data Index a initialDim projectedDim where
-  IndexNil   :: Index a () ()
-  IndexAll   :: (Shape init, Shape proj) =>      
-                   Index a init proj -> Index a (init :*: Int) (proj :*: Int)
-  IndexFixed :: (Shape init, Shape proj) => a -> 
-                   Index a init proj -> Index a (init :*: Int)  proj
-
-type SelectIndex = Index Int
-type MapIndex    = Index ()
-}}}
-Given this definition, the type of `select` now becomes
-{{{
-select:: (U.Elt e, Shape dim, Shape dim') => Array dim e -> SelectIndex dim dim'  -> Array dim' e
-}}}
-Example:
-{{{
-arr:: Array DIM3 Double
-select arr (IndexFixed 3 (IndexAll (IndexAll IndexNil)))
-}}}
-The index type is also used to express the type of generalised replicate:
-{{{
-replicate:: Array dim' e -> SelectIndex dim dim'  -> Array dim e
-}}}
-Even though the index type serves well to express the relationship
-between the selector/multiplicator and the dimensionality of the
-argument and the result array, it is somehow inconvenient to use, as
-the examples demonstrate. This is therefore another example where we
-need to add another layer to improve the usability of the library. 
-
-Note that the library provides no way to statically check the pre- and
-postconditions on the actual size of arguments and results. This has
-to be done at run time using assertions.
-
-== Array Operations ==
-   
-Backpermute and default backpermute are two general operations which allow 
-the programmer to express all structural operations which reorder or extract
-elements based on their position in the argument array:
-{{{
-backpermute:: (U.Elt e, Shape dim, Shape dim') => 
-  Array dim e -> dim' -> (dim' -> dim) -> Array dim' e
-
-backpermuteDft::(U.Elt e, Shape dim, Shape dim') => 
-  Array dim e -> e -> dim' -> (dim' -> Maybe dim) -> Array dim' e
-}}}
-
-
-
-The following operations could be (and in the sequential implementation indeed are)  expressed
-in terms of backpermute and default backpermute. However, a programmer should aim at using more
-specialised functions when provided, as they carry more information about the pattern of reordering. 
-In particular in the parallel case, this could be used to provide significantly more efficient 
-implementation which make use of locality and communication patterns.
-{{{
-shift:: (Shape dim, U.Elt e) => Array dim e -> e -> dim -> Array dim e
-
-rotate:: (Shape dim, U.Elt e) => Array dim e -> e -> dim -> Array dim e
-
-tile::  (Shape dim, U.Elt e) => Array dim e -> dim -> dim -> Array dim e
-}}}