Changes between Version 13 and Version 14 of DataParallel/Replicate


Ignore:
Timestamp:
Aug 7, 2011 11:49:42 AM (3 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 ===