У меня есть код haskell для разрешения быстрого преобразования Фурье, и я хочу применить к нему параллелизм данных. Однако каждая стратегия, которую я использую, порождает слишком много искр, и большинство из них переполняется.
Кто-нибудь знает, как применить хорошую стратегию параллелизма данных в следующем алгоритме:
-- 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)
ПАР МОНАД
Ответ от leftaroundabout очень помог мне понять, как применять параллелизм данных в коде. Однако я изучил монаду par и попытался применить к ней параллелизм задач. Проблема в том, что он работает намного медленнее, чем оригинальный bflyS. Я думаю, что код, который я разработал, слишком дорог для создания потоков по сравнению с относительной работой, которую я делаю. Кто-нибудь знает, как лучше использовать монаду par?
--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
repaвместоvector. Тогда вы получаете параллелизм бесплатно. 12.03.2014