I'm struggling to understand some aspects of parallelism on haskell. I have to apply parallelism to a piece of code, but the attempts I tried do not work properly.
The function is as follows:
fft :: [Complex Float] -> [Complex Float]
fft [a] = [a]
fft as = interleave ls rs
where
(cs,ds) = bflyS as
ls = fft cs
rs = fft ds
interleave [] bs = bs
interleave (a:as) bs = a : interleave bs as
halve as = splitAt n' as
where
n' = div (length as + 1) 2
-- twiddle factors
tw :: Int -> Int -> Complex Float
tw n k = cis (-2 * pi * fromIntegral k / fromIntegral n)
bflyS :: [Complex Float] -> ([Complex Float], [Complex Float])
bflyS as = (los,rts)
where
(ls,rs) = halve as
los = zipWith (+) ls rs
ros = zipWith (-) ls rs
rts = zipWith (*) ros [tw n i | i <- [0..n - 1]]
n = length a
My attempts to perform this parallel function task are as follows:
bflySTask :: [Complex Float] -> ([Complex Float], [Complex Float])
bflySTask as = (los,rts) `using` if n>1000 then parTuple2 (parListChunk 500 rseq) (parListChunk 500 rseq) else r0
where
(ls,rs) = halve as
los = zipWith (+) ls rs
ros = zipWith (-) ls rs
n = length as
fx = (map (tw (n)) [0..n-1])
rts = zipWith (*) ros fx
And with Par Monad
bflySTask :: [Complex Float] -> ([Complex Float], [Complex Float])
bflySTask as = f as
where
(ls,rs) = halve as
los = zipWith (+) ls rs
ros = zipWith (-) ls rs
n = length as
fx = (map (tw (n)) [0..n-1])
f as = if n>10000 then
runPar $ do
v1<-new
v2<-new
fork $ put v1 (zipWith (*) ros fx)
fork $ put v2 (zipWith (+) ls rs)
a <- get v1
b <- get v2
return (a, b)
else
(zipWith (+) ls rs, zipWith (*) ros fx)
Both approaches slightly reduce parallelism, like the balance of Parallel GC 1.30, and some sparks GC'd and fizzled. Does anyone know what I can do for others to apply parallelism to these functions without changing the data structure?
source
share