Changes between Version 1 and Version 2 of DataParallel/Regular


Ignore:
Timestamp:
May 12, 2009 6:00:17 AM (6 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