Changes between Version 13 and Version 14 of DataParallel/Replicate
 Timestamp:
 Aug 7, 2011 11:49:42 AM (3 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

DataParallel/Replicate
v13 v14 8 8 smvm m v = [: sumP [: x * (v !: i)  (i,x) < row :]  row < m :] 9 9 }}} 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 (lengthrow) v`.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 `replicatePA (lengthPA row) v`. 11 11 12 12 This is clearly wasted effort and space. However, the situation is even worse in Ben's pathological example: … … 76 76 In the `smvm` example, a replicated array is consumed by lifted indexing to extract matching elements of the vector for all nonzero elements of the matrix. Using just an length array as a segment descriptor without overlapping segments, lifted indexing might be implemented as follows: 77 77 {{{ 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) 79 79 }}} 80 80 81 81 With overlapping segments, we have 82 82 {{{ 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) 84 84 }}} 85 In the case of `smvm`, where the first argument is produced by `replicateP (length row) v`, we have `as_start = replicate (lengthrow) 0` and `asdata = v`. In other words, lifted indexing draws from a single copy of `v`, which is what we wanted.85 In the case of `smvm`, where the first argument is produced by `replicatePA (lengthPA row) v`, we have `as_start = replicatePA (lengthPA row) 0` and `asdata = v`. In other words, lifted indexing draws from a single copy of `v`, which is what we wanted. 86 86 87 87 === Reduction ===