Changes between Version 2 and Version 3 of DataParallel/Regular


Ignore:
Timestamp:
May 13, 2009 6:43:09 AM (5 years ago)
Author:
gckeller
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Regular

    v2 v3  
    99 
    1010 
     11=== Efficiency === 
    1112 
     13When 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 
     17The 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. 
    1218 
    1319== The regular array type == 
     
    1521Regular parallel arrays are similar to arrays in SAC, with one major 
    1622difference: array operations in DPH are fully typed, and consequently, what 
    17 is called 'shape invariant programming' in SAC works differently in DPH. 
     23is 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.  
    1824 
    1925An multidimensional array is parametrised with its dimensionality and its 
     
    2430 
    2531}}} 
    26 where Shape is a type family defined on tuples of integers, including nullary 
     32where IX is the standard Haskell index class,  Shape is a type family defined on tuples of integers, including nullary 
    2733tuples - arrays of which correspond to scalar values. So, for example 
    2834{{{ 
     
    5561fromScalar::  U.Elt r => r -> Array DIM0 r 
    5662}}} 
     63and  bpermuteR, which creates a new array of new shape, using values of the argument array. 
     64{{{ 
     65bpermuteR:: Array dim e -> Shape dim' -> (Shape dim' -> Shape dim) -> Array dim' 
     66}}} 
     67For example, transposition of a two dimensional array can be defined in terms of mkArray as follows: 
     68{{{ 
     69transpose:: Array DIM2 a -> Array DIM2 a 
     70transpose arr = bpermuteR arr (n,m) (\(i,j) -> (j,i)) 
     71  where (n,m) = shape arr 
     72}}} 
     73Or cutting a 3 x 3 tile starting at indices (0,0) out of a two dimensional matrix: 
     74{{{ 
     75tile:: Array DIM2 a -> Array DIM2 a 
     76tile arr = bpermuteR arr (3,3) id 
     77}}} 
    5778 
    5879=== Manipulating array values === 
     
    7495Manipulating the shape of arrays: 
    7596{{{ 
     97-- size of both shapes have to be the same, otherwise runtime error 
    7698reshape     ::(Ix (Shape dim), Ix (Shape dim')) => 
    7799                 (Shape dim)                  -- new shape 
     
    92114which expands the array along specified axes. To encode the 
    93115relationship between the argument's dimensionality and the result's dimensionality,  
    94 we use the Index type.  
     116we use the Index type: 
    95117{{{ 
    96118(!) :: Elt e => Arr dim e -> Index dim dim' -> Arr dim' e 
     
    109131}}} 
    110132 
     133The index type is similar to generalized  selection in SaC. For example, the selection vector  
     134{{{ 
     135  (1,2,3) 
     136}}} 
     137which 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}}} 
     141Where 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}}} 
     145specifies a subvector (i.e., all the values in position (1,i,3) for all i's in the arrays range. This corresponds to 
     146{{{ 
     147IndexFixed 1 (IndexAll (IndexFixed 3 IndexNil)):: Index ((((),Int), Int),,Int) ((),Int) 
     148}}} 
    111149==== Examples ==== 
    112150 
     
    119157 
    120158-- create a two dimensional array by replicating each element n times 
     159-- 'replicateLifted' 
    121160replicateL:: Int -> Array DIM1 a -> Array DIM2 a 
    122161replicateL n arr = RArray.replicate (IndexAll (IndexFixed n IndexNil))  arr 
    123162 
    124  
     163-- 'chunkreplicate' on a two dimensional array 
     164-- 
    125165replicateC2:: Int -> Array DIM2 a -> Array DIM3 a 
    126166replicateC2 n arr = RArray.replicate       (IndexFixed n (IndexAll (IndexAll IndexNil)))  arr 
     
    131171 }}} 
    132172 
    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 dot-notation. 
     173In the actual array language (user level) the DPH should provide a general selection-like notation for index expressions. 
    135174 
     175=== Comparison with SaC === 
    136176 
     177We 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