Changes between Version 35 and Version 36 of DataParallel/Replicate


Ignore:
Timestamp:
Aug 16, 2011 1:40:55 PM (3 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Replicate

    v35 v36  
    157157In the case of `smvm`, where the first argument is produced by `replicatePA (lengthPA row) v`, we have `as_vsegs = 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. 
    158158 
     159=== Splitting and combining (for lifted conditions) === 
     160 
     161Due to lifted conditionals (or, generally, case constructs), arrays with virtual segments may be split (packed) and combined.  Arrays with virtual segments can be split (or packed) by merely packing the virtual segment descriptor.  Hence, some physical segments may not appear as virtual segments at all.  This ensures good asymptotical complexity for packing, but also means that subsequent operations need to be careful to avoid operating on physical segments that do not appear as virtual segments, as this would be wasted work. 
     162 
     163Arrays with virtual segments can not always be combined without duplicating the data corresponding to repeated segments (after all, a disjoint segment may be inserted into a sequence of repeated segments).  For simplicity, we may want to expand all repeated segments and remove all not used physical segments in `combinePA`.  (It seems that this should not lead to unexpected blow-ups as the repeated data now is part of a functions result and should be accounted for in its complexity estimate.) 
     164 
    159165=== Reduction === 
    160166 
     
    169175To 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`. 
    170176 
    171 As 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. 
    172  
    173 === Splitting and combining (for lifted conditions) === 
    174  
    175 Due to lifted conditionals (or, generally, case constructs), arrays with repeated segments may be split (packed) and combined.  Arrays with repeated segments can be split (or packed) by including a repeated segment in the result exactly if one of its repetitions is included.  This can be determined by disjunctively combining all flags for one sequence of repeated segments. 
    176  
    177 Arrays with repeated segments can not always be combined without duplicating the data corresponding to repeated segments (after all, a disjoint segment may be inserted into a sequence of repeated segments).  For simplicity, we may want to expand all repeated segments in `combinePA`.  (It seems that this should not lead to unexpected blow-ups as the repeated data now is part of a functions result and should be accounted for in its complexity estimate.) 
     177As we saw in the previous 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. 
    178178 
    179179=== Splitting and joining (for distribution across threads) ===