¿Se puede hacer la recursión en paralelo? ¿Tendría eso sentido?

7

Digo, estoy usando un simple recursivo algo para fibonacci, que se ejecutaría como:

fib(5) -> fib(4)+fib(3)
            |      |
      fib(3)+fib(2)|
                fib(2)+fib(1)

y así sucesivamente

Ahora, la ejecución seguirá siendo secuencial. En lugar de eso, ¿cómo puedo codificar esto para que fib(4) y fib(3) se calculen generando 2 hilos separados, luego en fib(4) , 2 hilos se generan para fib(3) y fib(2) . ¿Lo mismo ocurre cuando fib(3) se divide en fib(2) y fib(1) ?

(Soy consciente de que la programación dinámica sería un enfoque mucho mejor para Fibonacci, solo lo uso como un ejemplo fácil aquí)

(si alguien pudiera compartir un ejemplo de código en C \ C ++ \ C # también, sería ideal)

    
pregunta Akash 11.05.2014 - 17:48

6 respuestas

24

Esto es posible pero una muy mala idea; calcule la cantidad de subprocesos que generará al calcular fib (16), por ejemplo, y luego multiplíquelo por el costo de un subproceso. Los hilos son increíblemente caros; Hacer esto para la tarea que describe es como contratar a un mecanógrafo diferente para escribir cada personaje de una novela.

Dicho esto, los algoritmos recursivos suelen ser buenos candidatos para la paralelización, especialmente si dividen el trabajo en dos trabajos más pequeños que se pueden realizar de forma independiente. El truco es saber cuándo dejar de paralelizar.

En general, desea paralelizar solo tareas "vergonzosamente paralelas". Es decir, las tareas que son computacionalmente caras y se pueden computar de forma independiente . Mucha gente se olvida de la primera parte. Los subprocesos son tan caros que solo tiene sentido hacer uno cuando tienes una gran cantidad de trabajo por hacer, y además, que puedes dedicar un procesador completo al subproceso . Si tienes 8 procesadores, hacer 80 subprocesos los obligará a compartir el procesador, ralentizando tremendamente a cada uno de ellos. Es mejor hacer solo 8 subprocesos y dejar que cada uno tenga acceso al procesador al 100% cuando tenga que realizar una tarea vergonzosamente paralela.

Las bibliotecas como la biblioteca paralela de tareas en .NET están diseñadas para descubrir automáticamente cuánto es eficiente el paralelismo; Podría considerar investigar su diseño si este tema le interesa.

    
respondido por el Eric Lippert 11.05.2014 - 18:14
3

La pregunta tiene dos respuestas, en realidad.

¿Se puede hacer la recursión en paralelo? ¿Eso tendría sentido?

Sí, por supuesto. En la mayoría de los casos (¿todos?), Un algoritmo recursivo se puede reescribir de una manera sin recursión, lo que lleva a un algoritmo que a menudo es fácilmente paralelizable. No siempre, pero a menudo.

Think Quicksort, o iteración a través de un árbol de directorios. En ambos casos, se puede utilizar una cola para contener todos los resp. De resultados intermedios. subdirectorios encontrados. La cola se puede procesar en paralelo, creando finalmente más entradas hasta que la tarea se haya completado con éxito.

¿Qué pasa con el ejemplo fib() ?

Desafortunadamente, la función de Fibonacci es una mala elección, ya que los valores de entrada dependen completamente de los resultados calculados previamente. Esta dependencia hace que sea difícil hacerlo en paralelo si se inicia cada vez con 1 y 1 .

Sin embargo, si necesita realizar los cálculos de Fibonacci con más frecuencia, podría ser una buena idea almacenar (o almacenar en caché) los resultados precalculados para evitar todos los cálculos hasta ese momento. El concepto detrás es bastante similar a las tablas del arco iris.

Digamos que usted almacena en caché cada décimo par de números Fibo hasta 10.000. Iniciar esta rutina de inicialización en un hilo de fondo. Ahora, si alguien pregunta por el número 5246 de Fibo, el algoritmo simplemente toma el par de 5240 y comienza el cálculo desde ese punto en adelante. Si el par 5240 aún no está allí, simplemente espere.

De esta manera, el cálculo de muchos números de fibo elegidos al azar se podría hacer de manera muy eficiente y en paralelo, porque es muy poco probable que dos hilos tengan que calcular los mismos números, e incluso entonces, no sería un gran problema. .

    
respondido por el JensG 12.05.2014 - 01:02
1

Por supuesto que es posible, pero para un ejemplo tan pequeño (y, de hecho, para muchos que son mucho más grandes) la cantidad de código de control de plomería / concurrencia que tendría que escribir ocultaría el código de negocio hasta el punto de que no sería una buena idea a menos que realmente, realmente, realmente necesite que los números de Fibonacci se calculen muy rápido.

Casi siempre es más legible y mantenible formular su algoritmo normalmente y luego permitir una extensión de biblioteca / idioma de concurrencia como TBB o GCD tenga cuidado de cómo distribuir realmente los pasos a los hilos.

    
respondido por el Kilian Foth 11.05.2014 - 18:03
0

En su ejemplo, está calculando fib (3) dos veces, lo que conduce a una doble ejecución de la totalidad de fib (1) y fib (2), para números más altos es aún peor.

Probablemente ganará velocidad sobre la solución no recursiva, pero costará mucho más en recursos (procesadores) de lo que vale.

    
respondido por el spado 11.05.2014 - 19:37
0

¡Sí puede! El ejemplo más simple que puedo darte es imaginar un árbol binario de números. Por alguna razón, usted quiere sumar todos los números en un árbol binario. Bueno, para hacerlo, debe agregar el valor del nodo raíz al valor del nodo izquierdo / derecho ... pero el nodo mismo puede ser la raíz de otro árbol (un subárbol del árbol original)
En lugar de calcular la suma del subárbol izquierdo, luego la suma del derecho ... luego agréguelos al valor de la raíz ... puede calcular la suma del subárbol izquierdo y derecho en paralelo.

    
respondido por el Vincent Grigori 10.06.2016 - 12:43
0

Un problema es que el algoritmo recursivo estándar para la función de fibonacci es muy malo, ya que el número de llamadas para calcular fib (n) es igual a fib (n), que es un crecimiento muy rápido. Así que realmente me negaría a hablar de eso.

Veamos un algoritmo recursivo más razonable, Quicksort. Ordena una matriz haciendo lo siguiente: Si la matriz es pequeña, ordénela utilizando Bubblesort, Insertion sort o lo que sea. De lo contrario: elija un elemento de la matriz. Ponga todos los elementos más pequeños a un lado, todos los elementos más grandes al otro lado. Ordenar el lado con los elementos más pequeños. Ordenar el lado con los elementos más grandes.

Para evitar una recursión arbitrariamente profunda, el método habitual es que la función de ordenación rápida realice una llamada recursiva para el más pequeño de los dos lados (el que tiene menos elementos) y maneje el lado más grande en sí.

Ahora tiene una forma muy sencilla de usar varios subprocesos: en lugar de hacer una llamada recursiva para ordenar el lado más pequeño, comience un subproceso; luego ordena la mitad más grande, luego espera a que termine el hilo. Pero comenzar con hilos es caro. Por lo tanto, mide el tiempo promedio que se tarda en ordenar n elementos, en comparación con el tiempo para crear un hilo. A partir de eso, se encuentra la n más pequeña, por lo que vale la pena crear un nuevo hilo. Entonces, si el lado más pequeño que necesita ser ordenado está por debajo de ese tamaño, haces una llamada recursiva. De lo contrario, ordena esa mitad en un nuevo hilo.

    
respondido por el gnasher729 10.06.2016 - 13:14

Lea otras preguntas en las etiquetas