Nenhuma aceleração com paralelização ingênua de classificação por mesclagem em Haskell

ota: Esta publicação foi completamente reescrita em 10/06/2011; obrigado a Peter por me ajudar. Além disso, por favor, não se ofenda se eu não aceitar uma resposta, pois essa pergunta parece ser bastante aberta. (Mas, se você resolver, obtém a marca de seleção, é claro

Outro usuário postou uma pergunta sobre paralelizar uma classificação de mesclagem. Pensei em escrever uma solução simples, mas, infelizmente, não é muito mais rápida que a versão seqüencia

Problem statement

classificação @Merge é um algoritmo de divisão e conquista, no qual as folhas da computação podem ser paralelizada

O código funciona da seguinte maneira: a lista é convertida em uma árvore, representando nós de computação. Em seguida, a etapa de mesclagem retorna uma lista para cada nó. Teoricamente, devemos ver ganhos significativos de desempenho, já que estamos saindo de umOlgoritmo @ (n log n) para umOlgoritmo (n) com infinitos processadore

Os primeiros passos da computação são paralelos, quando o parâmetrol (nível) é maior que zero abaixo. Isso é feito por [via variável strat] selecionando o rpar estratégia, que fará a sub-computaçãomergeSort 'x ocorrem em paralelo commergeSort 'y. Em seguida, mesclamos os resultados e forçamos sua avaliação com 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

Avaliando apenas alguns níveis da computação, deveríamos ter um paralelo decenteomplexidade da comunicação também - alguma ordem de fator constante den.

Resultado

Obtenha o código fonte da 4ª versão aqui http: //pastebin.com/DxYneAa] e execute-o com o seguinte para inspecionar o uso do encadeamento ou as linhas de comando subseqüentes para comparações,

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

s resultados em um X5680 de 24 núcleos a 3,33 GHz mostram pouca melhor

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

em minha própria máquina, um Phenom II de quatro núcleo

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

A inspeção do resultado no encadeamento mostra uma boa utilização para pequenas quantidades de dados. (embora, infelizmente, não haja aceleração perceptível). No entanto, quando tento executá-lo em listas maiores, como acima, ele usa cerca de 2 cpus na metade do tempo. Parece que muitas faíscas estão sendo podadas. Também é sensível aos parâmetros de memória, onde 256mb é o ponto ideal, 128mb fornece 9 segundos, 512 fornece 8,4 e 1024 fornece 12,3!

Solutions Estou procurando

Finalmente, se alguém conhece algumas ferramentas de alta potência para jogar nisso, eu agradeceria. (Éden?). Meu principal interesse no paralelismo de Haskell é ser capaz de escrever pequenas ferramentas de suporte para projetos de pesquisa, que eu posso lançar em um servidor núcleo de 24 ou 80 no cluster de nosso laboratório. Como eles não são o ponto principal da pesquisa do nosso grupo, não quero gastar muito tempo com a eficiência da paralelização. Então, para mim, mais simples é melhor, mesmo que eu acabe recebendo 20% de uso.

Mais discussão Percebo que a segunda barra no encadeamento às vezes é verde (c.f. suapagina inicia, onde a segunda barra parece sempre ser uma coleta de lixo). O que isto significa Existe alguma maneira de evitar a coleta de lixo? Parece estar demorando muito tempo. Por exemplo, por que uma subcomputação não pode ser bifurcada, retornar o resultado na memória compartilhada e depois morre Existe uma maneira melhor (setas, aplicativo) de expressar paralelism

questionAnswers(2)

yourAnswerToTheQuestion