Changes between Version 1 and Version 2 of DataParallel/Replicate

Jun 15, 2011 2:21:56 PM (6 years ago)



  • DataParallel/Replicate

    v1 v2  
    11= Preventing space blow-up due to replicate =
     3== The problem ==
    35The vectorisation transformation lifts scalar computations into vector space.  In the course of this lifting, scalar constants are duplicated to fill an array, using the function 'replicateP'.  Array computations are lifted in a similar manner, which leads to array constants being replicated to form arrays of arrays, which are represented as a segmented arrays.  A simple example is our  'smvm' example code:
     7smvm :: [:[: (Int, Double) :]:] -> [:Double:] -> [:Double:]
     8smvm m v = [: sumP [: x * (v !: i) | (i,x) <- row :] | row <- m :]
     10Here the variable 'v' is constant in the array comprehensions and will be replicated while lifting the expression `v !: i`.   In other words, for every single element in a `row`, lifting implies the allocation of a separate copy of of the entire array `v` — and this only to perform a single indexing operation on that copy of `v`.  More precisely, in the lifted code, lifted indexing (which we usually denote by `(!^)` is applied to a nested array consisting of multiple copies of `v`; i.e., it is applied to the result of `replicateP (length row) v`. 
     12This is clearly wasted effort and space.  However, the situation is even worse in Ben's pathological example:
     14treeLookup :: [:Int:] -> [:Int:] -> [:Int:]
     15treeLookup table xx
     16  | lengthP xx == 1
     17  = [: table !: (xx !: 0) :]
     18  | otherwise
     19  = let len     = lengthP xx
     20          half    = len `div` 2
     21          s1      = sliceP 0    half xx
     22          s2      = sliceP half half  xx           
     23      in concatP (mapP (treeLookup table) [: s1, s2 :])
     25Here `table` is constant in `mapP (treeLookup table) [: s1, s2 :]`; hence, the entire `table` gets duplicated on each level of the recursion, leading to space consumption that is exponential in the depth of the recursion.