Paralelización automática

Este artículo necesita citas adicionales para su verificación . Por favor, ayude a mejorar este artículo añadiendo citas de fuentes fiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Paralelización automática» – noticias  · periódicos  · libros  · académico  · JSTOR ( febrero de 2008 ) ( Aprenda cómo y cuándo eliminar este mensaje )

La paralelización automática , también autoparalelización o autoparalelización , se refiere a la conversión de código secuencial en código multiproceso y/o vectorizado para utilizar múltiples 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 complejo del programa 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 énfasis son los bucles , porque, en general, la mayor parte del tiempo de ejecución de un programa tiene lugar dentro de alguna forma de bucle. Hay dos enfoques principales para la paralelización de bucles: multihilo segmentado y multihilo cíclico. ^[3] Por ejemplo, considere un bucle que en cada iteración aplica cien operaciones y se ejecuta durante mil iteraciones. Esto puede considerarse 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.

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 separarlos en tokens . Estos tokens se almacenarán en un archivo que luego utilizará el motor gramatical. El motor gramatical comprobará los patrones de tokens que coincidan con las 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-analizador. 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 tiempos de ejecución e inicio. El programador generará el cronograma óptimo en términos de cantidad de procesadores a utilizar o 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 le 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 de subprocesos múltiples cíclicos intenta dividir un bucle para que cada iteración pueda ejecutarse en un procesador separado simultáneamente.

El compilador normalmente realiza dos pasadas de análisis antes de la paralelización real para determinar lo siguiente:

• ¿Es seguro paralelizar el bucle? Para responder a esta pregunta es necesario realizar un análisis de dependencia y un análisis de alias precisos.
• ¿Vale la pena paralelizar? Esta respuesta requiere una estimación (modelado) confiable 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 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 datos, pero puede generar una sobrecarga adicional en forma de paso 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 teórico de ejecución del código después de la paralelización con el tiempo de ejecución secuencial del código. De manera un tanto contraintuitiva, el código no siempre se beneficia de la ejecución en paralelo. La sobrecarga adicional que puede asociarse con el uso de múltiples procesadores puede reducir la aceleración potencial del código paralelizado.

Un bucle se llama DOALL si todas sus iteraciones, en cualquier invocación dada, pueden ejecutarse simultáneamente.

El código Fortran 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 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 ) findo         

Existen muchos problemas agradablemente paralelos que tienen este tipo de 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 único fotograma se puede renderizar de forma independiente.

Por otro lado, el siguiente código no se puede autoparalelizar, 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 findo         

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 ) findo         

Sin embargo, los compiladores paralelizadores actuales normalmente 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 multihilo canalizado 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 simultáneamente.

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 una transmisión televisiva en vivo, las siguientes tareas deben realizarse muchas veces por segundo:

1. Leer un cuadro de datos de píxeles sin procesar del sensor de imagen,
2. ¿Realizar una compensación de movimiento MPEG en los datos sin procesar?
3. La entropía comprime los vectores de movimiento y otros datos.
4. Divida los datos comprimidos en paquetes,
5. Agregue la corrección de errores adecuada y realice una FFT para convertir los paquetes de datos en señales COFDM , y
6. Envía las señales COFDM a la antena de TV.

Un compilador paralelizador multihilo canalizado podría asignar cada una de estas seis operaciones a un procesador diferente, quizás organizado en una matriz sistólica , insertando el código apropiado para reenviar la salida de un procesador al siguiente.

Las investigaciones recientes se centran en el uso de la potencia de las GPU ^[4] y de 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 de forma directa o indirecta) se puede marcar de forma sencilla para diferentes iteraciones de un bucle y se puede comparar para detectar dependencias. Con esta información, las iteraciones se agrupan en niveles de modo que las iteraciones que pertenecen al mismo nivel sean independientes entre sí y se puedan ejecutar en paralelo.

La paralelización automática mediante compiladores o herramientas es muy difícil debido a las siguientes razones: ^[6]

• El análisis de dependencia es difícil para el código que utiliza direccionamiento indirecto, punteros, recursión o llamadas de función indirectas porque es difícil detectar dichas dependencias en tiempo de compilación;
• los bucles tienen un número desconocido de iteraciones;
• Los accesos a 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]

Debido a las dificultades inherentes a la paralelización automática completa, existen varios enfoques más sencillos para obtener un programa paralelo de mayor calidad. Uno de ellos es permitir que los programadores agreguen "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 es construir un sistema interactivo entre programadores y herramientas/compiladores de paralelización. Algunos 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 multithreading especulativo soportado por hardware .

La mayoría de los compiladores de investigación para la paralelización automática consideran los programas Fortran , ^{[ cita requerida ]} 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 Fortran D de Rice
• Compilador SUIF
• Compilador Fortran de Viena

• Optimización de anidación de bucles
• Contrato de paralelización
• Modelo politópico también conocido como modelo poliédrico
• Paralelismo escalable
• FMBM
• Vectorización
• SecuenciaL

• Pountain, Dick (diciembre de 1989). «Configuración de programas paralelos, parte 1: el transpilador de Occam, actualmente en desarrollo, facilitará la escritura de software para el procesamiento paralelo». BYTE . Vol. 14, núm. 13. McGraw-Hill, Inc. pp. 349–352. ISSN  0360-5280. ark:/13960/t34188734 . Consultado el 6 de enero de 2022 .(NB. Utiliza el término transpilador de Occam como sinónimo de un compilador de fuente a fuente que funciona como un preprocesador que toma un programa Occam normal como entrada y deriva un nuevo código fuente de Occam como salida con asignaciones de enlace a canal, etc. agregados, configurándolo así para que el procesamiento paralelo se ejecute de la manera más eficiente posible en una red de transputadores ).