Changes between Version 2 and Version 3 of DataParallel/Desugaring


Ignore:
Timestamp:
Apr 1, 2007 12:03:02 PM (7 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Desugaring

    v2 v3  
    1010(4) [: e | let ds, qs :] = let ds in [: e | qs :] 
    1111(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 
     12      [: e | (XS, XSS) <- zip [: XS | qs :] [: XSS | qss :] :] 
     13      where XS & XSS are the bound variables in qs & qss 
    1414}}} 
    1515In 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. 
     
    2929== Modified rules == 
    3030 
     31The idea is to flatten out the processing of comprehensions to some degree by defining a transformation function `<< . >>` that gets two arguments: a pattern `pa` and a desugared expression `ea`, where we are guaranteed that `ea` is array valued and all its elements match `pa`.  The semantics of the transformation function is given by 
     32{{{ 
     33<<[: e | qs :]>> pa ea = [: e | pa <- ea, qs :] 
     34                       = concatMap (\pa -> [: e | qs :]) ea 
     35}}} 
     36We have the second line by applying Rule (3). 
     37 
     38Using this definition of `<< . >>`, we can derive a new set of desugaring rules.  The derivation proceeds by unfold/fold transformations and some properties of the involved combinators.  The resulting rules are the following: 
     39{{{ 
     40(1') <<[: e |            :]>> pa ea = mapP (\pa -> e) ea 
     41(2') <<[: e | b, qs      :]>> pa ea =  
     42  <<[: e | qs :]>> pa (filterP (\pa -> b) ea) 
     43(3') <<[: e | p <- a, qs :]>> pa ea = 
     44  let ok p = True 
     45      ok p = False 
     46  in 
     47  <<[: q | qs :]>> (pa, p) (crossMapP ea (\pa -> filterP ok a)) 
     48(4') <<[: e | let ds, qs :]>> pa ea = 
     49  <<[: e | qs :]>> (pa, XS) (mapP (\v@pa -> let ds in (v, XS)) ea) 
     50  where XS are the variables bound by ds 
     51(5') <<[: e | qs | qss   :]>> pa ea = 
     52  <<[: e | qss :]>> (pa, XS) (zipP ea [: XS | qs :]) 
     53  where XS are the variables bound by qs 
     54}}} 
     55The typical array processing comprehensions containing only generators, guards, and parallel comprehensions (but not cross-products and lets) are translated into a straight combination of `mapP`, `filterP`, and `zipP` by these rules, which is exactly what we want.