Changes between Version 1 and Version 2 of DataParallel/Desugaring


Ignore:
Timestamp:
Apr 1, 2007 11:34:38 AM (8 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