Paralelización automática , también paralelización automática , o autoparallelization se refiere a la conversión secuencial código en multi-hilo y / o vectorizado código con el fin de utilizar varios procesadores simultáneamente en una memoria compartida multiprocesador ( SMP máquina). [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 autoparalización se centra más 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 en canalización 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.
Técnica de paralelización automática
Analizar gramaticalmente
Esta es la primera etapa en la que el escáner leerá los archivos de origen de entrada para identificar todos los usos estáticos y externos. Cada línea del archivo se comparará con patrones predefinidos para segregar en tokens . Estos tokens se almacenarán en un archivo que luego será utilizado por el motor gramatical. 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.
Analizar
El analizador se utiliza para identificar secciones de código que se pueden ejecutar al mismo tiempo. 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.
Calendario
El programador enumerará todas las tareas y sus dependencias entre sí en términos de ejecución y horas de inicio. El programador producirá la programación óptima en términos de la cantidad de procesadores que se utilizarán o el tiempo total de ejecución de la aplicación.
Codigo de GENERACION
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 que 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 le indicarán al programador en qué núcleo se ejecutará una tarea en particular junto con las horas de inicio y finalización.
Multi-hilo cíclico
Un compilador de paralelización cíclico de subprocesos múltiples intenta dividir un bucle para que cada iteración se pueda ejecutar en un procesador separado al mismo tiempo.
Análisis de paralelización del compilador
El compilador generalmente realiza dos pasos de análisis antes de la paralelización real para determinar lo siguiente:
- ¿Es seguro paralelizar el bucle? Responder a esta pregunta necesita un análisis de dependencia y un análisis de alias precisos
- ¿Vale la pena paralelizarlo? Esta respuesta requiere una estimación confiable (modelado) de la carga de trabajo del programa y la capacidad del sistema paralelo.
El primer paso del compilador realiza un análisis de dependencia de datos del ciclo para determinar si cada iteración del ciclo se puede ejecutar independientemente de las demás. A veces se puede tratar la dependencia de datos, pero puede incurrir en gastos generales adicionales en forma de transmisión de mensajes , sincronización de 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. Algo contrario a la intuición, el código no siempre se beneficia de la ejecución paralela. La sobrecarga adicional que se puede asociar con el uso de múltiples procesadores puede afectar la posible aceleración del código paralelizado.
Ejemplo
Un bucle se llama DOALL si todas sus iteraciones, en cualquier invocación, se pueden ejecutar al mismo tiempo. El código de Fortran a continuación 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 z
será correcto independientemente del orden de ejecución de las otras iteraciones.
hacer yo = 1 , n z ( i ) = x ( i ) + y ( i ) enddo
Hay muchos problemas agradablemente paralelos que tienen tales bucles DOALL. 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 solo fotograma se puede renderizar de forma independiente.
Por otro lado, el siguiente código no puede ser auto-parallelized, porque el valor de z(i)
depende del resultado de la iteración anterior, z(i - 1)
.
hacer yo = 2 , n z ( i ) = z ( i - 1 ) * 2 enddo
Esto no significa que el código no se pueda paralelizar. De hecho, es equivalente a
hacer i = 2 , n z ( i ) = z ( 1 ) * 2 ** ( i - 1 ) enddo
Sin embargo, los compiladores de paralelización actuales no suelen ser capaces de generar estos paralelismos automáticamente, y es cuestionable si este código se beneficiaría de la paralelización en primer lugar.
Subprocesos múltiples canalizados
Un compilador de paralelización de subprocesos múltiples en cadena 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 se pueda ejecutar 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, cuando se produce una transmisión televisiva en vivo, las siguientes tareas deben realizarse muchas veces por segundo:
- Leer un cuadro de datos de píxeles sin procesar del sensor de imagen,
- Haga compensación de movimiento MPEG en los datos brutos,
- La entropía comprime los vectores de movimiento y otros datos,
- Divida los datos comprimidos en paquetes,
- Agregue la corrección de errores apropiada y haga una FFT para convertir los paquetes de datos en señales COFDM , y
- Envíe las señales COFDM a través de la antena de TV.
Un compilador de paralelización multiproceso interconectado podría asignar cada una de estas 6 operaciones a un procesador diferente, quizás dispuesto en una matriz sistólica , insertando el código apropiado para enviar la salida de un procesador al siguiente procesador.
La investigación reciente se centra en el uso de la potencia de las GPU [4] y los sistemas multinúcleo [5] para calcular esos 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 la detección de dependencia. Con esta información, las iteraciones se agrupan en niveles de modo que las iteraciones que pertenecen al mismo nivel son independientes entre sí y se pueden ejecutar en paralelo.
Dificultades
La paralelización automática mediante compiladores o herramientas es muy difícil debido a las siguientes razones: [6]
- El análisis de dependencias es difícil para el código que usa direccionamiento indirecto, punteros, recursividad o llamadas a funciones indirectas porque es difícil detectar tales dependencias en tiempo de compilación;
- los bucles tienen un número desconocido de iteraciones;
- los accesos a los recursos globales son difíciles de coordinar en términos de asignación de memoria, E / S y variables compartidas;
- Los algoritmos irregulares que utilizan indirección dependiente de la entrada interfieren con el análisis y la optimización en tiempo de compilación. [7]
Solución alterna
Debido a las dificultades inherentes a la paralelización automática completa, existen varios enfoques más fáciles 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 (compilador de formato intermedio de la Universidad de Stanford), compilador de Polaris y ParaWise (formalmente CAPTools). Finalmente, otro enfoque es el multiproceso especulativo soportado por hardware .
Paralelizar compiladores y herramientas
La mayoría de la investigación compiladores para la paralelización automática consideran Fortran programas, [ cita requerida ] , porque Fortran hace mayores garantías sobre aliasing de lenguajes como C . Ejemplos típicos son:
- Compilador de paradigmas
- Compilador de Polaris
- Compilador Rice Fortran D
- Compilador SUIF
- Compilador de Viena Fortran
Ver también
- Optimización del nido de bucles
- Modelo politopo
- Paralelismo escalable
- BMDFM
- Vectorización
- SecuenciaL
Referencias
- ^ " Yehezkael, Rafael (2000)." Experimentos en la separación del algoritmo computacional de la distribución de programas y la comunicación ". Notas de la conferencia en Ciencias de la Computación de Springer Verlag . Notas de la Conferencia en Ciencias de la Computación. 1947 : 268-278. Doi : [// doi. org / 10.1007% 2F3-540-70734-4_32 10.1007 / 3-540-70734-4_32. ISBN 978-3-540-41729-3."]
- ^ Fox, Geoffrey; Roy Williams; Paul Messina (1994). ¡La Computación Paralela funciona! . Morgan Kaufmann. págs. 575, 593. ISBN 978-1-55860-253-3.
- ^ Simone Campanoni, Timothy Jones, Glenn Holloway, Gu-Yeon Wei, David Brooks. "El proyecto HELIX: descripción general y direcciones" . 2012.
- ^ J Anantpur, R Govindarajan, Cálculo de dependencia en tiempo de ejecución y ejecución de bucles en sistemas heterogéneos "Copia archivada" (PDF) . Archivado desde el original (PDF) el 6 de octubre de 2015 . Consultado el 5 de octubre de 2015 .CS1 maint: copia archivada como título ( enlace )
- ^ X. Zhuang, AE Eichenberger, Y. Luo, Kevin O'Brien, Kathryn, Explotación del paralelismo con programación consciente de la dependencia
- ^ "Paralelismo automático y dependencia de datos" . Archivado desde el original el 14 de julio de 2014.
- ^ Rünger, Gudula (2006). "Modelos de programación paralela para algoritmos irregulares". Algoritmos paralelos y computación en clúster . Apuntes de clase en Ciencias e Ingeniería Computacionales. 52 : 3-23. doi : 10.1007 / 3-540-33541-2_1 . ISBN 978-3-540-33539-9.