Отсутствие ускорения с наивным распараллеливанием сортировки слиянием в Haskell

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

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

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

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

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

Первые шаги вычислений распараллеливаются, когда параметр l (уровень) больше нуля ниже. Это делается с помощью [через переменную strat ], выбирая стратегию 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.

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

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

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

Дальнейшее обсуждение

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