Nota: Esta publicación se reescribió por completo el 10-06-2011; gracias a Peter por ayudarme. Además, no se ofenda si no acepto una respuesta, ya que esta pregunta parece ser bastante abierta. (Pero, si lo resuelve, obtendrá la marca de verificación, por supuesto).

Otro usuario había publicado una pregunta sobre la paralelización de un tipo de fusión. Pensé que escribiría una solución simple, pero, por desgracia, no es mucho más rápido que la versión secuencial.

Planteamiento del problem

Merge sort es un algoritmo de divide y vencerás, donde las hojas de cálculo se pueden paralelizar.

El código funciona de la siguiente manera: la lista se convierte en un árbol, que representa los nodos de cálculo. Luego, el paso de fusión devuelve una lista para cada nodo. Teóricamente, deberíamos ver algunas ganancias de rendimiento significativas, ya que vamos desde unaO (n log n) algoritmo a unaO (n) algoritmo con procesadores infinitos.

Los primeros pasos del cálculo están paralelos, cuando el parámetrol (nivel) es mayor que cero a continuación. Esto se realiza mediante [a través de la variable strat] seleccionando la rpar estrategia, que hará subcálculomergeSort 'x ocurren en paralelo conmergeSort 'y. Luego, fusionamos los resultados y forzamos su evaluación con 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

Solo evaluando unos pocos niveles de cálculo, deberíamos tener un paralelo decente complejidad de la comunicación también: algún orden de factor constante den.

Resultados

Obtenga el código fuente de la cuarta versión aquí http: //pastebin.com/DxYneAa], y ejecútelo con lo siguiente para inspeccionar el uso de subprocesos, o las líneas de comando posteriores para la evaluación comparativa,

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

Resultados en un X5680 de 24 núcleos @ 3.33GHz muestran poca mejora

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

y en mi propia máquina, un Phenom II de cuatro núcleos,

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

La inspección del resultado en Threadscope muestra una buena utilización de pequeñas cantidades de datos. (aunque, lamentablemente, no hay aceleración perceptible). Sin embargo, cuando intento ejecutarlo en listas más grandes, como la anterior, usa aproximadamente 2 cpus la mitad del tiempo. Parece que se están eliminando muchas chispas. También es sensible a los parámetros de memoria, donde 256mb es el punto óptimo, 128mb da 9 segundos, 512 da 8.4 y 1024 da 12.3.

Soluciones que estoy buscando

Finalmente, si alguien conoce algunas herramientas de alta potencia para lanzar esto, lo agradecería. (¿Edén?). Mi interés principal en el paralelismo de Haskell es poder escribir pequeñas herramientas de apoyo para proyectos de investigación, que puedo lanzar en un servidor de 24 u 80 núcleos en el clúster de nuestro laboratorio. Como no son el punto principal de la investigación de nuestro grupo, no quiero dedicar mucho tiempo a la eficiencia de la paralelización. Entonces, para mí, más simple es mejor, incluso si solo termino obteniendo un 20% de uso.

Más discusió Me doy cuenta de que la segunda barra en Threadscope es a veces verde (c.f. espágina principa, donde la segunda barra parece ser siempre la recolección de basura). ¿Qué significa esto ¿Hay alguna forma de evitar la recolección de basura? Parece estar tomando mucho tiempo. Por ejemplo, ¿por qué no se puede bifurcar una subcomputación, devolver el resultado en la memoria compartida y luego morir?Existe una mejor manera (flechas, aplicativo) para expresar paralelismo?