Changes between Version 1 and Version 2 of DataParallel/Desugaring


Ignore:
Timestamp:
Apr 1, 2007 11:34:38 AM (7 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Desugaring

    v1 v2  
    33Wadler's desugaring for list comprehensions is not suitable for arrays, as we need to use collective operations to get good parallel code.  The build/foldr desugaring, although using collective operations, isn't a good match for how the array operations are implemented.  In fact, the ''naive'' desugaring from the H98 report is a much better fit: 
    44{{{ 
    5 [: e | :]            = [:e:] 
    6 [: e | b, qs :]      = if b then [: e | qs :] else [::] 
    7 [: e | p <- a, qs :] = let ok p = [: e | qs :] 
    8                            ok _ = [::] 
    9                      in concatMap ok a 
    10 [: e | let ds, qs :] = let ds in [: e | qs :] 
    11 [: e | qs | qss   :] =  
    12   [: e | (XS, XSS) <- zip [: XS | qs :] [: XSS | qss :] :] 
    13   where XS & XSS are the bound variables in qs & qss 
     5(1) [: e | :]            = [:e:] 
     6(2) [: e | b, qs :]      = if b then [: e | qs :] else [::] 
     7(3) [: e | p <- a, qs :] = let ok p = [: e | qs :] 
     8                               ok _ = [::] 
     9                           in concatMapP ok a 
     10(4) [: e | let ds, qs :] = let ds in [: e | qs :] 
     11(5) [: e | qs | qss   :] =  
     12(6) [: e | (XS, XSS) <- zip [: XS | qs :] [: XSS | qss :] :] 
     13    where XS & XSS are the bound variables in qs & qss 
    1414}}} 
     15In particular, `concatMapP f a` essentially implies to apply the lifted version of `f` directly to `a` and then the concat strips of one level of segment descriptors; i.e., both the `concatP` and the `mapP` vanish due to vectorisation. 
     16 
     17== Problem with the naive rules == 
     18 
     19Nevertheless, these rules are not entirely satisfactory.  For example, `[:e | x <- a, b:]` turns into 
     20{{{ 
     21concatMap (\x -> if b then [:e:] else [::]) a 
     22}}} 
     23which is a fairly complicated way to perform  
     24{{{ 
     25mapP (\x -> e) . filterP (\x -> b) $ a 
     26}}} 
     27even when taking vectorisation into account.  Under vectorisation, the conditional implies `filterP (\x -> b)`, but adds an expensive, and here useless, merge operation.  Maybe these overheads can be optimised away.  However, for the moment, we use a desugaring that is based on the above rules, but generates code that should be better suited to array processing. 
     28 
     29== Modified rules == 
     30