Paralelización automática

Question

¿Cuál es su opinión sobre un proyecto que intentará tomar un código y dividirlo en subprocesos automáticamente (quizás tiempo de compilación, probablemente en tiempo de ejecución).

Tome una mirada en el código de abajo:

for(int i=0;i<100;i++) 
    sum1 += rand(100) 
for(int j=0;j<100;j++) 
    sum2 += rand(100)/2 

Este tipo de código se puede obtener de forma automática dividida a 2 hilos diferentes que se ejecutan en paralelo. ¿Crees que es posible? Tengo la sensación de que teóricamente es imposible (me recuerda el problema de detención) pero no puedo justificar este pensamiento.

¿Crees que es un proyecto útil? ¿Hay algo así?

Answer 1

Si en el caso general es posible saber si una pieza de código se puede paralelizar realmente no importa, porque incluso si su algoritmo no puede detectar todos los casos que se pueden paralelizar, quizás pueda detectar algunos de ellos.

Eso no significa que sería útil. Considere lo siguiente:

1. En primer lugar, para hacerlo en tiempo de compilación, debe inspeccionar todas las rutas de código que potencialmente puede alcanzar dentro de la construcción que desea paralelizar. Esto puede ser complicado para cualquier cosa que no sean cálculos.
2. En segundo lugar, debe decidir de alguna manera qué es paralelizable y qué no. No se puede dividir trivialmente un bucle que modifica el mismo estado en varios hilos, por ejemplo. Esta es probablemente una tarea muy difícil y en muchos casos terminará por no estar seguro; de hecho, dos variables podrían hacer referencia al mismo objeto.
3. Incluso si pudiera lograr esto, terminaría siendo confuso para el usuario. Sería muy difícil explicar por qué su código no era paralelizable y cómo debería cambiarse.

Creo que si quieres lograr esto en Java, necesitas escribirlo más como una biblioteca, y dejar que el usuario decida qué paralelizar (funciones de la biblioteca junto con anotaciones, solo pensar en voz alta). Los lenguajes funcionales son mucho más adecuados para esto.

Como trivia: durante un curso de programación paralela, tuvimos que inspeccionar el código y decidir si era paralelizable o no. No puedo recordar los detalles (algo sobre la propiedad "a lo más una vez"? Alguien me llene?), pero la moraleja de la historia es que fue extremadamente difícil, incluso para lo que parecían ser casos triviales.

Answer 2

Esto prácticamente no es posible.

El problema es que necesita saber, de antemano, mucha más información de la que está disponible para el compilador, o incluso el tiempo de ejecución, con el fin de paralelizar con eficacia.

Si bien sería posible paralelizar bucles muy simples, incluso entonces, hay un riesgo involucrado. Por ejemplo, el código anterior solo se puede paralelizar si rand() es seguro para subprocesos y muchas rutinas de generación de números aleatorios no lo son. (Sin embargo, el Math.random() de Java está sincronizado).

Intentar hacer este tipo de paralelización automática es, al menos en este punto, no práctico para cualquier aplicación "real".

Answer 3

Existen algunos proyectos que intentan simplificar la paralelización, como Cilk. Sin embargo, no siempre funciona tan bien.

Answer 4

Esto se llama paralelización automática. Si está buscando algún programa que pueda usar que lo haga por usted, aún no existe. Pero puede eventualmente. Este es un problema difícil y es un área de investigación activa. Si aún tiene curiosidad ...

Es posible dividir automáticamente su ejemplo en varios hilos, pero no en la forma en que está pensando. Algunas técnicas actuales intentan ejecutar cada iteración de para -loop en su propio hilo. Un hilo obtendría los índices pares (i = 0, i = 2, ...), el otro obtendría los índices impares (i = 1, i = 3, ...). Una vez hecho esto, para -loop, se puede iniciar el siguiente. Otras técnicas pueden volverse más locas, ejecutando el incremento i++ en un hilo y el rand() en un hilo separado.

Como han señalado otros, existe una verdadera dependencia entre iteraciones porque rand() tiene un estado interno. Eso no obstaculiza la paralelización por sí mismo. El compilador puede reconocer la dependencia de la memoria, y el estado modificado de rand() puede reenviarse de un hilo a otro. Pero probablemente lo limite a solo unos pocos hilos paralelos. Sin dependencias, podría ejecutar esto en tantos núcleos como tuviera disponibles.

Si está realmente interesado en este tema y no le importa tamizado a través de trabajos de investigación:

