Hispanopedia WikiLa paralelización automática , también llamada autoparalelización , se refiere a la conversión de código secuencial en código multihilo y/o vectorizado para utilizar varios procesadores simultáneamente en una máquina multiprocesador de memoria compartida ( SMP ). [ 1 ] La paralelización totalmente automática de programas secuenciales es un desafío porque requiere un análisis complejo del programa y el mejor enfoque puede depender de valores de parámetros que no se conocen en tiempo de compilación. [ 2 ]
Las estructuras de control de programación en las que la autoparalelización pone mayor énfasis son los bucles , porque, en general, la mayor parte del tiempo de ejecución de un programa se produce dentro de algún tipo de bucle. Hay dos enfoques principales para la paralelización de bucles: multihilo segmentado y multihilo cíclico. [ 3 ] Por ejemplo, consideremos un bucle que en cada iteración aplica cien operaciones y se ejecuta durante mil iteraciones. Esto puede pensarse como una cuadrícula de 100 columnas por 1000 filas, un total de 100 000 operaciones. El multihilo cíclico asigna cada fila a un hilo diferente. El multihilo segmentado asigna cada columna a un hilo diferente.
Técnica de paralelización automática
Analizar gramaticalmente
Esta es la primera etapa, donde 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 separarla en tokens . Estos tokens se almacenarán en un archivo que el motor de gramática utilizará posteriormente. El motor de gramática verificará los patrones de tokens que coincidan con las reglas predefinidas para identificar variables, bucles, sentencias de control, funciones, etc., en el código.
Analizar
El analizador se utiliza para identificar secciones de código que pueden ejecutarse simultáneamente. El analizador utiliza la información de datos estáticos proporcionada por el analizador sintáctico. Primero, el analizador encontrará todas las funciones totalmente independientes y las marcará como tareas individuales. Luego, el analizador determinará qué tareas tienen dependencias.
Cronograma
El planificador mostrará todas las tareas y sus dependencias entre sí en términos de tiempos de ejecución e inicio. El planificador generará la planificación óptima en función del número de procesadores a utilizar o del tiempo total de ejecución de la aplicación.
Generación de código
El planificador generará una lista de todas las tareas y los detalles de los núcleos en los que se ejecutarán, junto con el tiempo de ejecución. El generador de código insertará construcciones especiales que el planificador leerá durante la ejecución. Estas construcciones indicarán al planificador en qué núcleo se ejecutará cada tarea, así como sus horas de inicio y finalización.
Multihilo cíclico
Un compilador de paralelización multihilo cíclico intenta dividir un bucle para que cada iteración pueda ejecutarse simultáneamente en un procesador independiente.
Análisis de paralelización de compiladores
El compilador suele realizar dos pasadas de análisis antes de la paralelización propiamente dicha para determinar lo siguiente:
- ¿Es seguro paralelizar el bucle? Para responder a esta pregunta se necesita un análisis preciso de dependencias y un análisis de alias.
- ¿Merece la pena paralelizarlo? Para responder a esta pregunta, se requiere una estimación fiable (modelado) de la carga de trabajo del programa y de la capacidad del sistema paralelo.
La primera pasada del compilador realiza un análisis de dependencia de datos del bucle para determinar si cada iteración puede ejecutarse independientemente de las demás. En ocasiones, se puede gestionar la dependencia de datos, pero esto puede generar una sobrecarga adicional en forma de paso de mensajes , sincronización de memoria compartida u otro método de comunicación del procesador.
La segunda fase intenta justificar el esfuerzo de paralelización comparando el tiempo de ejecución teórico del código tras la paralelización con su tiempo de ejecución secuencial. Aunque parezca contraintuitivo, el código no siempre se beneficia de la ejecución en paralelo. La sobrecarga adicional que puede conllevar el uso de múltiples procesadores puede reducir la posible aceleración del código paralelizado.
Ejemplo
Un bucle se denomina DOALL si todas sus iteraciones, en una invocación determinada, pueden ejecutarse simultáneamente.
El código Fortran que aparece a continuación es DOALL y puede ser paralelizado automáticamente por un compilador porque cada iteración es independiente de las demás, y el resultado final del array zserá correcto independientemente del orden de ejecución de las otras iteraciones.
hacer i = 1 , n z ( i ) = x ( i ) + y ( i ) fin hacerExisten muchos problemas paraleles que presentan bucles DOALL. Por ejemplo, al renderizar una película mediante trazado de rayos, cada fotograma se puede renderizar de forma independiente, y cada píxel de un solo fotograma también 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 fin hacerEsto 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 ) fin hacerSin embargo, los compiladores de paralelización actuales no suelen ser capaces de aprovechar estos paralelismos automáticamente, y es cuestionable si este código se beneficiaría de la paralelización en primer lugar.
Multiprocesamiento en paralelo
Un compilador de paralelización multihilo segmentado intenta dividir la secuencia de operaciones dentro de un bucle en una serie de bloques de código, de manera que cada bloque de código pueda ejecutarse simultáneamente en procesadores separados.
Existen 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 programas de televisión en directo, se deben realizar las siguientes tareas muchas veces por segundo:
- Lee un fotograma de datos de píxeles sin procesar del sensor de imagen,
- Realizar compensación de movimiento MPEG en los datos sin procesar,
- 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 realice una FFT para convertir los paquetes de datos en señales COFDM , y
- Envía las señales COFDM a través de la antena de televisión.
Un compilador paralelizador multihilo segmentado 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.
Investigaciones recientes se centran en aprovechar la potencia de las GPU [ 4 ] y los sistemas multinúcleo [ 5 ] para calcular 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 de forma directa o indirecta) se puede marcar para las diferentes iteraciones de un bucle y comparar para detectar dependencias. Con esta información, las iteraciones se agrupan en niveles, de modo que las iteraciones de un mismo nivel son independientes entre sí y se pueden ejecutar en paralelo.
Dificultades
La paralelización automática por parte de 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 utiliza direccionamiento indirecto, punteros, recursión o llamadas a funciones indirectas porque es difícil detectar dichas dependencias en tiempo de compilación;
- Los bucles tienen un número desconocido de iteraciones;
- El acceso a los recursos globales es difícil 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 alternativa
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 consiste en permitir que los programadores añadan "pistas" 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 consiste en crear 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 (anteriormente CAPTools). Por último, otro enfoque es el multihilo especulativo con soporte de hardware .
Compiladores y herramientas de paralelización
La mayoría de los compiladores de investigación para la paralelización automática consideran los programas Fortran , porque Fortran ofrece garantías más sólidas sobre el aliasing que lenguajes como C. Algunos ejemplos típicos son:
- compilador de paradigmas
- Compilador Polaris
- Compilador Rice Fortran D
- compilador SUIF
- Compilador Fortran de Viena
Aubert, Rubiano, Rusch y Seiller [ 8 ] utilizaron una técnica de análisis de dependencias [ 9 ] para paralelizar automáticamente los bucles en programas C.
Véase también
- Optimización de bucles anidados
- contrato de paralelización
- Modelo politópico, también conocido como modelo poliédrico.
- Paralelismo escalable
- Máquina de flujo de datos modular binaria (BMDFM)
- Vectorización automática
- SecuenciaL
Referencias
- ↑ Yehezkael, Rafael (2000). "Experimentos para separar el algoritmo computacional de la distribución y comunicación del programa" (PDF) . Computación paralela aplicada. Nuevos paradigmas para la computación de alto rendimiento en la industria y la academia . Notas de clase en ciencias de la computación . Vol. 1947. Springer Verlag . págs. 268–278 . doi : 10.1007/3-540-70734-4_32 . ISBN 978-3-540-41729-3.
- ↑ Fox, Geoffrey; Williams, Roy; Messina, Paul (1994). ¡ La computación paralela funciona! Morgan Kaufmann . págs. 575, 593. ISBN 978-1-55860-253-3.
- ↑ Campanoni, Simone; Jones, Timothy; Holloway, Glenn; Wei, Gu-Yeon; Brooks, David (2012). El proyecto HELIX: descripción general y direcciones .
- ↑ Anantpur, J.; Govindarajan, R. "Cálculo de dependencia en tiempo de ejecución y ejecución de bucles en sistemas heterogéneos" (PDF) . Archivado del original (PDF) el 6 de octubre de 2015. Recuperado el 5 de octubre de 2015 .
- ↑ Zhuang, X.; Eichenberger, AE; Luo, Y.; O'Brien, Kathryn Kevin, Aprovechamiento del paralelismo con planificación basada en dependencias
- ↑ "Paralelismo automático y dependencia de datos" . Archivado del 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 . Notas de clase en ciencia e ingeniería computacional. 52 : 3–23 . doi : 10.1007/3-540-33541-2_1 . ISBN 978-3-540-33539-9.
- ↑ Aubert, Clément; Rubiano, Thomas; Rusch, Neea; Seiller, Thomas (2023). «Distribución y paralelización de bucles no canónicos». Verificación, comprobación de modelos e interpretación abstracta . Lecture Notes in Computer Science. Vol. 13881. pp. 91–108 . doi : 10.1007/978-3-031-24950-1_1 . ISBN 978-3-031-24949-5.
- ↑ Moyen, Jean-Yves; Rubiano, Thomas; Seiller, Thomas (2017). "Detección de fragmentos cuasi-invariantes de bucle". Tecnología automatizada para verificación y análisis . Notas de clase en informática. Vol. 10482. págs. 91–108 . doi : 10.1007/978-3-319-68167-2_7 . ISBN 978-3-319-68166-5.
Lecturas adicionales
- Pountain, Dick (diciembre de 1989). "Configuración de programas paralelos, Parte 1: El transpilador Occam, actualmente en desarrollo, facilitará la escritura de software para el procesamiento paralelo" . BYTE . Vol. 14, n.º 13. McGraw-Hill, Inc. págs. 349–352 . ISSN 0360-5280 . ark:/13960/t34188734 . Consultado el 6 de enero de 2022 . (Nota: Se utiliza el término transpilador Occam como sinónimo de un compilador de código fuente a código fuente que funciona como un preprocesador que toma un programa Occam normal como entrada y genera un nuevo código fuente Occam como salida, con asignaciones de enlace a canal, etc., añadidas, configurándolo así para el procesamiento paralelo y para que funcione de la forma más eficiente posible en una red de transcomputadores ).
- Optimizaciones del compilador
- Computación paralela
