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

Digamos, estoy usando un simple algoritmo recursivo para fibonacci, que se ejecutaría como:

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

y así

Ahora, la ejecución seguirá siendo secuencial. En lugar de eso, ¿cómo iba a codificar esta manera que fib(4)y fib(3)son calculados por el desove 2 hilos separados, a continuación, en fib(4), 2 hilos son generados por fib(3)y fib(2). Lo mismo para 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 la usé como un ejemplo fácil aquí)

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

Esto es posible pero una muy mala idea; calcule el número de hilos que generará al calcular fib (16), digamos, y luego multiplíquelo por el costo de un hilo. 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 a menudo son buenos candidatos para la paralelización, particularmente 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, tareas que son computacionalmente caras y pueden calcularse de manera independiente . Mucha gente se olvida de la primera parte. Los subprocesos son tan caros que solo tiene sentido crear uno cuando tienes una gran cantidad de trabajo que hacer, y además, puedes dedicar un procesador completo al subproceso . Si tiene 8 procesadores, entonces hacer 80 hilos los obligará a compartir el procesador, ralentizando enormemente cada uno de ellos. Es mejor hacer solo 8 subprocesos y dejar que cada uno tenga un 100% de acceso al procesador cuando tenga que realizar una tarea vergonzosamente paralela.

Las bibliotecas como la Biblioteca de tareas paralelas en .NET están diseñadas para determinar automáticamente cuánto paralelismo es eficiente; puede considerar investigar su diseño si este tema le interesa.

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 puede reescribirse sin recurrencia, lo que lleva a un algoritmo que a menudo es fácilmente paralelizable. No siempre, pero a menudo.

Piense en Quicksort o iterando a través de un árbol de directorios. En ambos casos, se podría usar una cola para contener todos los resultados intermedios resp. subdirectorios encontrados. La cola se puede procesar en paralelo, eventualmente creando más entradas hasta que la tarea se haya completado con éxito.

¿Qué hay del fib()ejemplo?

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

Sin embargo, si necesita hacer 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 de arcoiris.

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

De esta manera, el cálculo de muchos números de fibo elegidos al azar podría hacerse 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.

Por supuesto, 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 oscurecería el código comercial hasta el punto de que no sea ​​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 fácil de leer y mantener formular su algoritmo normalmente y luego dejar que una biblioteca de concurrencia / extensión de lenguaje como TBB o GCD se encargue de cómo distribuir realmente los pasos a los hilos.

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

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

¡Sí puede! Mi ejemplo más simple que puedo darle es imaginar un árbol binario de números. Por alguna razón, desea 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 en sí puede ser la raíz de otro árbol (un subárbol del árbol original) en
lugar de calcular el suma del subárbol izquierdo, luego la suma de la derecha ... luego agréguelas al valor de la raíz ... puede calcular la suma del subárbol izquierdo y derecho en paralelo.

Un problema es que el algoritmo recursivo estándar para la función fibonacci es terriblemente 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 usando Bubblesort, Insertion sort, o lo que sea. De lo contrario: elija un elemento de la matriz. Coloque 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 hará una llamada recursiva para el más pequeño de los dos lados (el que tiene menos elementos) y manejará el lado más grande.

Ahora tiene una manera muy simple de usar múltiples hilos: en lugar de hacer una llamada recursiva para ordenar el lado más pequeño, inicie un hilo; luego clasifique la mitad más grande, luego espere a que termine el hilo. Pero comenzar hilos es costoso. Entonces, mide cuánto tiempo toma en promedio ordenar n elementos, en comparación con el tiempo para crear un hilo. A partir de eso, encontrará el n más pequeño de tal manera que valga 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, usted hace una llamada recursiva. De lo contrario, ordena esa mitad en un nuevo hilo.