Added regular fold, sum (parallel and sequential)
authorkeller@cse.unsw.edu.au <unknown>
Tue, 21 Apr 2009 01:02:02 +0000 (01:02 +0000)
committerkeller@cse.unsw.edu.au <unknown>
Tue, 21 Apr 2009 01:02:02 +0000 (01:02 +0000)
12 files changed:
dph-base/Data/Array/Parallel/Stream/Segmented.hs
dph-prim-interface/Data/Array/Parallel/Unlifted.hs
dph-prim-interface/interface/DPH_Header.h
dph-prim-interface/interface/DPH_Interface.h
dph-prim-par/Data/Array/Parallel/Unlifted.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Parallel.hs
dph-prim-par/Data/Array/Parallel/Unlifted/Parallel/Segmented.hs
dph-prim-seq/Data/Array/Parallel/Unlifted.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/Segmented.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/Segmented/Combinators.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/Segmented/Sums.hs

index ca9bd2d..99c21ef 100644 (file)
@@ -19,6 +19,7 @@
 module Data.Array.Parallel.Stream.Segmented (
   SStream(..),
   segmentS, foldValuesSS, foldValuesSS', fold1ValuesSS,
+  foldValuesR,
   combineSS, (^+++^)
 ) where
 
@@ -180,10 +181,10 @@ SStream (Stream nexts1 ss1 ns1) (Stream nextv1 sv1 nv1)
                                          :*: ss1 :*: sv1 :*: ss2 :*: sv2')
 
 