1. Automatic thread extraction with decoupled software pipelining (2005) por G. Ottoni.
2. Speculative parallelization using software multi-threaded transactions (2010) por A. Raman.

Answer 5

Es ciertamente posible, pero es una tarea increíblemente difícil. Este ha sido el impulso central de la investigación del compilador durante varias décadas. El problema básico es que no podemos crear una herramienta que pueda encontrar la mejor partición en hilos para el código java (esto es equivalente al problema de detención).

En su lugar, tenemos que relajar nuestro objetivo de la mejor partición en alguna partición del código. Esto todavía es muy difícil en general. Entonces, necesitamos encontrar formas de simplificar el problema, uno es olvidarse del código general y comenzar a buscar tipos específicos de programas. Si tiene un flujo de control simple (bucles foráneos con límites constantes, bifurcaciones limitadas ...) entonces puede hacer mucho más camino directo.

Otra simplificación es reducir la cantidad de unidades paralelas que intenta mantener ocupadas. Si junta estas dos simplificaciones, obtendrá el estado de la técnica en vectorización automática (un tipo específico de paralelización que se utiliza para generar código de estilo MMX/SSE). Llegar a esa etapa ha llevado décadas, pero si nos fijamos en compiladores como el de Intel, entonces el rendimiento está empezando a ser bastante bueno.

Si pasa de las instrucciones vectoriales dentro de una única hebra a varias hebras dentro de un proceso, entonces tiene un gran aumento en la latencia moviendo datos entre los diferentes puntos en el código. Esto significa que su paralelismo tiene que ser mucho mejor para ganar contra la sobrecarga de comunicación. Actualmente este es un tema candente en la investigación, pero no hay herramientas automáticas dirigidas por el usuario disponibles. Si puedes escribir uno que funcione, sería muy interesante para muchas personas.

Para su ejemplo específico, si supone que rand() es una versión paralela para que pueda llamarlo independientemente desde diferentes subprocesos, entonces es bastante fácil ver que el código se puede dividir en dos.Un compilador convertiría solo necesita análisis de dependencia para ver que ninguno de los bucles utiliza datos de, o afecta al otro. Entonces, el orden entre ellos en el código de nivel de usuario es una dependencia falsa que podría dividirse (es decir, poniendo cada uno en un hilo separado).

Pero esta no es realmente la forma en que desearía paralelizar el código. Parece que cada iteración de bucle depende de la anterior ya que sum1 + = rand (100) es lo mismo que sum1 = suma1 + rand (100) donde la suma1 en el lado derecho es el valor de la iteración anterior. Sin embargo, la única operación involucrada es la suma, que es asociativa, por lo que reescribimos la suma de muchas maneras diferentes.

sum1 = (((rand_0 + rand_1) + rand_2) + rand_3) .... 
sum1 = (rand_0 + rand_1) + (rand_2 + rand_3) ... 

La ventaja de la segunda es que cada adición entre corchetes se puede calcular en paralelo a todos los demás. Una vez que tengas 50 resultados, entonces se pueden combinar en otras 25 adiciones, y así sucesivamente ... Trabajas más de esta manera 50 + 25 + 13 + 7 + 4 + 2 + 1 = 102 adiciones versus 100 en el original pero hay son solo 7 pasos secuenciales, por lo tanto, aparte de la sobrecarga de bifurcación/unión paralela y de comunicación, se ejecuta 14 veces más rápido. Este árbol de adiciones se llama operación de recopilación en arquitecturas paralelas y tiende a ser la parte costosa de un cálculo.

En una arquitectura muy paralela, como una GPU, la descripción anterior sería la mejor forma de paralelizar el código. Si está utilizando subprocesos dentro de un proceso, la sobrecarga los matará.

En resumen: es imposible hacerlo a la perfección, es muy difícil hacerlo bien, hay mucha investigación activa para descubrir cuánto podemos hacer.

Answer 6

El lenguaje de programación es Java y Java es una máquina virtual. Entonces, ¿no debería uno poder ejecutar el código en tiempo de ejecución en diferentes subprocesos propiedad de la máquina virtual? Dado que toda la memoria, etc. se maneja de esa manera, no causaría ningún daño. Podrías ver el Código como una pila de instrucciones que estiman el Tiempo de ejecución y luego distribuirlo en una Matriz de hilos, cada una de las cuales tiene una pila de ejecución exactamente al mismo tiempo. Puede ser peligroso, aunque algunos gráficos como el modo inmediato de OpenGL necesitan mantener el orden y, en su mayoría, no deben enhebrarse en absoluto.