Changes between Version 15 and Version 16 of DataParallel/Replicate


Ignore:
Timestamp:
Aug 7, 2011 12:02:11 PM (3 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Replicate

    v15 v16  
    3434Generally, we don't want to copy replicated data — it's a waste of space!  We definitely don't want to do it for large data structures, and in particular, we don't want to do it for arrays.  After all, that can change the asymptotic work complexity of a program.  To keep it simple, we are for the moment focusing on avoiding replicating arrays, as this is were our practical problems are coming from at the moment.  (Some cases of replicated scalars are also eliminated by fusion.) 
    3535 
     36NB: We will have to revisit replication of scalar structures as such scalar structures may be large trees. 
     37 
    3638=== Repeated segments === 
    3739 
    3840A replicated array results is always represented by a segmented array; more precisely, by a segmented array where a contiguous sequence of segments contains the same data.  For example, we have 
    3941{{{ 
    40 replicateP 3 [:1, 2, 3:] = [:[:1, 2, 3:], [:1, 2, 3:], [:1, 2, 3:]:] 
     42replicatePA 3 [:1, 2, 3:] = [:[:1, 2, 3:], [:1, 2, 3:], [:1, 2, 3:]:] 
    4143  where 
    4244    [:[:1, 2, 3:], [:1, 2, 3:], [:1, 2, 3:]:] = ([:3, 3, 3:], [:1, 2, 3, 1, 2, 3, 1, 2, 3:]) 
     
    4446and 
    4547{{{ 
    46 replicateP^ [:2, 3:] [:[:1, 2:], [:3:]:] = [:[:1, 2:], [:1, 2:], [:3:], [:3:], [:3:]:] 
     48expandPA [:2, 3:] [:[:1, 2:], [:3:]:] = [:[:1, 2:], [:1, 2:], [:3:], [:3:], [:3:]:] 
    4749  where 
    4850    [:[:1, 2:], [:1, 2:], [:3:], [:3:], [:3:]:] = ([:2, 2, 1, 1, 1:], [:1, 2, 1, 2, 3, 3, 3:]) 
    4951}}} 
     52NB: `expandPA` is lifted replication; `expandPA` is the name we used in HtM. 
    5053 
    5154=== Collapse repeated segments ===