Changes between Initial Version and Version 1 of DataParallel/CodeVectorisation/LiftedCaseExample


Ignore:
Timestamp:
Mar 19, 2007 7:26:18 AM (7 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/CodeVectorisation/LiftedCaseExample

    v1 v1  
     1== Vectorisation: The lifted case example == 
     2 
     3This example is taken from http://www.cse.unsw.edu.au/~chak/papers/LCK06.html. 
     4 
     5== Flattening sums == 
     6 
     7We represent arrays of type 
     8 
     9{{{ 
     10data Either a b = Left a | Right b 
     11}}} 
     12 
     13essentially as 
     14 
     15{{{ 
     16instance (ArrayElem a, ArrayElem b) => ArrayElem (Either a b) where 
     17  type [:Either a b:] = ([:Bool:], [:a:], [:b:]) 
     18}}} 
     19 
     20For instance, `[:Left 5, Right 4, Left 2:]` will be represented by `([:True, False, True:], [:5,2:], [:4:])`. The boolean array (the ''selector'') indicates whether the corresponding element is a `Left` or a `Right` one; the actual data is stored in two separate arrays. 
     21 
     22== Case distinction (take 1) == 
     23 
     24For case distinction on `Either`, we have 
     25 
     26{{{ 
     27either :: (a -> c) -> (b -> c) -> Either a b -> c 
     28either f g (Left  x) = f x 
     29either f g (Right y) = g y 
     30}}} 
     31 
     32The interesting question, of course, is how this works in a data-parallel context, i.e., what semantics something like `mapP (either f g) xs` has. For the moment, we assume that `[:a -> b:] = [:a:] -> [:b:]`. 
     33 
     34=== Sometimes it works ... === 
     35 
     36Let us first consider 
     37 
     38{{{ 
     39inc :: Int -> Int 
     40inc n = n+1 
     41 
     42good :: Either Int Int -> Int 
     43good x = either inc id x 
     44}}} 
     45 
     46The term `mapP good [:Left 5, Right 4, Left 2:]` translates to `good^ (EitherArr [:True, False, True:] [:5,2:] [:4:])`; to see how this is evaluated, we have to derive the lifted version of `good^`. This is easy (we ignore the tupling of functions here): 
     47 
     48{{{ 
     49good^ :: [:Either Int Int:] -> [:Int:] 
     50good^ xs = either^ inc^ id^ xs 
     51}}} 
     52 
     53We need the lifted versions of `either`, `inc` and `id`. The latter is trivial: 
     54 
     55{{{ 
     56id :: a -> a 
     57id x = x 
     58 
     59id^ :: [:a:] -> [:a:] 
     60id^ xs = xs 
     61}}} 
     62 
     63We will omit the definition of `inc^` - it just increments every element in an array. The definition of `either^` is easily derived from its type: 
     64 
     65{{{ 
     66either^ :: ([:a -> c:])     -> ([:b -> c:])     -> [:Either a b:]           -> [:c:] 
     67        :: ([:a:] -> [:c:]) -> ([:b:] -> [:c:]) -> ([:Bool:], [:a:], [:b:]) -> [:c:]   -- assuming [:a -> b:] = [:a:] -> [:b:] 
     68either^ f g (bs, xs, ys) = combineP bs (f xs) (g ys) 
     69}}} 
     70 
     71Here, we apply `f` and `g` to the respective data arrays and the combine the results according to the selector. For instance, we have 
     72 
     73{{{ 
     74combineP [:True, False, True:] [:6,3:] [:4:] = [:6,4,3:] 
     75}}} 
     76 
     77and therefore 
     78 
     79{{{ 
     80  mapP good [:Left 5, Right 4, Left 2:] 
     81= good^ ([:True, False, True:], [:5,2:], [:4:]) 
     82= either^ inc^ id^ ([:True, False, True:], [:5,2:], [:4:]) 
     83= combineP [:True, False, True:] (inc^ [:5,2:]) (id^ [:4:]) 
     84= combineP [:True, False, True:] [:6,3:] [:4:] 
     85= [:6,4,3:] 
     86}}} 
     87 
     88This is precisely the expected result. 
     89 
     90=== ... but sometimes it doesn't === 
     91 
     92Now, let us consider a slightly more complex function: 
     93 
     94{{{ 
     95bad :: (Either Int Int, Int) -> Int 
     96bad x = either ((+) (snd x)) id (fst x) 
     97}}} 
     98 
     99Again, we derive the lifted version of `bad`: 
     100 
     101{{{ 
     102bad^ :: [:(Either Int Int, Int):] -> [:Int:] 
     103bad^ xs = either^ ((+^) (snd^ x)) id^ (fst^ x) 
     104}}} 
     105 
     106So, how is `mapP bad [:(Left 5, 1), (Right 4, 3), (Left 2, 7):]` evaluated? We have 
     107 
     108{{{ 
     109  mapP bad [:(Left 5, 1), (Right 4, 3), (Left 2, 7):] 
     110= bad^ [:(Left 5, 1), (Right 4, 3), (Left 2, 7):] 
     111= either^ ((+^) [:1,3,7:]) id^ [:Left 5, Right 4, Left 2:] 
     112= either^ ((+^) [:1,3,7:]) id^ ([:True,False,True:], [:5,2:], [:4:]) 
     113= combineP [:True,False,True:] ((+^) [:1,3,7:] [:5,2:]) (id^ [:4:]) 
     114}}} 
     115 
     116This program diverges when trying to evaluate `(+^) [:1,3,7:] [:5,2:]` since `(+^)` only works with arrays of the same length. Note that it is not enough to just throw away the last element of the first array like Haskell's `zipWith` would do; we really want to evaluate `(+^) [:1,7:] [:5,2:]`, i.e. throw away the 3. 
     117 
     118== Case distinction (take 2) == 
     119 
     120So why doesn't it work? Simply because our definition of `either^` is wrong. In `either^ ((+^) [:1,3,7:]) id^ ([:True,False,True:], [:5,2:], [:4:])` two function arguments each contain one computation for ''each'' element of the `Either` array; it is the job of `either^` (and of case distinction in general) to select those which really should be applied. In particular, `either^` should filter the function arguments according to the selector. Without assuming `[:a -> b:] = [:a:] -> [:b:]`, it has the type 
     121 
     122{{{ 
     123either^ :: [:a -> c:] -> [:b -> c:] -> [:Either a b:] -> [:c:] 
     124}}} 
     125 
     126The real type is actually `[:a -> c:] -> [:(b -> c) -> Either a b -> c:]` but this is not important at the moment. So, `either^` has three array parameters; and since it is a lifted function, these arrays ''must have the same length''. The correct definition is 
     127 
     128{{{ 
     129either^ fs gs (bs, xs, ys) = let fs' = packP bs fs 
     130                                 gs' = packP (not^ bs) gs 
     131                                 xs' = fs' $^ xs 
     132                                 ys' = gs' $^ ys 
     133                             in 
     134                             combineP bs xs' ys' 
     135}}} 
     136 
     137Here, `$^` denotes the elementwise application of an array of functions to an array of arguments; `packP` filters an array according to a selector. 
     138 
     139Let us see how this works out for our example. Now, the type of `(+^)` is 
     140 
     141{{{ 
     142(+^) :: [:Int:] -> [:Int -> Int:] 
     143}}} 
     144 
     145and we will denote the result of `f^ [:x1, ..., xn:]` by `[:f x1, ..., f xn:]`. Moreover, `bad^` should really be defined as 
     146 
     147{{{ 
     148bad^ :: [:(Either Int Int, Int):] -> [:Int:] 
     149bad^ xs = either^ ((+^) (snd^ x)) (replicateP (lengthP xs) id) (fst^ x) 
     150}}} 
     151 
     152Note that where we previously lifted `id` to `id^`, we now ''replicate'' it to get a function array. Then, we have 
     153 
     154{{{ 
     155  mapP bad [:(Left 5, 1), (Right 4, 3), (Left 2, 7):] 
     156= bad^ [:(Left 5, 1), (Right 4, 3), (Left 2, 7):] 
     157= either^ ((+^) [:1,3,7:]) (replicateP 3 id) [:Left 5, Right 4, Left 2:] 
     158= either^ [:(+) 1, (+) 3, (+) 7:] [:id, id, id:] ([:True,False,True:], [:5,2:], [:4:]) 
     159= let fs' = packP [:True,False,True:] [:(+) 1, (+) 3, (+) 7:] 
     160      gs' = packP [:False,True,False:] [:id,id,id:] 
     161      xs' = fs' $^ [:5,2:] 
     162      ys' = gs' $^ [:4:] 
     163  in 
     164  combineP [:True,False,True:] xs' ys' 
     165= let fs' = [:(+) 1, (+) 7:] 
     166      gs' = [:id:] 
     167      xs' = fs' $^ [:5,2:] 
     168      ys' = gs' $^ [:4:] 
     169  in 
     170  combineP [:True,False,True:] xs' ys' 
     171= let xs' = [:(+) 1, (+) 7:] $^ [:5,2:] 
     172      ys' = [:id:] $^ [:4:] 
     173  in 
     174  combineP [:True,False,True:] xs' ys' 
     175= combineP [:True,False,True:] [:6,9:] [:4:] 
     176= [:6,4,9:] 
     177}}} 
     178 
     179This gives us the correct result. 
     180 
     181== Arrays of functions == 
     182 
     183The crucial mistake in our first approach was to assume that arrays of functions can be represented by functions over arrays. This does not work because the latter do not (and cannot) support array operations. Unfortunately, it is not enough to simply forbid `[:a -> b:]` as the transformation introduces such types and sometimes needs to manipulate these arrays (as in `packP` above - `either^` is just an example of how we would translate `case` expressions). 
     184 
     185So why can't we just use boxed arrays of functions? First, this kills performance. The main reason, however, is that this would break the semantics of the data-parallel model. The flattening transformation ensures that in the parallel case, all processes essentially execute the same code at the same time. This gives us very strong semantic guarantees; in particular, we can use collective operations for communication and synchronisation. This would not be the case if we could run unlifted code in a lifted context, which is necessarily the case with boxed function arrays. Explicit closures seem to be the only solution to this problem.