-foldValuesR :: (a -> b -> a) -> a -> Int -> Stream b -> Stream a
+foldValuesR :: (a -> b -> a) -> a -> Int -> Int -> Stream b -> Stream a
 {-# INLINE_STREAM foldValuesR #-}
-foldValuesR f z segSize (Stream nextv vs nv) =
-  Stream next (segSize :*: Box z :*: vs) ns
+foldValuesR f z noOfSegs segSize (Stream nextv vs nv) =
+  Stream next (segSize :*: Box z :*: vs) noOfSegs
   where
     {-# INLINE next #-}  
     next (0 :*: Box x :*: vs) =
index e382d32..327d762 100644 (file)
@@ -113,6 +113,10 @@ fold_s f z = map (fold f z)
 fold_s' f z segd xs = map (fold f z) (segd >: xs)
 fold1_s f = map (fold1 f)
 sum_s = map sum
+sum_r _ segSize xs = sum_s $ seg xs
+  where
+    seg [] = [] 
+    seg xs = (P.take segSize xs) : (seg (P.drop segSize xs))
 
 enumFromThenTo_s = zipWith3 enumFromThenTo
 enumFromStepLen i k 0 = []
index 895f434..528cfd8 100644 (file)
@@ -20,7 +20,7 @@ module Data.Array.Parallel.Unlifted (
   fst_s, snd_s, zip_s,
   bpermute_s', map_s, filter_s, pack_c, combine_c, zipWith_s,
   indexed_s,
-  fold_s, fold_s', fold1_s, sum_s,
+  fold_s, fold_s', fold1_s, sum_s, sum_r,
   enumFromThenTo_s,
   lengthsSegd, lengthsToSegd, toSegd, fromSegd,
 
index e7fbc11..d531b50 100644 (file)
@@ -189,6 +189,8 @@ fold1_s :: Elt a => (a -> a -> a) -> SArray a -> Array a
 sum_s :: (Num a, Elt a) => SArray a -> Array a
 {-# INLINE_BACKEND sum_s #-}
 
+sum_r :: (Num a, Elt a) => Int -> Int ->Array a -> Array a
+{-# INLINE_BACKEND sum_r #-}
 
 enumFromThenTo_s :: Array Int -> Array Int -> Array Int -> SArray Int
 {-# INLINE_BACKEND enumFromThenTo_s #-}
index e59114f..2a5cd94 100644 (file)
@@ -71,6 +71,7 @@ fold_s = foldSUP
 fold_s' = foldSUP'
 fold1_s = fold1SU
 sum_s = sumSUP
+sum_r = sumRUP
 enumFromThenTo_s = enumFromThenToSUP
 indexed_s = indexedSUP
 lengthsSegd = lengthsUSegd
index 83fb004..3cc07a7 100644 (file)
@@ -25,6 +25,7 @@ module Data.Array.Parallel.Unlifted.Parallel (
   mapSUP, filterSUP, packCUP, combineCUP, zipWithSUP, foldSUP, foldSUP', sumSUP,
   bpermuteSUP', enumFromThenToSUP, replicateSUP, repeatCUP, indexedSUP, jsTest,
 
+  sumRUP,
   indexedUP, replicateUP, replicateEachUP, replicateEachUnbalancedUP, repeatUP,
 
   dropUP
index 3f2e1c9..528d688 100644 (file)
@@ -20,6 +20,7 @@
 module Data.Array.Parallel.Unlifted.Parallel.Segmented (
   mapSUP, filterSUP, packCUP, combineCUP,
   zipWithSUP, foldlSUP, foldlSUP', foldSUP, foldSUP', sumSUP, bpermuteSUP',
+  sumRUP, foldRUP,
   enumFromThenToSUP, replicateSUP, replicateCUP, repeatCUP, indexedSUP, jsTest
 ) where
 
@@ -167,3 +168,20 @@ indexedSUP xss = segdSU xss >: zipU is xs
        . zipU (replicateU (lengthSU xss) 0)
        . mapUP (subtract 1)
        $ lengthsSU xss
+
+
+sumRUP :: (Num e, UA e) => Int ->  Int -> UArr e -> UArr e
+{-# INLINE sumRUP #-}
+sumRUP = foldRUP (+) 0
+
+
+foldRUP :: (UA a, UA b) => (b -> a -> b) -> b -> Int -> Int -> UArr a -> UArr b
+{-# INLINE foldRUP #-}
+foldRUP f z  noOfSegs segSize xs = 
+   joinD theGang unbalanced
+    (zipWithD theGang 
+              (\noS -> \xss -> foldlRU f z noS segSize xss)
+      (splitLenD theGang noOfSegs)
+      (splitAsD theGang 
+                (mapD theGang (*segSize) (splitLenD theGang noOfSegs))
+                xs))
\ No newline at end of file
index 3b26aa0..0f3137d 100644 (file)
@@ -69,6 +69,7 @@ fold_s = foldSU
 fold_s' = foldSU'
 fold1_s = fold1SU
 sum_s = sumSU
+sum_r = sumRU
 enumFromThenTo_s = enumFromThenToSU
 indexed_s = indexedSU
 lengthsSegd = lengthsUSegd
index fb44c6a..e8c84a6 100644 (file)
@@ -115,11 +115,17 @@ module Data.Array.Parallel.Unlifted.Sequential (
   fold1SU,
   {-scanSU, scan1SU,-}
 
+  -- * Higher-order operations (regular)
+  foldlRU,
+
   -- * Logical operations (segmented)
   andSU, orSU,
 
   -- * Arithmetic operations (segmented)
   sumSU, productSU, maximumSU, minimumSU,
+  -- * Arithmetic operations (regular segmented)
+  sumRU, 
 
   -- * Enumerations (segmented)
   enumFromToSU, enumFromThenToSU,
index 107f6c5..618c616 100644 (file)
@@ -52,6 +52,8 @@ module Data.Array.Parallel.Unlifted.Sequential.Segmented (
   fold1SU,
   {-scanSU, scan1SU,-}
 
+  foldlRU,
+
   -- filter and combines
   filterSU, packCU, 
 
@@ -61,7 +63,7 @@ module Data.Array.Parallel.Unlifted.Sequential.Segmented (
 
   -- * Arithmetic operations
   sumSU, productSU, maximumSU, minimumSU,
-
+  sumRU,
   -- * Enumerations
   enumFromToSU, enumFromThenToSU,
 
index cd1c6dd..84c3795 100644 (file)
@@ -23,6 +23,7 @@
 module Data.Array.Parallel.Unlifted.Sequential.Segmented.Combinators (
   mapSU, zipWithSU,
   foldlSU, foldlSU', foldSU, foldSU', foldl1SU, fold1SU, {-scanSU,-} {-scan1SU,-}
+  foldlRU,
   combineSU, combineCU,
   filterSU, packCU
 ) where
@@ -125,3 +126,9 @@ packCU flags xssArr = segmentArrU newLengths flatData
     newLengths = packU (lengthsSU xssArr) flags    
 
 
+-- | Regular arrar reduction 
+--
+
+foldlRU :: (UA a, UA b) => (b -> a -> b) -> b -> Int -> Int -> UArr a -> UArr b
+{-# INLINE_U foldlRU #-}
+foldlRU f z noOfSegs segSize = unstreamU . foldValuesR f z noOfSegs segSize . streamU
index 9fefbb1..b1a05b8 100644 (file)
@@ -17,7 +17,8 @@
 --
 
 module Data.Array.Parallel.Unlifted.Sequential.Segmented.Sums (
-  andSU, orSU, sumSU, productSU, maximumSU, minimumSU
+  andSU, orSU, sumSU, productSU, maximumSU, minimumSU,
+  sumRU
 ) where
 
 import Data.Array.Parallel.Unlifted.Sequential.Flat (
@@ -25,7 +26,7 @@ import Data.Array.Parallel.Unlifted.Sequential.Flat (
 import Data.Array.Parallel.Unlifted.Sequential.Segmented.SUArr (
   SUArr)
 import Data.Array.Parallel.Unlifted.Sequential.Segmented.Combinators (
-  foldSU, fold1SU)
+  foldSU, fold1SU, foldlRU)
 
 -- |
 andSU :: SUArr Bool -> UArr Bool
@@ -59,3 +60,9 @@ minimumSU :: (Ord e, UA e) => SUArr e -> UArr e
 {-# INLINE minimumSU #-}
 minimumSU = fold1SU min
 
+
+-- |Compute the segmented sum of an array of numerals
+--
+sumRU :: (Num e, UA e) => Int -> Int ->UArr e -> UArr e
+{-# INLINE sumRU #-}
+sumRU = foldlRU (+) 0