Changes between Version 29 and Version 30 of DataParallel/Replicate


Ignore:
Timestamp:
Aug 16, 2011 8:08:09 AM (4 years ago)
Author:
chak
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Replicate

    v29 v30  
    3131Replication 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.
    3232
    33 == Fixing the problem: Plan A (Repeated Segments) ==
    34 
    35 Generally, 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.  (Independently of our current plans, some cases of replicated scalars are eliminated by fusion.)
     33== Our goal ==
     34
     35Generally, 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 current practical problems are coming from.  (Independently of our current plans, some cases of replicated scalars are eliminated by fusion.)
    3636
    3737To clarify the scope of the present work:
     
    4747NB: We will have to revisit replication of scalar structures as such scalar structures may be large trees.
    4848
     49== Where does the problematic replication originate? ==
     50
     51The applications of `replicatePA` and `expandPA` that introduce the problematic replication of arrays are in the definition of `mapP`, specifically `replicatePA` is used in `mapP_S` and `expandPA` in `mapP_L` (see Page 403 of HtM):
     52{{{
     53mapP_S :: (a :-> b) -> PA a :-> PA b
     54mapP_S (Clo env _ fl) xss
     55  = fl (replicatePA (lengthPA xss) env) xss
     56
     57mapP_L :: PA (a :-> b) -> PA (PA a) -> PA (PA b)
     58mapP_L (AClo env _ fl) xss
     59  = unconcatPA xss (fl (expandPA xss env) (concatPA xss))
     60}}}
     61In both cases, we replicate the environment of a closure before we apply the lifted version of the function represented by the closure.  This is important as it guarantees that the consumer of these occurrences of `replicatePA` and `expandPA` process (topmost) segment structure in a homomorphic manner (after all, we are implementing a `map` function here)!
     62
     63Our basic plan to avoid array duplication is to change `replicatePA` and `expandPA` such that they 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.  As we will see, that also leads to the requirement that index transformations on replicated arrays, such as `packP`, need to preserve the compact encoding.
     64
     65== Fixing the problem: avoid to repeat segments ==
     66
    4967=== Repeated segments ===
    5068
     
    154172
    155173TODO: What if we have segment descriptors on top of one with repeated segments?
    156 
    157 == Fixing the problem: Plan B (Lifted Application) ==
    158 
    159 The 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):
    160 {{{
    161 mapP_S :: (a :-> b) -> PA a :-> PA b
    162 mapP_S (Clo env _ fl) xss
    163   = fl (replicatePA (lengthPA xss) env) xss
    164 
    165 mapP_L :: PA (a :-> b) -> PA (PA a) -> PA (PA b)
    166 mapP_L (AClo env _ fl) xss
    167   = unconcatPA xss (fl (expandPA xss env) (concatPA xss))
    168 }}}
    169 In both cases, we replicate the environment of a closure before we apply the lifted version of the function represented by the closure.  This is important as it guarantees that the consumer of these occurrences of `replicatePA` and `expandPA` process (topmost) segment structure in a homomorphic manner (after all, we are implementing a `map` function here)!
    170 
    171 The 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.
    172174
    173175== The bigger picture ==