Changes between Version 15 and Version 16 of DataParallel/Regular


Ignore:
Timestamp:
Jan 12, 2010 4:37:58 AM (4 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 }}}