Changes between Version 13 and Version 14 of DataParallel/Regular


Ignore:
Timestamp:
Dec 15, 2009 5:06:32 AM (4 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