7 | | Languages like SAC, which provide high-level support for operations on multi-dimensional arrays, offer shape invariant operations. If we want to model this on a library level, we either have to give up type safety to a |
8 | | large extend (for example, by encoding the shape as a list of integer values whose length is proportionate to its dimensionality) or use sophisticated language features like GADTs, which may impede the usability of the library for inexperienced users. |
| 12 | == Strict Arrays, Delayed Array and Shape Data Type == |
| 13 | Both strict and delayed arrays are parametrised with their shape - that is, their dimensionality and size |
| 14 | of each dimension. The shape type class has the following interface: |
| 15 | |
| 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 |
| 37 | }}} |
| 38 | |
| 39 | Note that a `Shape` has to be in the type class `Elt` imported from `Data.Parallel.Array.Unboxed` so |
| 40 | that it can be an element of `Data.Parallel.Array.Unboxed.Array`. |
| 41 | |
| 42 | The following instances are defined |
| 43 | {{{ |
| 44 | instance Shape () |
| 45 | instance Shape sh => Shape (sh :*: Int) |
| 46 | }}} |
| 47 | so we have inductively defined n-tuples of `Int` values to represent shapes. This somewhat unusual representation |
| 48 | is necessary to be able to inductively define operations on `Shape`. It should, however, be hidden from the library |
| 49 | user in favour of the common tuple representation. |
| 50 | |
| 51 | For convenience, we provide type synonyms for dimensionality up to five: |
| 52 | {{{ |
| 53 | type DIM0 = () |
| 54 | type DIM1 = (DIM0 :*: Int) |
| 55 | .... |
| 56 | }}} |
43 | | (Shape dim, U.Elt a) => Array dim a |
44 | | }}} |
45 | | The element type of multidimensional arrays is restricted to the type class `Elt` exported from ` Data.Array.Parallel.Unlifted`, and contains all primitive types like `Bool`, `Int`, `Float`, and pairs thereof constructed with the type constructor `:*:`, also exported from the same module. The elements of the type class `Shape` describe the shape of a multidimensional array, but also indices into |
46 | | an array ('''Note:''' so, is `Shape` really the right name? `Ix` however, also doesn't seem to be right, since it is too different from the`Ix` defined in the Prelude) |
47 | | {{{ |
48 | | class U.Elt sh => Shape sh where |
49 | | dim :: sh -> Int -- number of dimensions (>= 0) |
50 | | size :: sh -> Int -- for a shape, yield the total number of |
51 | | -- elements in that array |
52 | | index :: sh -> sh -> Int -- corresponding index into a linear, row-major |
53 | | -- representation of the array (first argument |
54 | | -- is the shape) |
| 109 | data Index a initialDim projectedDim where |
| 110 | IndexNil :: Index a () () |
| 111 | IndexAll :: (Shape init, Shape proj) => |
| 112 | Index a init proj -> Index a (init :*: Int) (proj :*: Int) |
| 113 | IndexFixed :: (Shape init, Shape proj) => a -> |
| 114 | Index a init proj -> Index a (init :*: Int) proj |
70 | | We use the following type synonyms to improve the readability of the code: |
71 | | {{{ |
72 | | type DIM0 = () |
73 | | type DIM1 = DIM0 :*: Int |
74 | | type DIM2 = DIM1 :*: Int |
75 | | type DIM3 = DIM2 :*: Int |
76 | | }}} |
77 | | == Operations == |
78 | | |
79 | | === Array Shapes === |
80 | | The `shape` function returns the shape of an n-dimensional array as n-tuple: |
81 | | {{{ |
82 | | shape :: Array dim e -> dim |
83 | | }}} |
84 | | For example |
85 | | {{{ |
86 | | matrixMult:: (Elt e, Num e) => Array DIM2 -> Array DIM2 e -> Array DIM2 e |
87 | | matrixMult m1 m2| snd (shape m1) == fst (shape m2) = multiply .... |
88 | | | otherwise = error "Incompatible array sizes in matrixMult..." |
89 | | |
90 | | }}} |
91 | | |
92 | | {{{ |
93 | | -- size of both shapes have to be the same, otherwise runtime error |
94 | | reshape ::(Shape dim, Shape dim') => |
95 | | dim -- new shape |
96 | | -> Array dim' a -- array to be reshaped |
97 | | -> Array dim a |
98 | | }}} |
99 | | |
100 | | === Creating Arrays === |
101 | | |
102 | | A new array can be created from a flat parallel array |
103 | | {{{ |
104 | | fromNArray:: U.Elt r => U.Array r -> Array DIM1 r |
105 | | }}} |
106 | | |
107 | | {{{ |
108 | | fromScalar:: U.Elt r => r -> Array DIM0 r |
109 | | }}} |
110 | | '' |
111 | | and bpermuteR, which creates a new array of new shape, using values of the argument array. |
112 | | {{{ |
113 | | bpermuteR:: Array dim e -> Shape dim' -> (Shape dim' -> Shape dim) -> Array dim' |
114 | | }}} |
115 | | For example, transposition of a two dimensional array can be defined in terms of bpermuteR as follows: |
116 | | {{{ |
117 | | transpose:: Array DIM2 a -> Array DIM2 a |
118 | | transpose arr = bpermuteR arr (m,n) (\(i,j) -> (j,i)) |
119 | | where (n,m) = shape arr |
120 | | }}} |
121 | | Or cutting a 3 x 3 tile starting at indices (0,0) out of a two dimensional matrix: |
122 | | {{{ |
123 | | tile:: Array DIM2 a -> Array DIM2 a |
124 | | tile arr = bpermuteR arr (3,3) id |
125 | | }}} |
126 | | |
127 | | '''SLPJ: Does the `Shape` stuff need to be exposed at this level. Could we not work just in terms of the `(Int,Int)` indices the programmer expects, and hide the shapery?''' |
128 | | |
129 | | === Manipulating array values === |
130 | | |
131 | | All the shape invariant operations available on parallel arrays are also defined on regular arrays: |
132 | | {{{ |
133 | | map :: (Elt a, Elt b) => (a -> b) -> Array dim a -> Array dim b |
134 | | zipWith :: (Elt a, Elt b, Elt c) => (a -> b -> c) -> Array dim a -> Array dim b -> Array dim c |
135 | | }}} |
136 | | Parallel array operations which can change the shape are restricted to one dimensional arrays, to make sure that the |
137 | | result is still a regular array. |
138 | | {{{ |
139 | | filter :: Elt a => (a -> Bool) -> Array DIM1 a -> Array DIM1 a |
140 | | scan :: Elt a => ((a, a) -> a) -- combination function |
141 | | -> a -- default value |
142 | | -> Array (dim, Int) a -- linear array |
143 | | -> (Array dim a, Array (dim, Int) a) |
144 | | }}} |
145 | | '''SLPJ: didn't understand scan'''. Manipulating the shape of arrays: |
146 | | '''SLPJ: why doesn't `reshape` need the size of the result array, as `bpermuteR` did.''' |
147 | | |
148 | | === Changing the dimensionality of an array === |
149 | | |
150 | | |
151 | | |
152 | | |
153 | | ==== The index type ==== |
154 | | |
155 | | Two operations we provide change the dimensionality of an argument |
156 | | array, namely the generalised indexing function, which extracts |
157 | | subarrays from an multidimensional array, and generalised replicate, |
158 | | which expands the array along specified axes. To encode the |
159 | | relationship between the argument's dimensionality and the result's dimensionality, |
160 | | we use the Index type: |
161 | | {{{ |
162 | | (!) :: Elt e => Arr dim e -> Index dim dim' -> Arr dim' e |
163 | | |
164 | | replicate :: Index dim' dim -- ^specifies new dimensions |
165 | | -> Array dim a -- ^data to be replicated |
166 | | -> Array dim' a |
167 | | |
168 | | }}} |
169 | | where Index is defined as |
170 | | {{{ |
171 | | data Index initialDim projectedDim where |
172 | | IndexNil :: Index () () |
173 | | IndexAll :: Index init proj -> Index (init, Int) (proj, Int) |
174 | | IndexFixed :: Int -> Index init proj -> Index (init, Int) proj |
175 | | }}} |
176 | | |
177 | | The index type is similar to generalized selection in SaC. For example, the selection vector |
178 | | {{{ |
179 | | (1,2,3) |
180 | | }}} |
181 | | which indexes the fourth element in the third subarray of the second matrix in a three dimensional array would correspond to the index value |
182 | | {{{ |
183 | | IndexFixed 1 (IndexFixed 2 (IndexFixed 3 IndexNil)) :: Index ((((),Int), Int),,Int) () |
184 | | }}} |
185 | | Where the type tells us that the index value describes a projection from a three dimensional array to a scalar value. More interestingly, the SaC selection |
186 | | {{{ |
187 | | (1,.,3) |
188 | | }}} |
189 | | specifies a subvector (i.e., all the values in position (1,i,3) for all i's in the arrays range. This corresponds to |
190 | | {{{ |
191 | | IndexFixed 1 (IndexAll (IndexFixed 3 IndexNil)):: Index ((((),Int), Int),,Int) ((),Int) |
192 | | }}} |
193 | | ==== Examples ==== |
194 | | |
195 | | To demonstrate the use of the Index type, consider the following replicates expressed in terms of generalised replicate: |
196 | | {{{ |
197 | | -- 'chunk replicate' - create a two dimensional array by replicating the one dimensional |
198 | | -- argument array n times |
199 | | replicateC:: Int -> Array DIM1 a -> Array DIM2 a |
200 | | replicateC n arr = RArray.replicate (IndexFixed n (IndexAll IndexNil)) arr |
201 | | |
202 | | -- create a two dimensional array by replicating each element n times |
203 | | -- 'replicateLifted' |
204 | | replicateL:: Int -> Array DIM1 a -> Array DIM2 a |
205 | | replicateL n arr = RArray.replicate (IndexAll (IndexFixed n IndexNil)) arr |
206 | | |
207 | | -- 'chunkreplicate' on a two dimensional array |
208 | | -- |
209 | | replicateC2:: Int -> Array DIM2 a -> Array DIM3 a |
210 | | replicateC2 n arr = RArray.replicate (IndexFixed n (IndexAll (IndexAll IndexNil))) arr |
211 | | |
212 | | |
213 | | replicateLL:: Int -> Array DIM2 a -> Array DIM3 a |
214 | | replicateLL n arr = RArray.replicate (IndexAll (IndexAll (IndexFixed n IndexNil))) arr |
215 | | }}} |
216 | | |
217 | | In the actual array language (user level) the DPH should provide a general selection-like notation for index expressions. |
218 | | |
219 | | === Comparison with SaC === |
220 | | |
221 | | We started out with the goal to provide support for SaC like array programming. In this section compares SaC's functionality with the approach described in this document. |
222 | | |