Paralelización automática
Paralelización automática, también auto paralelización, autoparalelización, o paralelización, se refiere a convertir código secuencial en multihilo o vectorizado (o los dos) con objeto de utilizar múltiples procesadores simultáneamente en una máquina con multiprocesador (SMP) de memoria compartida. La utilidad de la paralelización automática es liberar a los programadores del proceso tedioso y tendente a errores de la paralelización manual. Aunque la calidad de la automatización paralela ha mejorado en las últimas décadas, una paralelización automática completa de programas secuenciales por un compilador sigue siendo un gran reto, ya que necesita de un complejo análisis informático, y a los factores desconocidos(como el rango de los datos de entrada) durante la compilación.[1]
Las estructuras de control de programación en las que la autoparalelización se centra son los bucles, ya que, en general, la mayor parte del tiempo de ejecución de un programa tiene lugar en el interior de algún bucle. Un compilador paralelo intenta dividir un bucle de forma que sus iteraciones puedan ser ejecutadas en microprocesadores separados de forma concurrente.
Análisis de la compilación paralela
El compilador realiza normalmente dos ciclos de análisis antes de una paralelización para determinar lo siguiente:
- ¿Es seguro paralelizar el bucle? La respuesta a esta pregunta requiere un preciso análisis de dependencias y análisis de alias.
- ¿Merece la pena pralelizarlo? Esta respuesta requiere una estimación fiable (modelado) de la carga de trabajo del programa y de la capacidad del sistema paralelo.
En el primer paso el compilador realiza un análisis de dependencias del bucle para determinar si cada iteración del bucle puede ejecutarse de forma independiente a las demás. La dependencia de datos puede tratarse a veces mediante paso de mensajes, sincronización de memoria compartida, o algún otro método de comunicación entre procesadores, pero puede incrementar la sobrecarga.
El segundo paso intenta justificar el esfuerzo de paralelización, comparando el tiempo teórico de ejecución del código paralelizado con el tiempo de ejecución del código secuencial. Aunque parece contraproducente, el código no siempre se beneficia de la ejecución paralela. La carga de trabajo extra que se puede asociar al uso de múltiples procesadores puede anular el posible incremento de velocidad de ejecución del código paralelo.
Ejemplo
El código Fortran que aparece a continuación puede ser auto-paralelizado por un compilador porque cada iteración es independiente de las demás, y el resultado final del vector z será correcto independientemente del orden de ejecución de las iteraciones.
do i=1, n z(i) = x(i) + y(i) enddo Por otro lado, el siguiente código no puede ser auto-paralelizado, porque el valor de z(i) depende del resultado de la iteración anterior, z(i-1).
do i=2, n z(i) = z(i-1)*2 enddo Esto no significa que no pueda ser paralelizado. De hecho, es equivalente a
do i=2, n z(i) = z(1)*2**(i-1) enddo Sin embargo, los compiladores paralelos actuales no son capaces de conseguir estas paralelizaciones de forma automática, y es cuestionable que este código pueda beneficiarse de la paralelización.
Dificultades
La paralelización automática de los compiladores o herramientas es muy compleja debido a las siguientes causas:
- el análisis de dependencias es muy complejo para el código que utiliza direccionamiento indirecto, punteros, recursividad, y llamadas indirectas a funciones;
- los bucles tienen un número indeterminado de iteraciones;
- los accesos a recursos globales son difíciles de coordinar en términos de reserva de memoria, E/S, y variables compartidas.
Soluciones
Debido a las dificultades inherentes a la paralelización automática completa, existen varias aproximaciones más sencillas para conseguir un programa paralelo de más calidad, como son:
- Permitir a los programadores añadir "pistas" a sus programas para guiar al compilador en la paralelización, como HPF para sistemas de memoria distribuida y OpenMP o OpenHMPP para sistemas de memoria compartida.
- Construir un sistema interactivo entre los programadores y las herramientas que realizan la paralelización. Algunos ejemplos notables son Vector Fabrics' vfAnalyst, SUIF Explorer (El compilador de formato intermedio de la Universidad de Stanford), el compilador Polaris, y ParaWise (formalmente CAPTools).
- speculative multithreading soportado por hardware.
Compiladores paralelos históricos
La mayoría de las investigadores en compiladores para la paralelización automática prefieren los programas Fortran,[cita requerida] porque Fortran ofrece mayores garantías sobre aliasing que otros lenguajes como C. Ejemplos típicos son:
- Rice Fortran D compiler
- Vienna Fortran compiler
- Paradigm compiler
- Polaris compiler
- SUIF compiler
Véase también
- Optimización de bucles anidados
- Modelo Polytope
- Paralelismo escalable
Referencias
- Fox, Geoffrey; Roy Williams, Giuseppe Messina (1994). Parallel Computing Works!. Morgan Kaufmann. pp. 575,593. ISBN 978-1558602533.