Changes between Version 7 and Version 8 of DataParallel/Regular


Ignore:
Timestamp:
May 13, 2009 1:10:52 PM (6 years ago)
Author:
gckeller
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Regular

    v7 v8  
    1717The remainder of this document is a first design draft for SAC style language support of multidimensional arrays in the context of DPH. The implementation is not completed yet, and there are several open questions. 
    1818 
    19 '''SLPJ: perhaps early give some SAC examples and the corresponding 
    20 code for us.''' 
     19 
    2120 
    2221== The regular array type == 
    23   
     22 
     23=== SaC === 
     24 
     25=== DPH ===  
    2426Regular parallel arrays are similar to arrays in SAC, with one major 
    2527difference: array operations in DPH are fully typed, and consequently, what 
    26 is called 'shape invariant programming' in SAC works differently in DPH. In particular, the dimensionality of an array (not its size, however) are encoded in its type.  '''SLPJ: unlike SAC, where functions can be polymorphic even in the dimensionality of the array?''' 
     28is called 'shape invariant programming' in SAC works differently in DPH. In particular, in DPH the dimensionality of an array (not its size, however) are encoded in its type. 
    2729 
    2830An multidimensional array is parametrised with its dimensionality and its 
     
    3032 
    3133{{{ 
    32 (Ix (Shape dim), Elt a)  => Array dim a  
    33  
    34 }}} 
    35 where IX is the standard Haskell index class,  Shape is a type family defined on tuples of integers, including nullary 
     34(Ix (Shape dim), U.Elt a)  => Array dim a  
     35 
     36}}} 
     37where Ix is the standard Haskell index class,  Shape is a type family defined on tuples of integers, including nullary 
    3638tuples - arrays of which correspond to scalar values. So, for example 
    3739{{{ 
    38   Array ()      Double    -- scalar double precision floating point value 
    39   Array (3,2) Double   -- two dimensional array (matrix) of three rows, two columns 
    40 }}} 
    41 '''SLPJ: urk. Is `(2,3)` a type?!  Or did you mean `Array (Int,Int) Double`?''' 
     40  Array ()        Double   -- scalar double precision floating point value 
     41  Array (Int,Int) Double   -- two dimensional array (matrix) 
     42}}} 
     43`U.Elt` is the `Elt` type class defined in ` Data.Array.Parallel.Unlifted` and contains all primitive types like `Int`, `Bool`, and tuples thereof. 
     44 
    4245 
    4346Internally, shapes are represented as nested pairs 
     
    4952}}} 
    5053 
    51 Elements types are restricted to the element type of flat parallel 
    52 arrays, that it, primitive types like integers, boolean and floating 
    53 point numbers, and tuples. '''SLPJ: so what is in class `Elt`?''' 
    54  
     54For readability, we define the following type synonyms: 
     55{{{ 
     56type DIM0 = Shape () 
     57type DIM1 = Shape Int 
     58type DIM2 = Shape (Int, Int) 
     59type DIM3 = Shape (Int, Int, Int) 
     60}}} 
    5561== Operations == 
    5662 
     63=== Array Shapes === 
     64The `shape` function returns the shape of an n-dimensional array as n-tuple: 
     65{{{ 
     66shape  :: Array dim e -> Shape dim 
     67}}} 
     68For example 
     69{{{ 
     70matrixMult:: (Elt e, Num e) => Array DIM2 -> Array DIM2 e -> Array DIM2 e  
     71matrixMult m1 m2| snd (shape m1) == fst (shape m2) = multiply .... 
     72                | otherwise                                             = error "Incompatible array sizes in matrixMult..." 
     73 
     74}}} 
     75 
     76{{{ 
     77-- size of both shapes have to be the same, otherwise runtime error 
     78reshape     ::(Ix (Shape dim), Ix (Shape dim')) => 
     79                 (Shape dim)                  -- new shape 
     80              -> Array dim' a                 -- array to be reshaped 
     81              -> Array dim a 
     82}}} 
     83 
    5784=== Creating Arrays === 
    5885 
     
    6188fromNArray:: U.Elt r => U.Array r -> Array DIM1 r 
    6289}}} 
    63 '''SLPJ: what is U?  What is U.Array?''' 
    64 and from scalar values: 
     90where `U.Array` is the array type defined in `Data.Array.Parallel.Unlifted` - that is, non-nested parallel arrays. 
     91  
    6592{{{ 
    6693fromScalar::  U.Elt r => r -> Array DIM0 r 
    6794}}} 
    68 '''SLPJ: whoa!  What are `DIM1`, `DIM0`?  Presumably you mean 1-dimensional etc.  But indexed by what?  Always `Int`?  Maybe that's ok; but say so.''' 
     95'' 
    6996and  bpermuteR, which creates a new array of new shape, using values of the argument array. 
    7097{{{ 
    7198bpermuteR:: Array dim e -> Shape dim' -> (Shape dim' -> Shape dim) -> Array dim' 
    7299}}} 
    73 For example, transposition of a two dimensional array can be defined in terms of mkArray as follows '''SLPJ: in terms of `bpermuteR` perhaps?''': 
     100For example, transposition of a two dimensional array can be defined in terms of bpermuteR as follows: 
    74101{{{ 
    75102transpose:: Array DIM2 a -> Array DIM2 a 
    76 transpose arr = bpermuteR arr (n,m) (\(i,j) -> (j,i)) 
     103transpose arr = bpermuteR arr (m,n) (\(i,j) -> (j,i)) 
    77104  where (n,m) = shape arr 
    78105}}} 
    79 '''SLPJ: presumably `shape :: Array dim a -> Shape dim`?  Or perhaps rather `shape :: Array dim a -> dim`?'''.  '''SLPJ: did you mean `bpermuteR arr (m,n)`?''' 
    80106Or cutting a 3 x 3 tile starting at indices (0,0) out of a two dimensional matrix: 
    81107{{{ 
     
    103129}}} 
    104130'''SLPJ: didn't understand scan'''.  Manipulating the shape of arrays: 
    105 {{{ 
    106 -- size of both shapes have to be the same, otherwise runtime error 
    107 reshape     ::(Ix (Shape dim), Ix (Shape dim')) => 
    108                  (Shape dim)                  -- new shape 
    109               -> Array dim' a                 -- array to be reshaped 
    110               -> Array dim a 
    111 }}} 
    112131'''SLPJ: why doesn't `reshape` need the size of the result array, as `bpermuteR` did.''' 
    113132