Changes between Version 27 and Version 28 of DataParallel/Regular


Ignore:
Timestamp:
Jan 20, 2010 2:50:21 AM (6 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