La vectorización automática , en computación paralela , es un caso especial de paralelización automática , en el que un programa informático se convierte de una implementación escalar , que procesa un único par de operandos a la vez, a una implementación vectorial , que procesa una operación en varios pares de operandos a la vez. Por ejemplo, las computadoras convencionales modernas, incluidas las supercomputadoras especializadas , suelen tener operaciones vectoriales que realizan simultáneamente operaciones como las siguientes cuatro sumas (a través de hardware SIMD o SPMD ):
Sin embargo, en la mayoría de los lenguajes de programación, normalmente se escriben bucles que realizan sumas secuenciales de muchos números. A continuación, se muestra un ejemplo de un bucle de este tipo, escrito en C :
para ( i = 0 ; i < n ; i ++ ) c [ i ] = a [ i ] + b [ i ]; Un compilador vectorizador transforma dichos bucles en secuencias de operaciones vectoriales. Estas operaciones vectoriales realizan adiciones en bloques de elementos de las matrices a, by c. La vectorización automática es un tema de investigación importante en la ciencia informática. [ cita requerida ]
Las primeras computadoras solían tener una unidad lógica, que ejecutaba una instrucción en un par de operandos a la vez. Por lo tanto, los lenguajes y programas de computación estaban diseñados para ejecutarse en secuencia. Sin embargo, las computadoras modernas pueden hacer muchas cosas a la vez. Por eso, muchos compiladores optimizadores realizan una vectorización automática, en la que partes de programas secuenciales se transforman en operaciones paralelas.
La vectorización de bucles transforma los bucles procedimentales asignando una unidad de procesamiento a cada par de operandos. Los programas pasan la mayor parte de su tiempo dentro de estos bucles. Por lo tanto, la vectorización puede acelerarlos significativamente, especialmente en conjuntos de datos grandes. La vectorización de bucles se implementa en MMX , SSE y AVX de Intel , en AltiVec de Power ISA , en NEON , SVE y SVE2 de ARM y en los conjuntos de instrucciones Vector Extension de RISC-V .
Existen muchas restricciones que impiden o dificultan la vectorización. En ocasiones, la vectorización puede ralentizar la ejecución, por ejemplo, debido a la sincronización de la canalización o al tiempo de movimiento de datos. El análisis de dependencia de bucles identifica los bucles que se pueden vectorizar, basándose en la dependencia de los datos de las instrucciones dentro de los bucles.
La vectorización automática, como cualquier optimización de bucle u otra optimización en tiempo de compilación, debe preservar exactamente el comportamiento del programa.
Se deben respetar todas las dependencias durante la ejecución para evitar resultados incorrectos.
En general, las dependencias invariantes de bucle y las dependencias léxicas hacia delante se pueden vectorizar fácilmente, y las dependencias léxicas hacia atrás se pueden transformar en dependencias léxicas hacia delante. Sin embargo, estas transformaciones se deben realizar de forma segura, para garantizar que la dependencia entre todas las declaraciones se mantenga fiel al original.
Las dependencias cíclicas deben procesarse independientemente de las instrucciones vectorizadas.
La precisión de los enteros (tamaño de bit) debe mantenerse durante la ejecución de instrucciones vectoriales. La instrucción vectorial correcta debe elegirse en función del tamaño y el comportamiento de los enteros internos. Además, con tipos de enteros mixtos, se debe tener especial cuidado para promoverlos o degradarlos correctamente sin perder precisión. Se debe tener especial cuidado con la extensión de signo (porque varios enteros se empaquetan dentro del mismo registro) y durante las operaciones de desplazamiento u operaciones con bits de acarreo que de otro modo se tendrían en cuenta.
También se debe mantener la precisión de punto flotante , a menos que se desactive la compatibilidad con IEEE-754 , en cuyo caso las operaciones serán más rápidas pero los resultados pueden variar levemente. Las grandes variaciones, incluso si se ignora IEEE-754, generalmente significan un error del programador.
Para vectorizar un programa, el optimizador del compilador debe primero comprender las dependencias entre las instrucciones y realinearlas, si es necesario. Una vez que se asignan las dependencias, el optimizador debe organizar adecuadamente las instrucciones de implementación cambiando los candidatos apropiados por instrucciones vectoriales, que operan sobre múltiples elementos de datos.
El primer paso es construir el gráfico de dependencias , identificando qué declaraciones dependen de qué otras declaraciones. Esto implica examinar cada declaración e identificar cada elemento de datos al que accede la declaración, asignar modificadores de acceso a la matriz a funciones y verificar la dependencia de cada acceso con todos los demás en todas las declaraciones. El análisis de alias se puede utilizar para certificar que las diferentes variables acceden (o intersecan) la misma región en la memoria.
El gráfico de dependencias contiene todas las dependencias locales cuya distancia no es mayor que el tamaño del vector. Por lo tanto, si el registro del vector tiene 128 bits y el tipo de matriz es de 32 bits, el tamaño del vector es 128/32 = 4. Todas las demás dependencias no cíclicas no deberían invalidar la vectorización, ya que no habrá ningún acceso concurrente en la misma instrucción del vector.
Supongamos que el tamaño del vector es igual a 4 enteros:
para ( i = 0 ; i < 128 ; i ++ ) { a [ i ] = a [ i -16 ]; // 16 > 4, es seguro ignorar a [ i ] = a [ i -1 ]; // 1 < 4, permanece en el gráfico de dependencia } Utilizando el gráfico, el optimizador puede luego agrupar los componentes fuertemente conectados (SCC) y separar las declaraciones vectorizables del resto.
Por ejemplo, considere un fragmento de programa que contiene tres grupos de sentencias dentro de un bucle: (SCC1+SCC2), SCC3 y SCC4, en ese orden, en el que solo el segundo grupo (SCC3) puede ser vectorizado. El programa final contendrá entonces tres bucles, uno para cada grupo, con solo el del medio vectorizado. El optimizador no puede unir el primero con el último sin violar el orden de ejecución de las sentencias, lo que invalidaría las garantías necesarias.
Algunas dependencias no obvias se pueden optimizar aún más en función de modismos específicos.
Por ejemplo, las siguientes dependencias de datos propios se pueden vectorizar porque el valor de los valores de la derecha ( RHS ) se obtiene y luego se almacena en el valor de la izquierda, por lo que no hay forma de que los datos cambien dentro de la asignación.
a [ i ] = a [ i ] + a [ i + 1 ]; La autodependencia de los escalares se puede vectorizar mediante la eliminación de variables .
El marco general para la vectorización de bucles se divide en cuatro etapas:
Algunas vectorizaciones no se pueden comprobar por completo en tiempo de compilación. Por ejemplo, las funciones de biblioteca pueden anular la optimización si los datos que procesan son suministrados por el autor de la llamada. Incluso en estos casos, la optimización en tiempo de ejecución puede vectorizar bucles sobre la marcha.
Esta verificación en tiempo de ejecución se realiza en la etapa de preludio y dirige el flujo a instrucciones vectorizadas si es posible, de lo contrario vuelve al procesamiento estándar, dependiendo de las variables que se pasan en los registros o variables escalares.
El código siguiente se puede vectorizar fácilmente en tiempo de compilación, ya que no tiene ninguna dependencia de parámetros externos. Además, el lenguaje garantiza que ninguna de las dos ocupará la misma región en memoria que ninguna otra variable, ya que son variables locales y viven únicamente en la pila de ejecución .
int a [ 128 ]; int b [ 128 ]; // inicializar b para ( i = 0 ; i < 128 ; i ++ ) a [ i ] = b [ i ] + 5 ; Por otro lado, el código siguiente no tiene información sobre las posiciones de memoria, porque las referencias son punteros y la memoria a la que apuntan puede superponerse.
vacío calcular ( int * a , int * b ) { int i ; para ( i = 0 ; i < 128 ; i ++ , a ++ , b ++ ) * a = * b + 5 ; } Una rápida comprobación en tiempo de ejecución de la dirección de a y b , más el espacio de iteración del bucle (128) es suficiente para saber si las matrices se superponen o no, revelando así cualquier dependencia. (Tenga en cuenta que a partir de C99, calificar los parámetros con la palabra clave restrict (aquí: int *restrict a, int *restrict b) le dice al compilador que los rangos de memoria a los que apuntan a y b no se superponen, lo que lleva al mismo resultado que el ejemplo anterior).
Existen algunas herramientas para analizar dinámicamente las aplicaciones existentes para evaluar el potencial latente inherente para el paralelismo SIMD, explotable a través de mayores avances del compilador y/o mediante cambios manuales en el código. [1]
Un ejemplo sería un programa para multiplicar dos vectores de datos numéricos. Un enfoque escalar sería algo como esto:
para ( i = 0 ; i < 1024 ; i ++ ) c [ i ] = a [ i ] * b [ i ]; Esto podría vectorizarse para que se vea así:
para ( i = 0 ; i < 1024 ; i += 4 ) c [ i : i + 3 ] = a [ i : i + 3 ] * b [ i : i + 3 ]; Aquí, c[i:i+3] representa los cuatro elementos de la matriz desde c[i] hasta c[i+3] y el procesador vectorial puede realizar cuatro operaciones para una sola instrucción vectorial. Dado que las cuatro operaciones vectoriales se completan aproximadamente en el mismo tiempo que una instrucción escalar, el enfoque vectorial puede ejecutarse hasta cuatro veces más rápido que el código original.
Hay dos enfoques de compilación distintos: uno basado en la técnica de vectorización convencional y el otro basado en el desenrollado de bucles .
Esta técnica, utilizada en máquinas vectoriales convencionales, intenta encontrar y explotar el paralelismo SIMD a nivel de bucle. Consta de dos pasos principales, que se describen a continuación.
En el primer paso, el compilador busca obstáculos que puedan impedir la vectorización. Un obstáculo importante para la vectorización es la dependencia de datos reales más corta que la longitud del vector. Otros obstáculos incluyen llamadas a funciones y recuentos de iteraciones cortos.
Una vez que se determina que el bucle es vectorizable, se descompone el bucle según la longitud del vector y cada instrucción escalar dentro del cuerpo del bucle se reemplaza con la instrucción vectorial correspondiente. A continuación, se muestran las transformaciones de componentes para este paso utilizando el ejemplo anterior.
para ( i = 0 ; i < 1024 ; i += 4 ) para ( j = 0 ; j < 4 ; j ++ ) c [ i + j ] = a [ i + j ] * b [ i + j ]; para ( i = 0 ; i < 1024 ; i += 4 ) { para ( j = 0 ; j < 4 ; j ++ ) tA [ j ] = A [ i + j ]; para ( j = 0 ; j < 4 ; j ++ ) tB [ j ] = B [ i + j ]; para ( j = 0 ; j < 4 ; j ++ ) tC [ j ] = tA [ j ] * tB [ j ]; para ( j = 0 ; j < 4 ; j ++ ) C [ i + j ] = tC [ j ]; } para ( i = 0 ; i < 1024 ; i += 4 ) { vA = vec_ld ( & A [ i ]); vB = vec_ld ( & B [ i ]); vC = vec_mul ( vA , vB ); vec_st ( vC , & C [ i ]); } Esta técnica relativamente nueva está dirigida específicamente a las arquitecturas SIMD modernas con longitudes de vector cortas. [2] Aunque los bucles se pueden desenrollar para aumentar la cantidad de paralelismo SIMD en bloques básicos, esta técnica explota el paralelismo SIMD dentro de bloques básicos en lugar de bucles. Los dos pasos principales son los siguientes.
Para mostrar las transformaciones paso a paso para este enfoque, se utiliza nuevamente el mismo ejemplo.
para ( i = 0 ; i < 1024 ; i += 4 ) { sA0 = ld ( & A [ i + 0 ]); sB0 = ld ( & B [ i + 0 ]); sC0 = sA0 * sB0 ; st ( sC0 , & C [ i + 0 ]); ... sA3 = ld ( & A [ i + 3 ]); sB3 = ld ( & B [ i + 3 ]); sC3 = sA3 * sB3 ; st ( sC3 , & C [ i + 3 ]); } para ( i = 0 ; i < 1024 ; i += 4 ) { ( sA0 , sA1 , sA2 , sA3 ) = ld ( & A [ i + 0 : i + 3 ]); ( sB0 , sB1 , sB2 , sB3 ) = ld ( & B [ i + 0 : i + 3 ]); ( sC0 , sC1 , sC2 , sC3 ) = ( sA0 , sA1 , sA2 , sA3 ) * ( sB0 , sB1 , sB2 , sB3 ); st (( sC0 , sC1 , sC2 , sC3 ), & C [ i + 0 : i + 3 ]); } para ( i = 0 ; i < 1024 ; i += 4 ) { vA = vec_ld ( & A [ i ]); vB = vec_ld ( & B [ i ]); vC = vec_mul ( vA , vB ); vec_st ( vC , & C [ i ]); } Aquí, sA1, sB1, ... representan variables escalares y vA, vB y vC representan variables vectoriales.
La mayoría de los compiladores comerciales que vectorizan automáticamente utilizan el enfoque convencional a nivel de bucle, excepto el compilador IBM XL, [3] [ fuente obsoleta ] que utiliza ambos.
La presencia de sentencias if en el cuerpo del bucle requiere la ejecución de instrucciones en todas las rutas de control para fusionar los múltiples valores de una variable. Un enfoque general es realizar una secuencia de transformaciones de código: predicación → vectorización (usando uno de los métodos anteriores) → eliminar predicados vectoriales → eliminar predicados escalares. [4] Si se utiliza el siguiente código como ejemplo para mostrar estas transformaciones;
para ( i = 0 ; i < 1024 ; i ++ ) si ( A [ i ] > 0 ) C [ i ] = B [ i ]; de lo contrario D [ i ] = D [ i -1 ]; para ( i = 0 ; i < 1024 ; i ++ ) { P = A [ i ] > 0 ; NP = ! P ; C [ i ] = B [ i ]; ( P ) D [ i ] = D [ i -1 ]; ( NP ) } donde (P) denota un predicado que protege la declaración.
para ( i = 0 ; i < 1024 ; i += 4 ) { vP = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); vNP = vec_not ( vP ); C [ i : i + 3 ] = B [ i : i + 3 ]; ( vP ) ( NP1 , NP2 , NP3 , NP4 ) = vNP ; D [ i + 3 ] = D [ i + 2 ]; ( NP4 ) D [ i + 2 ] = D [ i + 1 ]; ( NP3 ) D [ i + 1 ] = D [ i ]; ( NP2 ) D [ i ] = D [ i -1 ]; ( NP1 ) } para ( i = 0 ; i < 1024 ; i += 4 ) { vP = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); vNP = vec_not ( vP ); C [ i : i + 3 ] = vec_sel ( C [ i : i + 3 ], B [ i : i + 3 ], vP ); ( NP1 , NP2 , NP3 , NP4 ) = vNP ; D [ i + 3 ] = D [ i + 2 ]; ( NP4 ) D [ i + 2 ] = D [ i + 1 ]; ( NP3 ) D [ i + 1 ] = D [ i ]; ( NP2 ) D [ i ] = D [ i -1 ]; ( NP1 ) } para ( i = 0 ; i < 1024 ; i += 4 ) { vP = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); vNP = vec_not ( vP ); C [ i : i + 3 ] = vec_sel ( C [ i : i + 3 ], B [ i : i + 3 ], vP ); ( NP1 , NP2 , NP3 , NP4 ) = vNP ; si ( NP4 ) D [ i + 3 ] = D [ i + 2 ]; si ( NP3 ) D [ i + 2 ] = D [ i + 1 ]; si ( NP2 ) D [ i + 1 ] = D [ i ]; si ( NP1 ) D [ i ] = D [ i -1 ]; } La ejecución de las instrucciones en todas las rutas de control en el código vectorial ha sido uno de los principales factores que ralentizan el código vectorial con respecto a la línea base escalar. Cuanto más complejo se vuelve el flujo de control y más instrucciones se pasan por alto en el código escalar, mayor es la sobrecarga de vectorización. Para reducir esta sobrecarga de vectorización, se pueden insertar ramas vectoriales para pasar por alto las instrucciones vectoriales de manera similar a la forma en que las ramas escalares pasan por alto las instrucciones escalares. [5] A continuación, se utilizan predicados de AltiVec para mostrar cómo se puede lograr esto.
para ( i = 0 ; i < 1024 ; i ++ ) { si ( A [ i ] > 0 ) { C [ i ] = B [ i ]; si ( B [ i ] < 0 ) D [ i ] = E [ i ]; } } para ( i = 0 ; i < 1024 ; i += 4 ) { vPA = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); C [ i : i + 3 ] = vec_sel ( C [ i : i + 3 ], B [ i : i + 3 ], vPA ); vT = B [ i : i + 3 ] < ( 0 , 0 , 0 , 0 ); vPB = vec_sel (( 0 , 0 , 0 , 0 ), vT , vPA ); D [ i : i + 3 ] = vec_sel ( D [ i : i + 3 ], E [ i : i + 3 ], vPB ); } para ( i = 0 ; i < 1024 ; i += 4 ) { si ( vec_any_gt ( A [ i : i + 3 ], ( 0 , 0 , 0 , 0 ))) { vPA = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); C [ i : i + 3 ] = vec_sel ( C [ i : i + 3 ], B [ i : i + 3 ], vPA ); vT = B [ i : i + 3 ] < ( 0 , 0 , 0 , 0 ); vPB = vec_sel (( 0 , 0 , 0 , 0 ), vT , vPA ); si ( vec_cualquier_uno ( vPB , ( 0 , 0 , 0 , 0 ))) D [ i : i + 3 ] = vec_sel ( D [ i : i + 3 ], E [ i : i + 3 ], vPB ); } } Hay dos cosas que se deben tener en cuenta en el código final con ramas vectoriales: primero, la instrucción de definición de predicado para vPA también se incluye dentro del cuerpo de la rama vectorial externa mediante el uso de vec_any_gt. Segundo, la rentabilidad de la rama vectorial interna para vPB depende de la probabilidad condicional de que vPB tenga valores falsos en todos los campos, dado que vPA tiene valores falsos en todos los campos.
Consideremos un ejemplo en el que siempre se toma la rama externa en la línea base escalar, lo que omite la mayoría de las instrucciones en el cuerpo del bucle. El caso intermedio anterior, sin ramas vectoriales, ejecuta todas las instrucciones vectoriales. El código final, con ramas vectoriales, ejecuta tanto la comparación como la rama en modo vectorial, lo que potencialmente mejora el rendimiento en comparación con la línea base escalar.
En la mayoría de los compiladores de C y C++ , es posible utilizar funciones intrínsecas para vectorizar manualmente, a expensas del esfuerzo del programador y la capacidad de mantenimiento.