Changes between Version 13 and Version 14 of DataParallel/Replicate


Ignore:
Timestamp:
Aug 7, 2011 11:49:42 AM (4 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Replicate

    v13 v14  
    88smvm m v = [: sumP [: x * (v !: i) | (i,x) <- row :] | row <- m :]
    99}}}
    10 Here the variable 'v' is constant in the array comprehensions and will be replicated while lifting the expression `v !: i`.   In other words, for every single element in a `row`, lifting implies the allocation of a separate copy of of the entire array `v` — and this only to perform a single indexing operation on that copy of `v`.  More precisely, in the lifted code, lifted indexing (which we usually denote by `(!:^)` is applied to a nested array consisting of multiple copies of `v`; i.e., it is applied to the result of `replicateP (length row) v`. 
     10Here the variable 'v' is constant in the array comprehensions and will be replicated while lifting the expression `v !: i`.   In other words, for every single element in a `row`, lifting implies the allocation of a separate copy of of the entire array `v` — and this only to perform a single indexing operation on that copy of `v`.  More precisely, in the lifted code, lifted indexing (which we usually denote by `(!:^)` is applied to a nested array consisting of multiple copies of `v`; i.e., it is applied to the result of `replicatePA (lengthPA row) v`. 
    1111
    1212This is clearly wasted effort and space.  However, the situation is even worse in Ben's pathological example:
     
    7676In the `smvm` example, a replicated array is consumed by lifted indexing to extract matching elements of the vector for all non-zero elements of the matrix.  Using just an length array as a segment descriptor without overlapping segments, lifted indexing might be implemented as follows:
    7777{{{
    78 (as_len, as_data) !:^ is = bpermute as_data ((prescan (+) 0 as_len) +^ is)
     78(as_len, as_data) !:^ is = bpermutePA as_data ((prescanPA (+) 0 as_len) +^ is)
    7979}}}
    8080
    8181With overlapping segments, we have
    8282{{{
    83 (as_start, as_len, as_data) !:^ is = bpermute as_data (as_start +^ is)
     83(as_start, as_len, as_data) !:^ is = bpermutePA as_data (as_start +^ is)
    8484}}}
    85 In the case of `smvm`, where the first argument is produced by `replicateP (length row) v`, we have `as_start = replicate (length row) 0` and `as-data = v`.  In other words, lifted indexing draws from a single copy of `v`, which is what we wanted.
     85In the case of `smvm`, where the first argument is produced by `replicatePA (lengthPA row) v`, we have `as_start = replicatePA (lengthPA row) 0` and `as-data = v`.  In other words, lifted indexing draws from a single copy of `v`, which is what we wanted.
    8686
    8787=== Reduction ===