Changes between Version 34 and Version 35 of DataParallel/Replicate


Ignore:
Timestamp:
Aug 16, 2011 1:31:02 PM (4 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Replicate

    v34 v35  
    159159=== Reduction ===
    160160
    161  TODO: rl's example
     161We need to be careful when reducing an array with virtual segments, as we want the work complexity to be in proportion of the physical and not in proportion of the virtual segments.  Consider
    162162{{{
    163163f xs is = mapP f is
     
    165165   f i = sumP xs + i
    166166}}}
    167 IDEA: Work on the data array of the segmented array with repeated segments (but without repeated data), then copy the segment results according to the repetition information.  This avoids reducing the same data multiple times.  We do something similar for scans, but don't dopy the results, but keep them in a segmented array with the same '''repeated''' segment information.
     167As `xs` is free in `f` it will be in the environment of the array closure constructed by the vectorised code.  Hence, given the implementation of `mapP` discussed earlier, `xs` will be replicated `length is` times.  However, we want to work complexity of `sumP xs` be in proportion of `length xs` and not of `length xs * length is`.
     168
     169To this end, `sumP^` performs a reduction on the physical segments only.  Afterwards, the per-segment results are distributed over a vector of the length of the `vsegs` descriptor using `bpermutePA`.
     170
     171As we will see in the next subsection, some physical segments may not appear as virtual segments at all (if a replicated array shrunk by applying a pack operation).  Hence, we need to be careful that `sumP^` only reduces those physical segments of the array that are used by one or more virtual segments.
    168172
    169173=== Splitting and combining (for lifted conditions) ===