Подтвердить что ты не робот

Как применять параллелизм данных для быстрой преобразования Фурье 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
4b9b3361

ОТВЕТЫ

Ответ 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