Add interleave{U|UP}
authorRoman Leshchinskiy <rl@cse.unsw.edu.au>
Fri, 4 Jun 2010 00:46:47 +0000 (00:46 +0000)
committerRoman Leshchinskiy <rl@cse.unsw.edu.au>
Fri, 4 Jun 2010 00:46:47 +0000 (00:46 +0000)
12 files changed:
dph-base/Data/Array/Parallel/Stream/Flat.hs
dph-base/Data/Array/Parallel/Stream/Flat/Basics.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/Basics.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/Flat.hs
dph-prim-seq/Data/Array/Parallel/Unlifted/Sequential/Flat/Basics.hs

index 626a173..426c280 100644 (file)
@@ -16,7 +16,7 @@ module Data.Array.Parallel.Stream.Flat (
   Step(..), Stream(..),
 
   emptyS, singletonS, consS, replicateS, replicateEachS, replicateEachRS, (+++),
-  indexedS, tailS,
+  indexedS, interleaveS, tailS,
   enumFromToS, enumFromThenToS, enumFromStepLenS, enumFromToEachS, enumFromStepLenEachS,
   toStream, fromStream,
 
index 6d4b633..57756f1 100644 (file)
@@ -19,7 +19,7 @@
 module Data.Array.Parallel.Stream.Flat.Basics (
   -- * Basic operations
   emptyS, singletonS, consS, replicateS, replicateEachS, replicateEachRS,
-  (+++), indexedS,
+  (+++), indexedS, interleaveS,
   tailS,
 
   -- * Conversion to\/from lists
@@ -133,6 +133,27 @@ indexedS (Stream next s n c) = Stream next' (0 :*: s) n ("indexedS" `sArgs` c)
                         Skip    s' -> Skip            (i     :*: s')
                         Done       -> Done
 
+-- | Interleave the elements of two streams
+--
+interleaveS :: Stream a -> Stream a -> Stream a
+{-# INLINE_STREAM interleaveS #-}
+interleaveS (Stream next1 s1 n1 c1) (Stream next2 s2 n2 c2)
+  = Stream next (False :*: s1 :*: s2) (n1+n2) ("interleaveS" `sArgs` (c1,c2))
+  where
+    {-# INLINE next #-}
+    next (False :*: s1 :*: s2)
+      = case next1 s1 of
+          Yield x s1' -> Yield x (True  :*: s1' :*: s2)
+          Skip    s1' -> Skip    (False :*: s1' :*: s2)
+          Done        -> Done
+
+    next (True :*: s1 :*: s2)
+      = case next2 s2 of
+          Yield x s2' -> Yield x (False :*: s1 :*: s2')
+          Skip    s2' -> Skip    (True  :*: s1 :*: s2')
+          -- FIXME: error
+          Done        -> Done
+
 -- | Yield the tail of a stream
 --
 tailS :: Stream a -> Stream a
index a6a49b4..dca3c42 100644 (file)
@@ -40,6 +40,7 @@ update = P.error "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlift
 mbpermute = P.error "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlifted.mbpermute"
 bpermuteDft = P.error "Not implemented: dph-prim-interface:Data.Array.Parallel.Unlifted.bpermuteDft"
 
+interleave xs ys = P.concat [[x,y] | (x,y) <- P.zip xs ys]
 
 pack xs bs = [x | (x,b) <- P.zip xs bs, b]
 
index 6279ca6..e80ddd6 100644 (file)
@@ -5,7 +5,7 @@ module Data.Array.Parallel.Unlifted (
   (:*:)(..), Elt, Array, Segd,
 
   length,
-  empty, replicate, repeat, (+:+),
+  empty, replicate, repeat, (+:+), interleave,
   (!:), extract, drop, permute, mbpermute, bpermute, bpermuteDft, update,
   pack, combine, combine2ByTag,
   enumFromTo, enumFromThenTo, enumFromToEach, enumFromStepLen, enumFromStepLenEach,
index 56c0113..0ab7d4b 100644 (file)
@@ -56,6 +56,8 @@ update :: Elt a => Array a -> Array (Int :*: a) -> Array a
 (+:+) :: Elt a => Array a -> Array a -> Array a
 {-# INLINE_BACKEND (+:+) #-}
 
+interleave :: Elt a => Array a -> Array a -> Array a
+{-# INLINE_BACKEND interleave #-}
 
 pack :: Elt a => Array a -> Array Bool -> Array a
 {-# INLINE_BACKEND pack #-}
@@ -182,6 +184,16 @@ append_s :: Elt a => Segd         -- ^ segment descriptor of result array
                   -> Array a
 {-# INLINE_BACKEND append_s #-}
 
+{-# RULES
+
+"append_s->interleave" forall n k idxs1 idxs2 idxs3 m1 m2 m3 xs ys.
+  append_s (mkSegd (replicate n k) idxs1 m1)
+           (mkSegd (replicate n (GHC.Base.I# 1#)) idxs2 m2) xs
+           (mkSegd (replicate n (GHC.Base.I# 1#)) idxs3 m3) ys
+    = interleave xs ys
+
+  #-}
+
 repeat_c :: Elt a => Int          -- ^ length of the result array
                   -> Array Int    -- ^ number of time a segment is repeated
                   -> Segd         -- ^ segment descriptor
index b4cc56e..cb5fe84 100644 (file)
@@ -28,6 +28,7 @@ bpermute = bpermuteUP
 mbpermute = mbpermuteU
 update = updateUP
 (+:+) = (U.+:+)
+interleave = interleaveUP
 pack = packUP
 combine = combineUP
 combine2ByTag = combine2ByTagUP
index 9fe9a51..a98e235 100644 (file)
@@ -26,7 +26,7 @@ module Data.Array.Parallel.Unlifted.Parallel (
   replicateSUP, replicateRSUP, appendSUP, indicesSUP,
   foldSUP, foldRUP, fold1SUP, sumSUP, sumRUP,
 
-  indexedUP, replicateUP, repeatUP,
+  indexedUP, replicateUP, repeatUP, interleaveUP,
 
   dropUP
 ) where
index caa3b12..f8a12ba 100644 (file)
@@ -23,7 +23,7 @@
 
 module Data.Array.Parallel.Unlifted.Parallel.Basics (
   lengthUP, nullUP, indexedUP,
-  replicateUP, repeatUP
+  replicateUP, repeatUP, interleaveUP
 ) where
 
 import Data.Array.Parallel.Base (
@@ -33,7 +33,7 @@ import Data.Array.Parallel.Base (
 import Data.Array.Parallel.Unlifted.Sequential (
   UA, UArr, (!:), unitsU, lengthU, newU,
   foldU, mapU, zipU, unzipU,
-  indexedU, enumFromToU, replicateU)
+  indexedU, enumFromToU, replicateU, interleaveU)
 import Data.Array.Parallel.Unlifted.Distributed
 import Data.Array.Parallel.Unlifted.Parallel.Combinators ( mapUP )
 import Data.Array.Parallel.Unlifted.Parallel.Enum        ( enumFromToUP )
@@ -76,6 +76,15 @@ repeatUP n es = seq m
               $ enumFromToUP 0 (m*n-1)
   where
     m = lengthU es
+
+-- |Interleave elements of two arrays
+--
+interleaveUP :: UA e => UArr e -> UArr e -> UArr e
+{-# INLINE_UP interleaveUP #-}
+interleaveUP xs ys = joinD theGang unbalanced
+                     (zipWithD theGang interleaveU
+                       (splitD theGang balanced xs)
+                       (splitD theGang balanced ys))
    
 -- |Associate each element of the array with its index
 --
index be1106c..603e4f1 100644 (file)
@@ -26,6 +26,7 @@ mbpermute = mbpermuteU
 bpermuteDft = bpermuteDftU
 update = updateU
 (+:+) = (U.+:+)
+interleave = interleaveU
 pack = packU
 combine = combineU
 combine2ByTag = combine2ByTagU
index b2df674..3d56b31 100644 (file)
@@ -27,7 +27,7 @@ module Data.Array.Parallel.Unlifted.Sequential (
   -- * Basic operations
   lengthU, nullU, emptyU, singletonU, consU, unitsU,
   replicateU, (!:), (+:+),
-  indexedU, repeatU,
+  interleaveU, indexedU, repeatU,
 
   -- * Subarrays
   sliceU, extractU,
index 4e8e197..51c12e0 100644 (file)
@@ -32,7 +32,7 @@ module Data.Array.Parallel.Unlifted.Sequential.Flat (
   replicateU,
   -- replicateEachU,
   (!:), (+:+),
-  indexedU, repeatU, repeatUS,
+  interleaveU, indexedU, repeatU, repeatUS,
 
   -- * Subarrays
   sliceU, extractU,
index b2f5670..5a7d525 100644 (file)
@@ -23,7 +23,7 @@
 module Data.Array.Parallel.Unlifted.Sequential.Flat.Basics (
   lengthU, nullU, emptyU, singletonU, consU, unitsU, replicateU, 
   (!:), (+:+), repeatU, repeatUS,
-  indexedU,
+  interleaveU, indexedU,
   toU, fromU
 ) where
 
@@ -31,7 +31,7 @@ import Data.Array.Parallel.Base (
   (:*:)(..))
 import Data.Array.Parallel.Stream (
   Step(..), Stream(..),
-  consS, singletonS, replicateS, (+++), indexedS,
+  consS, singletonS, replicateS, (+++), indexedS, interleaveS,
   {-replicateEachS, zipS,-} toStream, sNoArgs)
 import Data.Array.Parallel.Unlifted.Sequential.Flat.UArr (
   UA, UArr, unitsU, lengthU, indexU, newU)
@@ -102,6 +102,12 @@ repeatUS k !xs = Stream next (0 :*: k) (k*n) (sNoArgs "repeatUS")
     next (i :*: k) | i == n    = Skip (0 :*: k-1)
                    | otherwise = Yield (xs !: i) (i+1 :*: k)
 
+-- |Interleave the elements of two arrays
+--
+interleaveU :: UA e => UArr e -> UArr e -> UArr e
+{-# INLINE_U interleaveU #-}
+interleaveU xs ys = unstreamU (interleaveS (streamU xs) (streamU ys))
+
 -- |Indexing
 -- ---------