我有一个 haskell 代码来解决快速傅立叶变换,我想在它上面应用数据并行性。然而,我使用的每一个策略都会产生太多的 Spark ,其中大部分都被溢出了。
有没有人知道如何在以下算法上应用良好的数据并行策略:
-- radix 2 Cooley-Tukey FFT
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
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 (length as) i | i <- [0..(length ros) - 1]]
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)
PAR MONAD
leftaroundabout 的回答帮助我了解了如何在代码上应用数据并行性。但是,我研究了 par monad 并尝试将任务并行性应用于它。问题是它的运行速度比原来的 bflyS 慢。我认为与我正在做的相关工作相比,我开发的代码创建线程的成本很高。有谁知道如何以更好的方式使用 par monad ?
--New Task Parallelism bflyS
bflySTask :: [Complex Float] -> ([Complex Float], [Complex Float])
bflySTask as = runPar $ do
let (ls, rs) = halve as
v1<-new
v2<-new
let ros = DATA.zipWith (-) ls rs
let aux = DATA.map (tw n) [0..n-1]
fork $ put v1 (DATA.zipWith (+) ls rs)
fork $ put v2 (DATA.zipWith (*) ros aux)
los <- get v1
rts <- get v2
return (los, rts)
where
n = DATA.length as
最佳答案
首先:在我开始考虑并行性之前,这里有很多优化要做:
Data.Vector
)所实现的那样快地进行遍历。 ,因为您不可避免地会遇到很多缓存未命中。事实上,我很少看到基于列表的算法从并行化中获得很多好处,因为它们受内存而非 CPU 性能的限制。 length
,但这是一个非常浪费的函数(O (n) 对于可能是 O (1) 的东西)。使用一些可能处理长度的容器;列表并不意味着(我们希望保持它们的能力是无限的)。 并行化本身将非常简单;我会按照 John L 的建议检查长度,实际上我宁愿在触发线程之前需要一个相当大的尺寸,至少是 256 之类的:因为性能可能仅在数千个尺寸时才变得至关重要,这应该是有足够的线程让你的核心保持忙碌。
import Data.Vector.Unboxed as UBV
import Control.Parallel.Strategies
type ℂ = Complex Float
fft' :: UBV.Vector ℂ -> UBV.Vector ℂ
fft' aₓs = interleave lᵥs rᵥs
where (lᵥs, rᵥs) = (fft lₓs, fft rₓs)
`using` if UBV.length aₓs > 256 then parTuple2 else r0
(lₓs, rₓs) = byflyS aₓs
关于haskell - 如何在haskell快速傅里叶变换上应用数据并行?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22335577/