Changes between Version 1 and Version 2 of DataParallel/Regular


Ignore:
Timestamp:
May 12, 2009 6:00:17 AM (5 years ago)
Author:
gckeller
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Regular

    v1 v2  
    11 
    2 == Regular, Multi-dimensional Arrays == 
     2= Regular, Multi-dimensional parallel Arrays = 
     3The nested parallel arrays of DPH could be used to model regular arrays, as we could simply either create segment information using replicate, or define regular arrays in terms of flat parallel arrays and separately stored dimensionality information, and define operations on these arrays in a library in terms of the nested operations. However, there are two main reasons why this is unsatisfactory: convenience and efficiency.  
     4 
     5=== Convenience === 
     6 
     7Languages 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 
     8large 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. 
     9 
     10 
     11 
     12 
     13== The regular array type == 
     14  
     15Regular parallel arrays are similar to arrays in SAC, with one major 
     16difference: array operations in DPH are fully typed, and consequently, what 
     17is called 'shape invariant programming' in SAC works differently in DPH. 
     18 
     19An multidimensional array is parametrised with its dimensionality and its 
     20element type: 
     21 
     22{{{ 
     23(Ix (Shape dim), Elt a)  => Array dim a  
     24 
     25}}} 
     26where Shape is a type family defined on tuples of integers, including nullary 
     27tuples - arrays of which correspond to scalar values. So, for example 
     28{{{ 
     29  Array ()      Double    -- scalar double precision floating point value 
     30  Array (3,2) Double   -- two dimensional array (matrix) of three rows, two columns 
     31}}} 
     32 
     33Internally, shapes are represented as nested pairs 
     34{{{ 
     35type family Shape dim 
     36type instance Shape () = () 
     37type instance Shape (Int) = ((),Int) 
     38type instance Shape (Int, Int) = (((),Int), Int) 
     39}}} 
     40 
     41Elements types are restricted to the element type of flat parallel 
     42arrays, that it, primitive types like integers, boolean and floating 
     43point numbers, and tuples. 
     44 
     45== Operations == 
     46 
     47=== Creating Arrays === 
     48 
     49A new arrays can be created from flat parallel arrays  
     50{{{ 
     51fromNArray:: U.Elt r => U.Array r -> Array DIM1 r 
     52}}} 
     53and from scalar values: 
     54{{{ 
     55fromScalar::  U.Elt r => r -> Array DIM0 r 
     56}}} 
     57 
     58=== Manipulating array values === 
     59 
     60All the shape invariant operations available on parallel arrays are also defined on regular arrays: 
     61{{{ 
     62map     :: (Elt a, Elt b) => (a -> b) -> Array dim a -> Array dim b 
     63zipWith :: (Elt a, Elt b, Elt c) => (a -> b -> c) -> Array dim a -> Array dim b -> Array dim c 
     64}}} 
     65Parallel array operations which can change the shape are restricted to one dimensional arrays, to make sure that the  
     66result is still a regular array.  
     67{{{ 
     68filter :: Elt a => (a -> Bool) -> Array DIM1 a -> Array DIM1 a 
     69scan        :: Elt a => ((a, a) -> a)            -- combination function 
     70              -> a                               -- default value 
     71              -> Array (dim, Int) a              -- linear array 
     72              -> (Array dim a, Array (dim, Int) a) 
     73}}} 
     74Manipulating the shape of arrays: 
     75{{{ 
     76reshape     ::(Ix (Shape dim), Ix (Shape dim')) => 
     77                 (Shape dim)                  -- new shape 
     78              -> Array dim' a                 -- array to be reshaped 
     79              -> Array dim a 
     80}}} 
     81 
     82=== Changing the dimensionality of an array === 
     83 
     84 
     85 
     86 
     87==== The index type ==== 
     88 
     89Two operations we provide change the dimensionality of an argument 
     90array, namely the generalised indexing function, which extracts 
     91subarrays from an multidimensional array, and generalised replicate, 
     92which expands the array along specified axes. To encode the 
     93relationship between the argument's dimensionality and the result's dimensionality,  
     94we use the Index type.  
     95{{{ 
     96(!) :: Elt e => Arr dim e -> Index dim dim' -> Arr dim' e 
     97 
     98replicate   :: Index dim' dim                     -- ^specifies new dimensions 
     99              -> Array dim a                      -- ^data to be replicated 
     100              -> Array dim' a 
     101 
     102}}} 
     103where Index is defined as 
     104{{{ 
     105data Index initialDim projectedDim where 
     106  IndexNil   :: Index () () 
     107  IndexAll   :: Index init proj -> Index (init, Int) (proj, Int) 
     108  IndexFixed :: Int -> Index init proj -> Index (init, Int)  proj 
     109}}} 
     110 
     111==== Examples ==== 
     112 
     113To demonstrate the use of the Index type, consider the following replicates expressed in terms of generalised replicate: 
     114{{{ 
     115-- 'chunk replicate' - create a two dimensional array by replicating the one dimensional  
     116-- argument array n times 
     117replicateC:: Int -> Array DIM1 a -> Array DIM2 a 
     118replicateC n arr = RArray.replicate       (IndexFixed n (IndexAll IndexNil))  arr 
     119 
     120-- create a two dimensional array by replicating each element n times 
     121replicateL:: Int -> Array DIM1 a -> Array DIM2 a 
     122replicateL n arr = RArray.replicate (IndexAll (IndexFixed n IndexNil))  arr 
     123 
     124 
     125replicateC2:: Int -> Array DIM2 a -> Array DIM3 a 
     126replicateC2 n arr = RArray.replicate       (IndexFixed n (IndexAll (IndexAll IndexNil)))  arr 
     127  
     128 
     129replicateLL:: Int -> Array DIM2 a -> Array DIM3 a 
     130replicateLL n arr = RArray.replicate (IndexAll (IndexAll (IndexFixed n IndexNil)))  arr 
     131 }}} 
     132 
     133The use of the index type is not very intuitive, and it should be 
     134hidden from the user, preferably by offering syntactic support similar to SACs dot-notation. 
     135 
     136