Changes between Version 26 and Version 27 of DataParallel/Replicate

Aug 16, 2011 7:30:17 AM (6 years ago)



  • DataParallel/Replicate

    v26 v27  
    170170The 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.
     172== The bigger picture ==
     174It makes sense to see this work and the concepts behind the Repa library as part of a bigger picture.  In both cases, we want to avoid the overhead of ''index space transformations''.  In Repa, we use ''delayed'' arrays —i.e., arrays represented as functionals— to delay the execution of index transformations (as well as maps) and to fuse them into consumers.  In Repa, we do that for index transformations explicitly specified by the programmer and we rely on the programmer to be aware of situations, where delayed arrays need to be `forced` into ''manifest'' form before they are consumed by an array operation that cannot be represented in delayed form — e.g., in matrix-matrix multiplication, we need to `force` the transposed array to improve cache behaviour.
     176In DPH, we are first of all concerned about chains of index transformations that begin with a lifted replicate as these lead to an asymptotic increase of work complexity as discussed above.  However, other index transformations, such as non-lifted replicate, are of concern as well, and will need to be addressed eventually.
     178Despite the conceptual similarity, there are two big differences between the situation in Repa and DPH:
     179 1. In Repa, arbitrary user-specified index transformations are being delayed and we rely on the programmer to `force` these explicitly where necessary — i.e., a user needs to be aware of this whole mechanism.  In contrast, in DPH, we aim at eliminating the index transformations introduced by the vectoriser (of which many programmers will not be aware); hence, the elimination also needs to be without user intervention.
     180 2. In Repa, we have no segmented arrays; hence, functions are sufficient to represent delayed arrays.  In contrast, in DPH, segmented arrays are central and we need auxiliary data structures —such as virtual segment descriptors— to delay index transformations efficiently.
     182A question for the future is whether we can find a uniform framework that works for both Repa's regular arrays and DPH's nested arrays. This would provide a key to an integrated system.
    172184== Related work ==