Changes between Version 7 and Version 8 of DataParallel/Regular
 Timestamp:
 May 13, 2009 1:10:52 PM (7 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

DataParallel/Regular
v7 v8 17 17 The 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. 18 18 19 '''SLPJ: perhaps early give some SAC examples and the corresponding 20 code for us.''' 19 21 20 22 21 == The regular array type == 23 22 23 === SaC === 24 25 === DPH === 24 26 Regular parallel arrays are similar to arrays in SAC, with one major 25 27 difference: 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?'''28 is 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. 27 29 28 30 An multidimensional array is parametrised with its dimensionality and its … … 30 32 31 33 {{{ 32 (Ix (Shape dim), Elt a) => Array dim a33 34 }}} 35 where I Xis the standard Haskell index class, Shape is a type family defined on tuples of integers, including nullary34 (Ix (Shape dim), U.Elt a) => Array dim a 35 36 }}} 37 where Ix is the standard Haskell index class, Shape is a type family defined on tuples of integers, including nullary 36 38 tuples  arrays of which correspond to scalar values. So, for example 37 39 {{{ 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 42 45 43 46 Internally, shapes are represented as nested pairs … … 49 52 }}} 50 53 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 54 For readability, we define the following type synonyms: 55 {{{ 56 type DIM0 = Shape () 57 type DIM1 = Shape Int 58 type DIM2 = Shape (Int, Int) 59 type DIM3 = Shape (Int, Int, Int) 60 }}} 55 61 == Operations == 56 62 63 === Array Shapes === 64 The `shape` function returns the shape of an ndimensional array as ntuple: 65 {{{ 66 shape :: Array dim e > Shape dim 67 }}} 68 For example 69 {{{ 70 matrixMult:: (Elt e, Num e) => Array DIM2 > Array DIM2 e > Array DIM2 e 71 matrixMult 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 78 reshape ::(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 57 84 === Creating Arrays === 58 85 … … 61 88 fromNArray:: U.Elt r => U.Array r > Array DIM1 r 62 89 }}} 63 '''SLPJ: what is U? What is U.Array?''' 64 and from scalar values: 90 where `U.Array` is the array type defined in `Data.Array.Parallel.Unlifted`  that is, nonnested parallel arrays. 91 65 92 {{{ 66 93 fromScalar:: U.Elt r => r > Array DIM0 r 67 94 }}} 68 '' 'SLPJ: whoa! What are `DIM1`, `DIM0`? Presumably you mean 1dimensional etc. But indexed by what? Always `Int`? Maybe that's ok; but say so.'''95 '' 69 96 and bpermuteR, which creates a new array of new shape, using values of the argument array. 70 97 {{{ 71 98 bpermuteR:: Array dim e > Shape dim' > (Shape dim' > Shape dim) > Array dim' 72 99 }}} 73 For example, transposition of a two dimensional array can be defined in terms of mkArray as follows '''SLPJ: in terms of `bpermuteR` perhaps?''':100 For example, transposition of a two dimensional array can be defined in terms of bpermuteR as follows: 74 101 {{{ 75 102 transpose:: Array DIM2 a > Array DIM2 a 76 transpose arr = bpermuteR arr ( n,m) (\(i,j) > (j,i))103 transpose arr = bpermuteR arr (m,n) (\(i,j) > (j,i)) 77 104 where (n,m) = shape arr 78 105 }}} 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)`?'''80 106 Or cutting a 3 x 3 tile starting at indices (0,0) out of a two dimensional matrix: 81 107 {{{ … … 103 129 }}} 104 130 '''SLPJ: didn't understand scan'''. Manipulating the shape of arrays: 105 {{{106  size of both shapes have to be the same, otherwise runtime error107 reshape ::(Ix (Shape dim), Ix (Shape dim')) =>108 (Shape dim)  new shape109 > Array dim' a  array to be reshaped110 > Array dim a111 }}}112 131 '''SLPJ: why doesn't `reshape` need the size of the result array, as `bpermuteR` did.''' 113 132