Changes between Version 27 and Version 28 of DataParallel/Regular


Ignore:
Timestamp:
Jan 20, 2010 2:50:21 AM (5 years ago)
Author:
gckeller
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/Regular

    v27 v28  
    344344  DArray (() :*: Int :*: Int)  Double -> DArray (() :*: Int :*: Int)  Double -> DArray (() :*: Int :*: Int)  Double   
    345345mmMult1 arr1@(DArray (() :*: m1 :*: n1) _) arr2@(DArray (() :*: m2 :*: n2) _) =  
    346   mapFold (+) 0 arrDP 
     346  fold (+) 0 arrDP 
    347347  where  
    348348    arrDP = DArray (():*: m1 :*: n2 :*:n1)  
     
    352352sums and rows, and in the second step, we collapse each of the rows to it's sum, to obtain the two dimensional 
    353353result matrix. It is important to note that the elements of `arrDP` are never all in memory (otherwise, the memory 
    354 consumption would be cubic), but each value is consumed immediately by `mapFold`.  
     354consumption would be cubic), but each value is consumed immediately by `mapfold`.  
    355355 
    356356This implementation suffers from the same problem a corresponding C implementation would - since we access one 
     
    361361  DArray (() :*: Int :*: Int)  Double -> DArray (() :*: Int :*: Int)  Double -> DArray (() :*: Int :*: Int)  Double   
    362362mmMult1 arr1@(DArray (() :*: m1 :*: n1) _) arr2@(DArray (() :*: m2 :*: n2) _) =  
    363   mapFold (+) 0 arrDP 
     363  fold (+) 0 arrDP 
    364364  where  
    365365    arr2T = forceDArray $ transpose arr2 
    366366    arrDP = DArray (():*: m1 :*: n2 :*:n1)  
    367367       (\(() :*: i :*: j :*: k) -> (index arr1 (() :*: i :*: k)) * (index arr2T (() :*: j:*: k))) 
     368 
     369transpose:: DArray (() :*: Int :*: Int)  Double -> DArray (() :*: Int :*: Int)  Double   
     370transpose (DArray (() :*: m :*: n) f) = 
     371  DArray (() :*: n :*: m) (\(() :*: i :*: j) -> f (() :*: j :*: i)) 
    368372}}} 
    369373However, we do need to force the actual creation of the transposed array, otherwise, the change would have no effect at all. We therefore  
    370374use `forceDArray`, which converts it into an array whose array function is a simple indexing operation (see description of `forceDArray` above). This means that the second version requires more memory, but this is offset by improving the locality for each of the multiplications.  
     375 
     376As it is, `mmMult` can only take two-dimensional arrays as arguments, and is not mappable. If we look at the implementation closely, we can see that the restriction to two-dimensional arrays is unnecessary. All we have to do to generalise it is to adjust the type signatures and replace `()` with an arbitrary shape variable: 
     377{{{ 
     378mmMult1:: Shape dim =>  
     379  DArray (dim :*: Int :*: Int)  Double -> DArray (dim :*: Int :*: Int)  Double -> DArray (dim :*: Int :*: Int)  Double   
     380mmMult1 arr1@(DArray (sh :*: m1 :*: n1) _) arr2@(DArray (sh' :*: m2 :*: n2) _) =  
     381  fold (+) 0 arrDP 
     382  where  
     383    arr2T = forceDArray $ transpose arr2 
     384    arrDP = DArray (sh:*: m1 :*: n2 :*:n1)  
     385       (\(sh :*: i :*: j :*: k) -> (index arr1 (sh :*: i :*: k)) * (index arr2T (sh :*: j:*: k))) 
     386 
     387transpose:: Shape dim => 
     388   DArray (dim :*: Int :*: Int)  Double -> DArray (dim :*: Int :*: Int)  Double   
     389transpose (DArray (sh:*: m :*: n) f) = 
     390  DArray (sh :*: n :*: m) (\(sh :*: i :*: j) -> f (sh :*: j :*: i)) 
     391}}} 
    371392 
    372393