Changes between Version 15 and Version 16 of DataParallel/Regular


Ignore:
Timestamp:
Jan 12, 2010 4:37:58 AM (6 years ago)
Author:
gckeller
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Regular

    v15 v16  
    159159}}}
    160160
     161=== Shape Polymorphic Computations on Arrays ===
     162
     163
     164The library provides a range of operation where the dimensionality of
     165the result depends on the dimensionality of the argument in a
     166non-trivial manner, which we want to be reflected in the type system.
     167Examples of such functions are generalised selection, which allows for
     168extraction of subarrays of arbitrary dimension, and generalised replicate,
     169which allows replication of an array in any dimension (or dimensions). For example,
     170given a three dimensional matrix, we can use select to extract scalar element values,
     171rows, columns, as well as two dimensional matrices along any of the three axes.
     172
     173For selection, we can informally state the relationship between dimensionality of
     174the argument, the selector, and the result as follows:
     175{{{
     176select:: Array dim e -> <select dim' of dim array> -> Array dim' e
     177}}}
     178
     179Another example for such a generalised function would be a generalised
     180`map`, which can apply a function to all elements, all rows, all
     181columns, or submatrices of different orientation of a multidimensional
     182array.
     183
     184For the former example, we need a way to express the relationship between the
     185shape of the argument and the shape and orientation of the result, as well as
     186the numerical position of the structure (i.e., first, second, third element).
     187In case of the generalised `map`, we don't need the numerical information, since
     188the operation will be applied to all elements, rows, columns etc.
     189
     190To express this dependency between input and output shape and orientation,
     191as well as possibly a concrete position,  the library provides the `Index` GADT,
     192which expresses a relationship between the source and the projected dimension.
     193It is defined as follows:
     194{{{
     195data Index a initialDim projectedDim where
     196  IndexNil   :: Index a initialDim initialDim
     197  IndexAll   :: (Shape init, Shape proj) =>     
     198                   Index a init proj -> Index a (init :*: Int) (proj :*: Int)
     199  IndexFixed :: (Shape init, Shape proj) => a ->
     200                   Index a init proj -> Index a (init :*: Int)  proj
     201}}}
     202To refer to a specific element, the type parameter `a` is instantiated with the type `Int`, otherwise
     203with the unit type:
     204{{{
     205type SelectIndex = Index Int
     206type MapIndex    = Index ()
     207}}}
     208Given this definition, the type of `select` now becomes
     209{{{
     210select:: (U.Elt e, Shape dim, Shape dim') => Array dim e -> SelectIndex dim dim'  -> Array dim' e
     211}}}
     212Example:
     213{{{
     214arr:: Array (() :*: Int :*: Int :*: Int) Double
     215
     216arr' :: () :*: Int :*: Int
     217arr' = select arr (IndexFixed 3 (IndexAll (IndexAll IndexNil)))
     218}}}
     219We could generalise this further, to extract from any array `arr` which is at least one dimensional
     220the third element:
     221{{{
     222arr:: Shape dim => Array (dim :*: Int) Double
     223
     224arr' :: Array dim Double
     225arr' = select arr (IndexFixed 3 IndexNil)
     226}}}
     227
     228
     229The index type is also used to express the type of generalised replicate
     230{{{
     231replicate:: Array dim' e -> SelectIndex dim dim'  -> Array dim e
     232}}}
     233which, given an array, can be used to expand it along any dimension. For example,
     234{{{
     235simpleReplicate:: (U.Elt e, Shape dim) => Array dim e -> Int -> Array (dim :*: Int) e
     236simpleReplicate arr n =
     237  replicate arr (IndexFixed n IndexNil)
     238}}}
     239replicates the argument array (which can of any dimensionality) `n` times and behaves
     240thus similarly to list replicate, whereas
     241{{{
     242elementwiseReplicate:: (U.Elt e, Shape dim) =>
     243  Array (dim :*: Int) e -> Int -> Array (dim :*: Int :*: Int) e
     244elementwiseReplicate arr n =
     245  replicate arr (IndexAll (IndexFixed n IndexNil))
     246}}}
     247replicates each element of an array `n` times (similarly to `map (replicate n)` on lists).
     248
     249
     250Even though the index type serves well to express the relationship
     251between the selector/multiplicator and the dimensionality of the
     252argument and the result array, it is inconvenient to use, as the
     253examples demonstrate. We therefore do need to add another layer to
     254improve the usability of the library.
     255
     256Note that the library provides no way to statically check the pre- and
     257postconditions on the actual size of arguments and results. This has
     258to be done at run time using assertions.
     259
    161260
    162261=== Reordering, Shifting, Tiling ===
     
    184283}}}
    185284
    186 === Shape Polymorphic Computations on Arrays ===
    187 
    188 The array operations described in this and the following subsection
    189 are available on both strict and delayed arrays, and yield the same
    190 result, with the exception that in case of delayed arrays, the result
    191 is only calculated once its forced by calling `fromDArray` or `forceDArray`. No
    192 intermediate array structures are ever created.
    193 
    194 The library provides a range of operation where the dimensionality of
    195 the result depends on the dimensionality of the argument in a
    196 non-trivial manner, which we want to be reflected in the type system.
    197 Examples of such functions are generalised selection, which allows for
    198 extraction of subarrays of arbitrary dimension, and generalised replicate,
    199 which allows replication of an array in any dimension (or dimensions).
    200 
    201 For selection, we can informally state the relationship between dimensionality of
    202 the argument, the selector, and the result as follows:
    203 {{{
    204 select:: Array dim e -> <select dim' of dim array> -> Array dim' e
    205 }}}
    206 
    207 To express this relationship, the library provides the index GADT,
    208 which expresses a relationship between the inital and the projected
    209 dimensionality. It is defined as follows:
    210 
    211 {{{
    212 data Index a initialDim projectedDim where
    213   IndexNil   :: Index a () ()
    214   IndexAll   :: (Shape init, Shape proj) =>     
    215                    Index a init proj -> Index a (init :*: Int) (proj :*: Int)
    216   IndexFixed :: (Shape init, Shape proj) => a ->
    217                    Index a init proj -> Index a (init :*: Int)  proj
    218 
    219 type SelectIndex = Index Int
    220 type MapIndex    = Index ()
    221 }}}
    222 Given this definition, the type of `select` now becomes
    223 {{{
    224 select:: (U.Elt e, Shape dim, Shape dim') => Array dim e -> SelectIndex dim dim'  -> Array dim' e
    225 }}}
    226 Example:
    227 {{{
    228 arr:: Array DIM3 Double
    229 select arr (IndexFixed 3 (IndexAll (IndexAll IndexNil)))
    230 }}}
    231 The index type is also used to express the type of generalised replicate:
    232 {{{
    233 replicate:: Array dim' e -> SelectIndex dim dim'  -> Array dim e
    234 }}}
    235 Even though the index type serves well to express the relationship
    236 between the selector/multiplicator and the dimensionality of the
    237 argument and the result array, it is somehow inconvenient to use, as
    238 the examples demonstrate. This is therefore another example where we
    239 need to add another layer to improve the usability of the library.
    240 
    241 Note that the library provides no way to statically check the pre- and
    242 postconditions on the actual size of arguments and results. This has
    243 to be done at run time using assertions.
    244 
    245 == Array Operations ==
    246    
    247 Backpermute and default backpermute are two general operations which allow
    248 the programmer to express all structural operations which reorder or extract
    249 elements based on their position in the argument array:
    250 {{{
    251 backpermute:: (U.Elt e, Shape dim, Shape dim') =>
    252   Array dim e -> dim' -> (dim' -> dim) -> Array dim' e
    253 
    254 backpermuteDft::(U.Elt e, Shape dim, Shape dim') =>
    255   Array dim e -> e -> dim' -> (dim' -> Maybe dim) -> Array dim' e
    256 }}}
    257 
    258 
    259 
    260 The following operations could be (and in the sequential implementation indeed are)  expressed
    261 in terms of backpermute and default backpermute. However, a programmer should aim at using more
    262 specialised functions when provided, as they carry more information about the pattern of reordering.
    263 In particular in the parallel case, this could be used to provide significantly more efficient
    264 implementation which make use of locality and communication patterns.
    265 {{{
    266 shift:: (Shape dim, U.Elt e) => Array dim e -> e -> dim -> Array dim e
    267 
    268 rotate:: (Shape dim, U.Elt e) => Array dim e -> e -> dim -> Array dim e
    269 
    270 tile::  (Shape dim, U.Elt e) => Array dim e -> dim -> dim -> Array dim e
    271 }}}