sobre - multiplos en haskell

¿Por qué no hay paralelismo implícito en Haskell?

Question

Haskell es funcional y puro, por lo que básicamente tiene todas las propiedades necesarias para que un compilador pueda abordar el paralelismo implícito .

Considera este ejemplo trivial:

f = do
a <- Just 1
b <- Just $ Just 2
-- ^ The above line does not utilize an `a` variable, so it can be safely
-- executed in parallel with the preceding line
c <- b
-- ^ The above line references a `b` variable, so it can only be executed
-- sequentially after it
return (a, c)
-- On the exit from a monad scope we wait for all computations to finish and
-- gather the results

Esquemáticamente, el plan de ejecución se puede describir como:

 do
|
+---------+---------+
| |
a <- Just 1 b <- Just $ Just 2
| |
| c <- b
| |
+---------+---------+
|
return (a, c)

¿Por qué no hay tal funcionalidad implementada en el compilador con una bandera o un pragma todavía? ¿Cuáles son los motivos prácticos?

Answer 1

En realidad, hubo tal intento, pero no en hardware común debido a la baja cantidad disponible de núcleos. El proyecto se llama Reduceron . Ejecuta el código Haskell con un alto nivel de paralelismo. En caso de que alguna vez se lanzara como un núcleo ASIC de 2 GHz , tendríamos un gran avance en la velocidad de ejecución de Haskell.

Answer 2

Este es un tema largamente estudiado. Si bien se puede derivar implícitamente el paralelismo en el código Haskell, el problema es que hay demasiado paralelismo, en un grano demasiado fino, para el hardware actual.

Entonces terminas gastando esfuerzo en la contabilidad, no corriendo las cosas más rápido.

Como no tenemos hardware paralelo infinito, se trata de elegir la granularidad correcta: demasiado gruesa y habrá procesadores inactivos, demasiado finos y los gastos generales serán inaceptables.

Lo que tenemos es más paralelismo de grano grueso (chispas) adecuado para generar miles o millones de tareas paralelas (por lo que no en el nivel de instrucción), que se asignan a los pocos núcleos que normalmente tenemos disponibles en la actualidad.

Tenga en cuenta que para algunos subconjuntos (por ejemplo, el procesamiento de matrices) hay bibliotecas de paralelización totalmente automáticas con modelos de costos ajustados.

Para más información sobre este tema, consulte http://research.microsoft.com/en-us/um/people/tharris/papers/2007-fdip.pdf , donde presentan un enfoque automático para la inserción de par en programas arbitrarios de Haskell.

Answer 3

Respuesta corta: a veces, ejecutar cosas en paralelo resulta ser más lento, no más rápido. Y averiguar cuándo es y cuándo no es una buena idea es un problema de investigación sin resolver.

Sin embargo, todavía puede estar "utilizando repentinamente todos esos núcleos sin molestarse con los hilos, los interbloqueos y las condiciones de carrera". No es automático; ¡solo tiene que darle al compilador algunas pistas sobre dónde hacerlo! :-RE

Answer 4

Si bien su bloque de código puede no ser el mejor ejemplo debido a la dependencia implícita de datos entre la b , vale la pena señalar que estas dos vinculaciones conmutan en esa

f = do
a <- Just 1
b <- Just $ Just 2
...

dará los mismos resultados

f = do
b <- Just $ Just 2
a <- Just 1
...

entonces esto aún podría ser paralelizado de una manera especulativa. Vale la pena señalar que esto no necesita tener nada que ver con las mónadas. Podríamos, por ejemplo, evaluar todas las expresiones independientes en un bloque de let en paralelo o podríamos introducir una versión de let que así lo haría. La biblioteca lparallel para Common Lisp hace esto.

