Changes between Version 16 and Version 17 of DataParallel/Replicate


Ignore:
Timestamp:
Aug 7, 2011 12:29:29 PM (4 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Replicate

    v16 v17  
    3030Replication of scalars and arrays is always a waste of time and space.  However, it is particularly problematic if the replicated structure is consumed by an indexing operation as it can change the asymptotic work complexity of the vectorised program.  This holds not only for indexing, but for any operation that consumes only a small part of its input array(s).  In other words, if a replicated structure is consumed in its entirety (for example by a fold), the asymptotic work complexity of replication matches that of consuming the structure.  For operations that only consume a small part of their input, that is not the case.  Hence, lifting, which introduces the replication, does increase asymptotic work.
    3131
    32 == A plan to fix the problem ==
     32== Fixing the problem: Plan A (Repeated Segments) ==
    3333
    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.)
     
    9696TODO: What if we have segment descriptors on top of one with repeated segments?
    9797
     98== Fixing the problem: Plan B (Lifted Application) ==
     99
     100The applications of `replicatePA` and `expandPA` that introduce segmented arrays with repeated segments in Plan A are in the definition of `mapP`, specifically `replicatePA` is used in `mapP_S` and `expandPA` in `mapP_L` (see Page 403 of HtM):
     101{{{
     102mapP_S :: (a :-> b) -> PA a :-> PA b
     103mapP_S (Clo env _ fl) xss
     104  = fl (replicatePA (lengthPA xss) env) xss
     105
     106mapP_L :: PA (a :-> b) -> PA (PA a) -> PA (PA b)
     107mapP_L (AClo env _ fl) xss
     108  = unconcatPA xss (fl (expandPA xss env) (concatPA xss))
     109}}}
     110In both cases, we replicate the environment of a closure before we apply the lifted version of the function represented by the closure.
     111
     112The idea behind Plan A is that `replicatePA` and `expandPA` produce a segmented array that encodes the replication without unnecessarily copying data and that the consumer —the lifted function `fl`— processes segmented arrays with encoded replication in a special manner.
     113
    98114== Related work ==
    99115