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 | |
| 17 | DArrays are collections of values of `primitive' type, which are |
| 18 | member of the class Data.Parallel.Array.Unlifted.Elt, which includes |
| 19 | all basic types like Float, Double, Bool, Char, Integer, and pairs |
| 20 | constructed with Data.Parallel.Array.Unlifted.(:*:), including (). |
| 21 | |
| 22 | === The Shape class === |
| 23 | |
| 24 | Values of class Shape serve two purposes: they can describe the dimensionality and |
| 25 | size of an array (in which case we refer to them as 'shape'), and they can also refer |
| 26 | to the position of a particular element in the array (in which case we refer to them |
| 27 | as an 'index'). It provides the following methods: |
| 28 | |
| 29 | {{{ |
| 30 | class (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 |
87 | | |
88 | | |
89 | | === Shape Invariant Computations on Arrays === |
| 102 | the result of `toDArray` is a DArray which contains an indexing function into |
| 103 | an 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 |
| 105 | every index of the range, and replaces `dArrayFn` by a simple indexing function into an array |
| 106 | of the result values. |
| 107 | {{{ |
| 108 | forceDArray:: (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 | |
| 115 | The `map` operation takes a function over element types and applies it to every |
| 116 | data element of the DArray, which can have arbitrary dimensionality. Note that |
| 117 | it is not possible to use this function to apply an operation for example to every |
| 118 | row 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 | |
| 122 | Similarily, `zip` and `zipWith` apply to every data element in the array as well. Both arguments |
| 123 | have to have the same dimensionality (which is enforced by the type system). If they have a different |
| 124 | shape, 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 | {{{ |
| 127 | zipWith:: (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 |
| 129 | zip:: (U.Elt a, U.Elt b, A.Shape dim) => |
| 130 | DArray dim a -> DArray dim b-> DArray dim (a :*: b) |
| 131 | }}} |
| 132 | |
| 133 | The function `fold` collapses the values of the innermost rows of an array of at least dimensionality 1. |
| 134 | {{{ |
| 135 | fold :: (U.Elt e, A.Shape dim) => |
| 136 | (e -> e-> e) -> e -> DArray (dim :*: Int) e -> DArray dim e |
| 137 | }}} |
| 138 | |
| 139 | Again, it's not possible to use `fold` directly to collapse an array along any other axis, but, as |
| 140 | we will see shortly, this can be easily done using other functions in combination with `fold`. |
| 141 | |
| 142 | |
| 143 | {{{ |
| 144 | |
| 145 | TODO: MISSING: description of mapStencil |
| 146 | }}} |
| 147 | |
| 148 | |
| 149 | === Reordering, Shifting, Tiling === |
| 150 | |
| 151 | Backpermute and default backpermute are two very versatile operations which allow |
| 152 | the programmer to express all structural operations which reorder or extract |
| 153 | elements based on their position in the argument array: |
| 154 | {{{ |
| 155 | backpermute:: (U.Elt e, A.Shape dim, A.Shape dim') => |
| 156 | DArray dim e -> dim' -> (dim' -> dim) -> DArray dim' e |
| 157 | backpermuteDft::(U.Elt e, A.Shape dim, A.Shape dim') => |
| 158 | DArray dim e -> e -> dim' -> (dim' -> Maybe dim) -> DArray dim' e |
| 159 | }}} |
| 160 | The function `backpermute` gets a source array, the shape of the new array, and |
| 161 | a function which maps each index of the new array to an index of the source array (and |
| 162 | thus indirectly provides a value for each index in the new array). Default backpermute is |
| 163 | additionally provided with a default value which is inserted in the array in cases where the |
| 164 | index function returns `Nothing`. (Remark: should probably be replaced by a default array instead of |
| 165 | default 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 |
| 168 | new shape has to have the same size as the original shape. |
| 169 | {{{ |
| 170 | reshape:: (Shape dim', Shape dim, U.Elt e) => DArray dim e -> dim' -> DArray dim' e |
| 171 | }}} |
| 172 | |
| 173 | === Shape Polymorphic Computations on Arrays === |