Changes between Version 2 and Version 3 of DataParallel/Regular
 Timestamp:
 May 13, 2009 6:43:09 AM (8 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

DataParallel/Regular
v2 v3 9 9 10 10 11 === Efficiency === 11 12 13 When encoding multidimensional arrays using segment descriptors or by storing the dimensions separately. In the first case, this would mean significant memory overhead proportionate to the number of subarrays on each level. But even in the second case, segment descriptors have to be generated to call functions like segmented fold and scan. It is hard to predict the exact overhead for this step, as fusion might prevent the segment descriptor array to be actually built in many cases. More significant in terms of overhead is that, when using segment descriptors, parallel splits become significantly more complicated, as they require communication in the irregular case to determine the distribution, whereas the distributions of a regularly segmented array can be determined locally on each processor. 14 15 == Language Support == 16 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. 12 18 13 19 == The regular array type == … … 15 21 Regular parallel arrays are similar to arrays in SAC, with one major 16 22 difference: array operations in DPH are fully typed, and consequently, what 17 is called 'shape invariant programming' in SAC works differently in DPH. 23 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. 18 24 19 25 An multidimensional array is parametrised with its dimensionality and its … … 24 30 25 31 }}} 26 where Shape is a type family defined on tuples of integers, including nullary32 where IX is the standard Haskell index class, Shape is a type family defined on tuples of integers, including nullary 27 33 tuples  arrays of which correspond to scalar values. So, for example 28 34 {{{ … … 55 61 fromScalar:: U.Elt r => r > Array DIM0 r 56 62 }}} 63 and bpermuteR, which creates a new array of new shape, using values of the argument array. 64 {{{ 65 bpermuteR:: Array dim e > Shape dim' > (Shape dim' > Shape dim) > Array dim' 66 }}} 67 For example, transposition of a two dimensional array can be defined in terms of mkArray as follows: 68 {{{ 69 transpose:: Array DIM2 a > Array DIM2 a 70 transpose arr = bpermuteR arr (n,m) (\(i,j) > (j,i)) 71 where (n,m) = shape arr 72 }}} 73 Or cutting a 3 x 3 tile starting at indices (0,0) out of a two dimensional matrix: 74 {{{ 75 tile:: Array DIM2 a > Array DIM2 a 76 tile arr = bpermuteR arr (3,3) id 77 }}} 57 78 58 79 === Manipulating array values === … … 74 95 Manipulating the shape of arrays: 75 96 {{{ 97  size of both shapes have to be the same, otherwise runtime error 76 98 reshape ::(Ix (Shape dim), Ix (Shape dim')) => 77 99 (Shape dim)  new shape … … 92 114 which expands the array along specified axes. To encode the 93 115 relationship between the argument's dimensionality and the result's dimensionality, 94 we use the Index type .116 we use the Index type: 95 117 {{{ 96 118 (!) :: Elt e => Arr dim e > Index dim dim' > Arr dim' e … … 109 131 }}} 110 132 133 The index type is similar to generalized selection in SaC. For example, the selection vector 134 {{{ 135 (1,2,3) 136 }}} 137 which indexes the fourth element in the third subarray of the second matrix in a three dimensional array would correspond to the index value 138 {{{ 139 IndexFixed 1 (IndexFixed 2 (IndexFixed 3 IndexNil)) :: Index ((((),Int), Int),,Int) () 140 }}} 141 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 142 {{{ 143 (1,.,3) 144 }}} 145 specifies a subvector (i.e., all the values in position (1,i,3) for all i's in the arrays range. This corresponds to 146 {{{ 147 IndexFixed 1 (IndexAll (IndexFixed 3 IndexNil)):: Index ((((),Int), Int),,Int) ((),Int) 148 }}} 111 149 ==== Examples ==== 112 150 … … 119 157 120 158  create a two dimensional array by replicating each element n times 159  'replicateLifted' 121 160 replicateL:: Int > Array DIM1 a > Array DIM2 a 122 161 replicateL n arr = RArray.replicate (IndexAll (IndexFixed n IndexNil)) arr 123 162 124 163  'chunkreplicate' on a two dimensional array 164  125 165 replicateC2:: Int > Array DIM2 a > Array DIM3 a 126 166 replicateC2 n arr = RArray.replicate (IndexFixed n (IndexAll (IndexAll IndexNil))) arr … … 131 171 }}} 132 172 133 The use of the index type is not very intuitive, and it should be 134 hidden from the user, preferably by offering syntactic support similar to SACs dotnotation. 173 In the actual array language (user level) the DPH should provide a general selectionlike notation for index expressions. 135 174 175 === Comparison with SaC === 136 176 177 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. 178