# Changes between Version 15 and Version 16 of DataParallel/Regular

Show
Ignore:
Timestamp:
01/11/10 20:37:58 (3 years ago)
Comment:

--

Unmodified
Removed
Modified
• ## DataParallel/Regular

v15 v16
159159}}}
160160
161=== Shape Polymorphic Computations on Arrays ===
162
163
164The library provides a range of operation where the dimensionality of
165the result depends on the dimensionality of the argument in a
166non-trivial manner, which we want to be reflected in the type system.
167Examples of such functions are generalised selection, which allows for
168extraction of subarrays of arbitrary dimension, and generalised replicate,
169which allows replication of an array in any dimension (or dimensions). For example,
170given a three dimensional matrix, we can use select to extract scalar element values,
171rows, columns, as well as two dimensional matrices along any of the three axes.
172
173For selection, we can informally state the relationship between dimensionality of
174the argument, the selector, and the result as follows:
175{{{
176select:: Array dim e -> <select dim' of dim array> -> Array dim' e
177}}}
178
179Another example for such a generalised function would be a generalised
180`map`, which can apply a function to all elements, all rows, all
181columns, or submatrices of different orientation of a multidimensional
182array.
183
184For the former example, we need a way to express the relationship between the
185shape of the argument and the shape and orientation of the result, as well as
186the numerical position of the structure (i.e., first, second, third element).
187In case of the generalised `map`, we don't need the numerical information, since
188the operation will be applied to all elements, rows, columns etc.
189
190To express this dependency between input and output shape and orientation,
191as well as possibly a concrete position,  the library provides the `Index` GADT,
192which expresses a relationship between the source and the projected dimension.
193It is defined as follows:
194{{{
195data Index a initialDim projectedDim where
196  IndexNil   :: Index a initialDim initialDim
197  IndexAll   :: (Shape init, Shape proj) =>
198                   Index a init proj -> Index a (init :*: Int) (proj :*: Int)
199  IndexFixed :: (Shape init, Shape proj) => a ->
200                   Index a init proj -> Index a (init :*: Int)  proj
201}}}
202To refer to a specific element, the type parameter `a` is instantiated with the type `Int`, otherwise
203with the unit type:
204{{{
205type SelectIndex = Index Int
206type MapIndex    = Index ()
207}}}
208Given this definition, the type of `select` now becomes
209{{{
210select:: (U.Elt e, Shape dim, Shape dim') => Array dim e -> SelectIndex dim dim'  -> Array dim' e
211}}}
212Example:
213{{{
214arr:: Array (() :*: Int :*: Int :*: Int) Double
215
216arr' :: () :*: Int :*: Int
217arr' = select arr (IndexFixed 3 (IndexAll (IndexAll IndexNil)))
218}}}
219We could generalise this further, to extract from any array `arr` which is at least one dimensional
220the third element:
221{{{
222arr:: Shape dim => Array (dim :*: Int) Double
223
224arr' :: Array dim Double
225arr' = select arr (IndexFixed 3 IndexNil)
226}}}
227
228
229The index type is also used to express the type of generalised replicate
230{{{
231replicate:: Array dim' e -> SelectIndex dim dim'  -> Array dim e
232}}}
233which, given an array, can be used to expand it along any dimension. For example,
234{{{
235simpleReplicate:: (U.Elt e, Shape dim) => Array dim e -> Int -> Array (dim :*: Int) e
236simpleReplicate arr n =
237  replicate arr (IndexFixed n IndexNil)
238}}}
239replicates the argument array (which can of any dimensionality) `n` times and behaves
240thus similarly to list replicate, whereas
241{{{
242elementwiseReplicate:: (U.Elt e, Shape dim) =>
243  Array (dim :*: Int) e -> Int -> Array (dim :*: Int :*: Int) e
244elementwiseReplicate arr n =
245  replicate arr (IndexAll (IndexFixed n IndexNil))
246}}}
247replicates each element of an array `n` times (similarly to `map (replicate n)` on lists).
248
249
250Even though the index type serves well to express the relationship
251between the selector/multiplicator and the dimensionality of the
252argument and the result array, it is inconvenient to use, as the
253examples demonstrate. We therefore do need to add another layer to
254improve the usability of the library.
255
256Note that the library provides no way to statically check the pre- and
257postconditions on the actual size of arguments and results. This has
258to be done at run time using assertions.
259
161260
162261=== Reordering, Shifting, Tiling ===

184283}}}
185284
186 === Shape Polymorphic Computations on Arrays ===
187
188 The array operations described in this and the following subsection
189 are available on both strict and delayed arrays, and yield the same
190 result, with the exception that in case of delayed arrays, the result
191 is only calculated once its forced by calling `fromDArray` or `forceDArray`. No
192 intermediate array structures are ever created.
193
194 The library provides a range of operation where the dimensionality of
195 the result depends on the dimensionality of the argument in a
196 non-trivial manner, which we want to be reflected in the type system.
197 Examples of such functions are generalised selection, which allows for
198 extraction of subarrays of arbitrary dimension, and generalised replicate,
199 which allows replication of an array in any dimension (or dimensions).
200
201 For selection, we can informally state the relationship between dimensionality of
202 the argument, the selector, and the result as follows:
203 {{{
204 select:: Array dim e -> <select dim' of dim array> -> Array dim' e
205 }}}
206
207 To express this relationship, the library provides the index GADT,
208 which expresses a relationship between the inital and the projected
209 dimensionality. It is defined as follows:
210
211 {{{
212 data Index a initialDim projectedDim where
213   IndexNil   :: Index a () ()
214   IndexAll   :: (Shape init, Shape proj) =>
215                    Index a init proj -> Index a (init :*: Int) (proj :*: Int)
216   IndexFixed :: (Shape init, Shape proj) => a ->
217                    Index a init proj -> Index a (init :*: Int)  proj
218
219 type SelectIndex = Index Int
220 type MapIndex    = Index ()
221 }}}
222 Given this definition, the type of `select` now becomes
223 {{{
224 select:: (U.Elt e, Shape dim, Shape dim') => Array dim e -> SelectIndex dim dim'  -> Array dim' e
225 }}}
226 Example:
227 {{{
228 arr:: Array DIM3 Double
229 select arr (IndexFixed 3 (IndexAll (IndexAll IndexNil)))
230 }}}
231 The index type is also used to express the type of generalised replicate:
232 {{{
233 replicate:: Array dim' e -> SelectIndex dim dim'  -> Array dim e
234 }}}
235 Even though the index type serves well to express the relationship
236 between the selector/multiplicator and the dimensionality of the
237 argument and the result array, it is somehow inconvenient to use, as
238 the examples demonstrate. This is therefore another example where we
239 need to add another layer to improve the usability of the library.
240
241 Note that the library provides no way to statically check the pre- and
242 postconditions on the actual size of arguments and results. This has
243 to be done at run time using assertions.
244
245 == Array Operations ==
246
247 Backpermute and default backpermute are two general operations which allow
248 the programmer to express all structural operations which reorder or extract
249 elements based on their position in the argument array:
250 {{{
251 backpermute:: (U.Elt e, Shape dim, Shape dim') =>
252   Array dim e -> dim' -> (dim' -> dim) -> Array dim' e
253
254 backpermuteDft::(U.Elt e, Shape dim, Shape dim') =>
255   Array dim e -> e -> dim' -> (dim' -> Maybe dim) -> Array dim' e
256 }}}
257
258
259
260 The following operations could be (and in the sequential implementation indeed are)  expressed
261 in terms of backpermute and default backpermute. However, a programmer should aim at using more