чание: этот пост был полностью переписан 2011-06-10; спасибо Петру за помощь, Также, пожалуйста, не обижайтесь, если я не приму один ответ, так как этот вопрос кажется довольно открытым. (Но, если вы решите это, вы, конечно, отметите галочкой).

Другой пользователь задал вопрос о распараллеливании сортировки слиянием. Я думал, что напишу простое решение, но, увы, оно не намного быстрее, чем последовательная версия.

Постановка задачи

Сортировка слиянием - это алгоритм «разделяй и властвуй», в котором листья вычислений могут быть распараллелены.

Код работает следующим образом: список преобразуется в дерево, представляющее вычислительные узлы. Затем шаг слияния возвращает список для каждого узла. Теоретически, мы должны увидеть некоторые существенные улучшения производительности, так как мы идем отO(п лог п) алгоритм кO(n) алгоритм с бесконечными процессорами.

Первые шаги вычисления распараллеливаются, когда параметрl (уровень) больше нуля ниже. Это делается с помощью [через переменнуюстрат] выбираяRPAR стратегия, которая сделает подсчетmergeSort 'x происходят параллельно сmergeSort 'y, Затем мы объединяем результаты и форсируемrdeepseq.

data Tree a = Leaf a | Node (Tree a) (Tree a) deriving (Show)

instance NFData a => NFData (Tree a) where
    rnf (Leaf v) = deepseq v ()
    rnf (Node x y) = deepseq (x, y) ()

listToTree [] = error "listToTree -- empty list"
listToTree [x] = Leaf x
listToTree xs = uncurry Node $ listToTree *** listToTree $
    splitAt (length xs `div` 2) xs

-- mergeSort' :: Ord a => Tree a -> Eval [a]
mergeSort' l (Leaf v) = return [v]
mergeSort' l (Node x y) = do
    xr <- strat $ runEval $ mergeSort' (l - 1) x
    yr <- rseq $ runEval $ mergeSort' (l - 1) y
    rdeepseq (merge xr yr)
    where
        merge [] y = y
        merge x [] = x
        merge (x:xs) (y:ys) | x < y = x : merge xs (y:ys)
                            | otherwise = y : merge (x:xs) ys
        strat | l > 0 = rpar
              | otherwise = rseq

mergeSort = runEval . mergeSort' 10

Оценивая только несколько уровней вычислений, мы должны иметь приличную параллельсложность общения а также - некоторый постоянный фактор порядкаn.

Результаты

Получить исходный код 4-й версии здесь [http://pastebin.com/DxYneAaC ], и запустите его со следующим для проверки использования потока или последующих командных строк для бенчмаркинга,

rm -f ParallelMergeSort; ghc -O2 -O3 -optc-O3 -optc-ffast-math -eventlog --make -rtsopts -threaded ParallelMergeSort.hs
./ParallelMergeSort +RTS -H512m -K512m -ls -N
threadscope ParallelMergeSort.eventlog

Результаты на 24-ядерном X5680 с частотой 3,33 ГГц показывают небольшое улучшение

> ./ParallelMergeSort 
initialization: 10.461204s sec.
sorting: 6.383197s sec.
> ./ParallelMergeSort +RTS -H512m -K512m -N
initialization: 27.94877s sec.
sorting: 5.228463s sec.

и на моей собственной машине, четырехъядерный Phenom II,

> ./ParallelMergeSort 
initialization: 18.943919s sec.
sorting: 10.465077s sec.
> ./ParallelMergeSort +RTS -H512m -K512m -ls -N
initialization: 22.92075s sec.
sorting: 7.431716s sec.

Проверка результатов в потоковой области показывает хорошее использование для небольших объемов данных. (хотя, к сожалению, ощутимого ускорения нет). Однако, когда я пытаюсь запустить его в больших списках, как указано выше, он использует около 2 процессоров в половину времени. Кажется, что многие искры подрезаются. Он также чувствителен к параметрам памяти, где 256 МБ - это приятное место, 128 МБ - 9 секунд, 512 - 8,4, а 1024 - 12,3!

Решения, которые я ищу

Наконец, если кто-нибудь знает мощные инструменты, чтобы бросить это, я был бы признателен. (Eden?). Мой основной интерес к параллелизму на Haskell - уметь писать небольшие вспомогательные инструменты для исследовательских проектов, которые я могу использовать на 24 или 80 основных серверах в кластере нашей лаборатории. Поскольку они не являются основной целью исследований нашей группы, я не хочу тратить много времени на эффективность распараллеливания. Так что для меня проще - лучше, даже если я получу только 20% использования.

Дальнейшее обсуждениеЯ замечаю, что второй столбец в области видимости иногда зеленый (см. Егодомашняя страницагде второй бар, кажется, всегда сборщик мусора). Что это значит?Есть ли способ обойти сборку мусора? Кажется, это занимает много времени. Например, почему нельзя вычислить подкомпьютер, вернуть результат в совместно используемую память и затем умереть?Есть ли лучший способ (стрелки, аппликативный) для выражения параллелизма?