Ahora, de ninguna manera soy un experto en el tema, pero esta es mi comprensión del problema. Un gran obstáculo es determinar cuándo es ventajoso paralelizar la evaluación de expresiones múltiples. Hay una sobrecarga asociada con el inicio de los hilos separados para la evaluación, y, como muestra su ejemplo, puede dar como resultado un trabajo desperdiciado. Algunas expresiones pueden ser demasiado pequeñas para que la evaluación paralela valga la pena. Tal como lo entiendo, la obtención de una medida totalmente precisa del costo de una expresión equivaldría a resolver el problema de detención, por lo que se lo relega a usar un enfoque heurístico para determinar qué evaluar en paralelo.

Entonces, no siempre es más rápido lanzar más núcleos a un problema. Incluso cuando se paralela explícitamente un problema con las muchas bibliotecas Haskell disponibles, a menudo no se verá mucha aceleración simplemente evaluando las expresiones en paralelo debido a la gran asignación de memoria y uso y la tensión que esto pone en el recolector de basura y el caché de la CPU. Usted termina necesitando un buen diseño de memoria compacta y recorrer sus datos de forma inteligente. Tener listas enlazadas de 16 hilos te atascará en tu bus de memoria y podría hacer las cosas más lentas.

Por lo menos, qué expresiones se pueden paralelizar de manera efectiva es algo que no es obvio para muchos programadores (al menos no para este), por lo que hacer que un compilador lo haga de manera efectiva no es trivial.

Answer 5

Una de las razones es porque Haskell no es estricto y no evalúa nada por defecto. En general, el compilador no sabe que el cálculo de a y b termina, por lo tanto, tratar de calcularlo sería un desperdicio de recursos:

x :: Maybe ([Int], [Int])
x = Just undefined
y :: Maybe ([Int], [Int])
y = Just (undefined, undefined)
z :: Maybe ([Int], [Int])
z = Just ([0], [1..])
a :: Maybe ([Int], [Int])
a = undefined
b :: Maybe ([Int], [Int])
b = Just ([0], map fib [0..])
where fib 0 = 1
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Considéralo para las siguientes funciones

main1 x = case x of
Just _ -> putStrLn "Just"
Nothing -> putStrLn "Nothing"

(a, b) parte no necesita ser evaluada. Tan pronto como obtenga que x = Just _ puede proceder a la bifurcación - por lo tanto, funcionará para todos los valores, pero a

main2 x = case x of
Just (_, _) -> putStrLn "Just"
Nothing -> putStrLn "Nothing"

Esta función impone la evaluación de tupla. Por lo tanto, x terminará con un error mientras que el resto funcionará.

main3 x = case x of
Just (a, b) -> print a >> print b
Nothing -> putStrLn "Nothing"

Esta función primero imprimirá la primera lista y luego la segunda. Funcionará para z (lo que resulta en la impresión de una cantidad infinita de números, pero Haskell puede manejarlo). b eventualmente se quedará sin memoria.

Ahora, en general, no sabe si el cómputo termina o no y cuántos recursos consumirá. Las listas infinitas están perfectamente bien en Haskell:

main = maybe (return ()) (print . take 5 . snd) b -- Prints first 5 Fibbonacci numbers

Por lo tanto, los hilos de desove para evaluar la expresión en Haskell podrían tratar de evaluar algo que no debe evaluarse por completo (por ejemplo, la lista de todos los números primos) que los programadores usan como parte de la estructura. Los ejemplos anteriores son muy simples y puede argumentar que el compilador podría notarlos; sin embargo, no es posible en general debido a un problema de detención (no puede escribir el programa que toma el programa arbitrario y su entrada y verifica si termina), por lo tanto no es optimización segura

Además, lo cual fue mencionado por otras respuestas, es difícil predecir si vale la pena comprometerse con la carga adicional de un hilo adicional. A pesar de que GHC no engendra nuevos hilos para chispas usando el enhebrado verde (con un número fijo de hilos del kernel, dejando de lado algunas excepciones), aún necesita mover los datos de un núcleo a otro y sincronizarlos, lo que puede ser bastante costoso.

Sin embargo, Haskell sí ha guiado la paralelización sin romper la pureza del lenguaje por par y funciones similares.