La paralelización automática , también paralelización automática o autoparalelización, se refiere a la conversión de código secuencial en código multiproceso y/o vectorizado para utilizar varios procesadores simultáneamente en una máquina multiprocesador de memoria compartida ( SMP ). [1] La paralelización completamente automática de programas secuenciales es un desafío porque requiere un análisis de programa complejo y el mejor enfoque puede depender de valores de parámetros que no se conocen en el momento de la compilación. [2]
Las estructuras de control de programación en las que la autoparalelización pone más atención son los bucles , porque, en general, la mayor parte del tiempo de ejecución de un programa tiene lugar dentro de algún tipo de bucle. Hay dos enfoques principales para la paralelización de bucles: subprocesos múltiples canalizados y subprocesos múltiples cíclicos. [3] Por ejemplo, considere un bucle que en cada iteración aplica cien operaciones y se ejecuta durante mil iteraciones. Esto se puede considerar como una cuadrícula de 100 columnas por 1000 filas, un total de 100.000 operaciones. El subproceso múltiple cíclico asigna cada fila a un subproceso diferente. El subproceso múltiple canalizado asigna cada columna a un subproceso diferente.
Esta es la primera etapa en la que el escáner leerá los archivos fuente de entrada para identificar todos los usos estáticos y externos. Cada línea del archivo se comparará con patrones predefinidos para segregarla en tokens . Estos tokens se almacenarán en un archivo que el motor gramatical utilizará más adelante. El motor gramatical verificará patrones de tokens que coincidan con reglas predefinidas para identificar variables, bucles, declaraciones de control, funciones, etc. en el código.
El analizador se utiliza para identificar secciones de código que se pueden ejecutar simultáneamente. El analizador utiliza la información de datos estáticos proporcionada por el analizador-escáner. El analizador primero encontrará todas las funciones totalmente independientes y las marcará como tareas individuales. Luego, el analizador encuentra qué tareas tienen dependencias.
El programador enumerará todas las tareas y sus dependencias entre sí en términos de ejecución y tiempos de inicio. El programador producirá el programa óptimo en términos de número de procesadores a utilizar o el tiempo total de ejecución de la aplicación.
El programador generará una lista de todas las tareas y los detalles de los núcleos en los que se ejecutarán junto con el tiempo durante el cual se ejecutarán. El generador de código insertará construcciones especiales en el código que el programador leerá durante la ejecución. Estas construcciones indicarán al programador en qué núcleo se ejecutará una tarea en particular junto con las horas de inicio y finalización.
Un compilador paralelizador cíclico de subprocesos múltiples intenta dividir un bucle para que cada iteración pueda ejecutarse en un procesador separado al mismo tiempo.
El compilador normalmente realiza dos pases de análisis antes de la paralelización real para determinar lo siguiente:
La primera pasada del compilador realiza un análisis de dependencia de datos del bucle para determinar si cada iteración del bucle se puede ejecutar independientemente de las demás. A veces se puede solucionar la dependencia de los datos, pero puede generar una sobrecarga adicional en forma de paso de mensajes , sincronización de la memoria compartida o algún otro método de comunicación del procesador.
El segundo paso intenta justificar el esfuerzo de paralelización comparando el tiempo de ejecución teórico del código después de la paralelización con el tiempo de ejecución secuencial del código. De manera algo contradictoria, el código no siempre se beneficia de la ejecución paralela. La sobrecarga adicional que puede asociarse con el uso de múltiples procesadores puede afectar la posible aceleración del código paralelizado.
Un bucle se llama DOALL si todas sus iteraciones, en cualquier invocación determinada, se pueden ejecutar simultáneamente.
El siguiente código de Fortran es DOALL y un compilador puede paralelizarlo automáticamente porque cada iteración es independiente de las demás y el resultado final de la matriz zserá correcto independientemente del orden de ejecución de las otras iteraciones.
hacer i = 1 , n z ( i ) = x ( i ) + y ( i ) enddo Hay muchos problemas agradablemente paralelos que tienen bucles DOALL de este tipo. Por ejemplo, al renderizar una película con trazado de rayos, cada fotograma de la película se puede renderizar de forma independiente y cada píxel de un único fotograma se puede renderizar de forma independiente.
Por otro lado, el siguiente código no se puede paralelizar automáticamente porque el valor de z(i)depende del resultado de la iteración anterior z(i - 1).
hacer i = 2 , n z ( i ) = z ( i - 1 ) * 2 enddo Esto no significa que el código no pueda paralelizarse. De hecho, es equivalente al bucle DOALL.
hacer i = 2 , n z ( i ) = z ( 1 ) * 2 ** ( i - 1 ) enddo Sin embargo, los compiladores de paralelización actuales generalmente no son capaces de generar estos paralelismos automáticamente, y es cuestionable si este código se beneficiaría de la paralelización en primer lugar.
Un compilador paralelizador multiproceso intenta dividir la secuencia de operaciones dentro de un bucle en una serie de bloques de código, de modo que cada bloque de código pueda ejecutarse en procesadores separados al mismo tiempo.
Hay muchos problemas agradablemente paralelos que tienen bloques de código relativamente independientes, en particular sistemas que utilizan tuberías y filtros .
Por ejemplo, al producir televisión en vivo, las siguientes tareas deben realizarse muchas veces por segundo:
Un compilador paralelizador de subprocesos múltiples canalizado podría asignar cada una de estas seis operaciones a un procesador diferente, tal vez organizado en una matriz sistólica , insertando el código apropiado para reenviar la salida de un procesador al siguiente procesador.
Investigaciones recientes se centran en utilizar la potencia de las GPU [4] y los sistemas multinúcleo [5] para calcular dichos bloques de código independientes (o simplemente iteraciones independientes de un bucle) en tiempo de ejecución. La memoria a la que se accede (ya sea directa o indirecta) se puede marcar simplemente para diferentes iteraciones de un bucle y se puede comparar para detectar dependencias. Utilizando esta información, las iteraciones se agrupan en niveles de modo que las iteraciones que pertenecen al mismo nivel sean independientes entre sí y puedan ejecutarse en paralelo.
La paralelización automática mediante compiladores o herramientas es muy difícil debido a las siguientes razones: [6]
Debido a las dificultades inherentes a la paralelización totalmente automática, existen varios enfoques más sencillos para obtener un programa paralelo de mayor calidad. Uno de ellos es permitir a los programadores agregar "sugerencias" a sus programas para guiar la paralelización del compilador, como HPF para sistemas de memoria distribuida y OpenMP u OpenHMPP para sistemas de memoria compartida . Otro enfoque es construir un sistema interactivo entre programadores y herramientas/compiladores de paralelización. Ejemplos notables son Pareon de Vector Fabrics , SUIF Explorer (el compilador de formato intermedio de la Universidad de Stanford), el compilador Polaris y ParaWise (formalmente CAPTools). Finalmente, otro enfoque es el multiproceso especulativo soportado por hardware .
La mayoría de los compiladores de investigación para la paralelización automática consideran los programas Fortran , [ cita necesaria ] porque Fortran ofrece garantías más sólidas sobre el alias que lenguajes como C. Ejemplos típicos son: