Как применять параллелизм данных для быстрой преобразования Фурье haskell?
У меня есть код haskell для разрешения быстрого преобразования Фурье, и я хочу применить данные parallelism к нему. Тем не менее, каждая стратегия, которую я использую, генерирует слишком много искр, и большинство из них переполняются.
Кто-нибудь имеет представление о том, как применить хорошую стратегию данных parallelism по следующему алгоритму:
-- 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 очень помог мне понять, как применять данные parallelism в коде. Тем не менее, я изучил парную монаду и попытался применить к ней задачу parallelism. Проблема в том, что он работает медленнее, чем исходный bflyS. Я думаю, что код, который я разработал, является способом дорогостоящего создания потоков по сравнению с относительной работой, которую я делаю. Кто-нибудь знает, как лучше использовать парную монаду?
--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
Ответы
Ответ 1
Во-первых: там будет много оптимизации, прежде чем я начну думать о parallelism:
-
Перечисляет рок, но их непоследовательная модель памяти означает, что они просто не могут допускать обход почти так же быстро, как то, что вы можете достичь с помощью жестких массивов, таких как Data.Vector
, потому что вы неизбежно оказываетесь в большом количестве промахи кэша. На самом деле, я редко видел, что алгоритм на основе списков сильно выигрывает от параллелизации, потому что они связаны памятью, а не с производительностью процессора.
-
Ваши переменные факторы вычисляются снова и снова, вы, очевидно, можете многое получить через воспоминания здесь.
-
Вы продолжаете называть length
, но это очень расточительная функция (O (n) для чего-то, что может быть O (1)). Используйте некоторый контейнер, который, вероятно, обрабатывает длину; списки не предназначены (мы любим держать их способности бесконечными).
Сама параллелизация будет довольно простой; Я бы проверял длину, предложенную Джоном Л, действительно, я бы предпочел потребовать довольно большой размер перед тем, как исправить поток, по крайней мере, что-то вроде 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