Changes between Version 13 and Version 14 of DataParallel/Regular


Ignore:
Timestamp:
Dec 15, 2009 5:06:32 AM (6 years ago)
Author:
gckeller
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Regular

    v13 v14  
    1 = Shape Polymorphic Arrays and Delayed Arrays =
    2 
    3 The library provides a layer on top of DPH unlifted arrays to support multi-dimensional arrays, and operations
    4 like maps, folds, permutations, shifts and so on. The interface for delayed arrays is similar, but in contrast
     1
     2The library provides a layer on top of DPH unlifted arrays to support multi-dimensional arrays, and shape polymorphic
     3operations for fast sequential and parallel execution. The interface for delayed arrays is similar, but in contrast
    54to operations on the former, any operation on a delayed array is not evaluated. To force evaluation, the programmer
    6 has to explicitely convert a delayed array to a strict array.
     5has to explicitly convert them to a strict array.
    76
    87The current implementation of the library exposes some implementation details the user of the library shouldn't
    98have to worry about. Once the design of the library is finalised, most of these will be hidden by distinguishing
    10 between internal types and representation types
     9between internal types and representation types.
    1110
    1211== Strict Arrays, Delayed Array and Shape Data Type ==
     
    1413of each dimension. The shape type class has the following interface:
    1514
    16 {{{
    17 class (Show sh, U.Elt sh) => Shape sh where
    18   dim   :: sh -> Int           -- ^number of dimensions (>= 0)
    19   size  :: sh -> Int           -- ^for a *shape* yield the total number of
    20                                -- elements in that array
    21   index :: sh -> sh -> Int     -- ^corresponding index into a linear, row-major
    22                                -- representation of the array (first argument
    23                                -- is the shape)
    24   indexInv:: sh -> Int -> sh   -- ^given index into linear row major representation,
    25                                -- calculates index into array
    26   range      :: sh -> U.Array sh  -- ^all the valid indices in a shape. The following
    27                                   -- equality should hold:
    28                                   -- map (index sh) (range sh) = [:0..(size sh)-1:]
    29   inRange    :: sh -> sh -> Bool  -- ^determines if a given index is in range
    30   zeroDim    :: sh               
    31   addDim     :: sh -> sh -> sh    -- ^adds two shapes of the same dimensionality
    32   modDim     :: sh -> sh -> sh    -- ^modulo operation lifted on shapes
    33   addModDim  :: sh -> sh -> sh
    34 
    35   last    :: (sh :*: Int) -> Int  -- ^yields the innermost dimension of a shape
    36   inits   :: (sh :*: Int) -> sh   -- ^removes the innermost dimension from a shape
     15=== DArrays ===
     16
     17DArrays are collections of values of `primitive' type, which are
     18member of the class Data.Parallel.Array.Unlifted.Elt, which includes
     19all basic types like Float, Double, Bool, Char, Integer, and pairs
     20constructed with Data.Parallel.Array.Unlifted.(:*:), including ().
     21
     22=== The Shape class ===
     23
     24Values of class Shape serve two purposes: they can describe the dimensionality and
     25size of an array (in which case we refer to them as 'shape'), and they can also refer
     26to the position of a particular element in the array (in which case we refer to them
     27as an 'index'). It provides the following methods:
     28
     29{{{
     30class (Show sh, U.Elt sh, Eq sh, Rebox sh) => Shape sh where
     31  dim   :: sh -> Int           
     32  -- ^number of dimensions (>= 0)
     33  size  :: sh -> Int           
     34  -- ^for a *shape* yield the total number of  elements in that array
     35  toIndex :: sh -> sh -> Int     
     36  -- ^corresponding index into a linear representation of
     37  -- the array (first argument is the shape)
     38
     39  fromIndex:: sh -> Int -> sh   
     40  -- ^given index into linear row major representation, calculates
     41  -- index into array                               
     42
     43  range      :: sh -> U.Array sh
     44  -- ^all the valid indices in a shape. The following equality should hold:
     45  -- map (toIndex sh) (range sh) = [:0..(size sh)-1:]
     46
     47 
     48  inRange      :: sh -> sh -> Bool
     49  -- ^Checks if a given index is in the range of an array shape. I.e.,
     50  -- inRange sh ind == elem ind (range sh)
     51
     52  zeroDim      :: sh
     53  -- ^shape of an array of size zero of the particular dimensionality
     54
     55  intersectDim :: sh -> sh -> sh
     56  -- ^shape of an array of size zero of the particular dimensionality 
     57
     58  next:: sh -> sh -> Maybe sh
     59  -- ^shape of an array of size zero of the particular dimensionality   
    3760}}}
    3861
     
    4972user in favour of the common tuple representation.
    5073
    51 For convenience, we provide type synonyms for dimensionality up to five:
    52 {{{
    53 type DIM0 = ()
    54 type DIM1 = (DIM0 :*: Int)
    55 ....
    56 }}}
    57 
    58 
    5974== Operations on Arrays and Delayed Arrays ==
    6075
     
    6479{{{
    6580data Array dim e where
    66   Array { arrayShape    :: dim                -- ^extend of dimensions
    67         , arrayData     :: U.Array e          -- flat parallel array
    68         }               :: Array dim e
     81  Array:: { arrayShape    :: dim                -- ^extend of dimensions
     82          , arrayData     :: U.Array e          -- flat parallel array
     83           }  -> Array dim e
    6984  deriving Show
    7085
     
    7994  DArray :: {dArrayShape::dim -> dArrayFn:: (dim -> e)} -> DArray dim e
    8095}}}
     96
    8197Delayed arrays can be converted to and from strict arrays:
    82 (TODO: there needs to be an darray constructor function accepting the shape and the function as arguments)
    8398{{{
    8499toDArray:: (U.Elt e, Array.Shape dim)   => Array.Array dim e -> DArray dim e
    85100fromDArray:: (U.Elt e, Array.Shape dim) => DArray dim e      -> Array dim e
    86101}}}
    87 
    88 
    89 === Shape Invariant Computations on Arrays ===
     102the result of `toDArray` is a DArray which contains an indexing function into
     103an array. In general, the function `dArrayFn` can be much more complex.  The function
     104`forceDArray`  (should this be called `normalizeDArray`?) forces the evaluation `dArrayFn` on
     105every index of the range, and replaces `dArrayFn` by a simple indexing function into an array
     106of the result values.
     107{{{
     108forceDArray:: (U.Elt e, A.Shape dim) => DArray dim e -> DArray dim e
     109}}}
     110
     111== Collection Oriented Operations ==
     112
     113=== Elementwise Application of Functions ===
     114
     115The `map` operation takes a function over element types and applies it to every
     116data element of the DArray, which can have arbitrary dimensionality. Note that
     117it is not possible to use this function to apply an operation for example to every
     118row or column of a matrix. We will discuss how this can be done later on.
     119
     120{{{map:: (U.Elt a, U.Elt b, A.Shape dim) =>  (a -> b) -> DArray dim a -> DArray dim b}}}
     121
     122Similarily, `zip` and `zipWith` apply to every data element in the array as well. Both arguments
     123have to have the same dimensionality (which is enforced by the type system). If they have a different
     124shape, the result will have the intersection of both shapes. For example, zipping an array of shape
     125`(() :*: 4 :*: 6)` and `(() :*: 2 :*: 8)` results in an array of shape `(() :*: 2 :*: 6)`.
     126{{{
     127zipWith:: (U.Elt a, U.Elt b, U.Elt c, A.Shape dim) =>
     128  (a -> b -> c) -> DArray dim a -> DArray dim b-> DArray dim c
     129zip:: (U.Elt a, U.Elt b, A.Shape dim) =>
     130  DArray dim a -> DArray dim b-> DArray dim (a :*: b)
     131}}}         
     132
     133The function `fold` collapses the values of the innermost rows of  an array of at least dimensionality 1.
     134{{{
     135fold :: (U.Elt e, A.Shape dim) =>
     136 (e -> e-> e) -> e -> DArray (dim :*: Int)  e  -> DArray dim e
     137}}}
     138
     139Again, it's not possible to use `fold` directly to collapse an array along any other axis, but, as
     140we will see shortly, this can be easily done using other functions in combination with `fold`.
     141
     142
     143{{{
     144
     145TODO: MISSING: description of mapStencil
     146}}}
     147
     148
     149=== Reordering, Shifting, Tiling ===
     150
     151Backpermute and default backpermute are two very versatile operations which allow
     152the programmer to express all structural operations which reorder or extract
     153elements based on their position in the argument array:
     154{{{
     155backpermute:: (U.Elt e, A.Shape dim, A.Shape dim') =>   
     156  DArray dim e -> dim' -> (dim' -> dim) -> DArray dim' e
     157backpermuteDft::(U.Elt e, A.Shape dim, A.Shape dim') =>
     158  DArray dim e -> e -> dim' -> (dim' -> Maybe dim) -> DArray dim' e
     159}}}
     160The function `backpermute` gets a source array, the shape of the new array, and
     161a function which maps each index of the new array to an index of the source array (and
     162thus indirectly provides a value for each index in the new array). Default backpermute  is
     163additionally provided with a default value which is inserted in the array in cases where the
     164index function returns `Nothing`. (Remark: should probably be replaced by a default array instead of
     165default value for more generality)
     166
     167`reshape arr newShape` returns a new array with the same value as the argument array, but a new shape. The
     168new shape has to have the same size as the original shape.
     169{{{
     170reshape:: (Shape dim', Shape dim, U.Elt e) => DArray dim e -> dim' -> DArray dim' e
     171}}}
     172
     173=== Shape Polymorphic Computations on Arrays ===
    90174
    91175The array operations described in this and the following subsection
    92176are available on both strict and delayed arrays, and yield the same
    93177result, with the exception that in case of delayed arrays, the result
    94 is only calculated once its forced by calling `fromDArray`. No
     178is only calculated once its forced by calling `fromDArray` or `forceDArray`. No
    95179intermediate array structures are ever created.
    96180
    97181The library provides a range of operation where the dimensionality of
    98182the result depends on the dimensionality of the argument in a
    99 non-trivial matter, which we want to be reflected in the type system.
     183non-trivial manner, which we want to be reflected in the type system.
    100184Examples of such functions are generalised selection, which allows for
    101185extraction of subarrays of arbitrary dimension, and generalised replicate,
     
    160244
    161245
    162 {{{
    163 map:: (U.Elt a, U.Elt b, Shape dim) => (a -> b) -> Array dim a -> Array dim b
    164 
    165 zip:: (U.Elt a, U.Elt b, Shape dim) => Array dim a -> Array dim b-> Array dim (a :*: b)
    166 
    167 zipWith:: (U.Elt a, U.Elt b, U.Elt c, Shape dim) =>
    168           (a -> b -> c) -> Array dim a -> Array dim b-> Array dim c
    169 
    170 mapFold:: (U.Elt e, Shape dim) => (e -> e-> e) -> e -> Array (dim :*: Int) e  -> Array dim  e
    171 
    172 reshape:: (Shape dim', Shape dim, U.Elt e) => Array dim e -> dim' -> Array dim' e
    173 }}}
    174246
    175247The following operations could be (and in the sequential implementation indeed are)  expressed