La vectorización automática , en computación paralela , es un caso especial de paralelización automática , donde un programa de computadora se convierte de una implementación escalar , que procesa un solo par de operandos a la vez, a una implementación vectorial , que procesa una operación en múltiples pares de operandos a la vez. Por ejemplo, las computadoras convencionales modernas, incluidas las supercomputadoras especializadas , generalmente tienen operaciones vectoriales que realizan simultáneamente operaciones como las siguientes cuatro adiciones (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 secuencialmente sumas de muchos números. A continuación se muestra un ejemplo de dicho bucle, 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 sumas en bloques de elementos de las matrices a, by c. La vectorización automática es un tema de investigación importante en informática. [ cita necesaria ]
Las primeras computadoras generalmente tenían una unidad lógica, que ejecutaba una instrucción en un par de operandos a la vez. Por lo tanto, los lenguajes y programas informáticos fueron diseñados para ejecutarse en secuencia. Sin embargo, las computadoras modernas pueden hacer muchas cosas a la vez. Por lo tanto, muchos compiladores de optimización realizan una vectorización automática, donde partes de programas secuenciales se transforman en operaciones paralelas.
La vectorización de bucles transforma bucles de procedimientos asignando una unidad de procesamiento a cada par de operandos. Los programas pasan la mayor parte de su tiempo dentro de dichos bucles. Por lo tanto, la vectorización puede acelerarlos significativamente, especialmente en grandes conjuntos de datos. La vectorización de bucle 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 .
Muchas restricciones impiden o dificultan la vectorización. A veces, la vectorización puede ralentizar la ejecución, por ejemplo, debido a la sincronización de la canalización o al tiempo del movimiento de datos. El análisis de dependencia de bucles identifica bucles que se pueden vectorizar, basándose en la dependencia de 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.
Todas las dependencias deben respetarse durante la ejecución para evitar resultados incorrectos.
En general, las dependencias invariantes de bucle y las dependencias léxicas hacia adelante se pueden vectorizar fácilmente, y las dependencias léxicas hacia atrás se pueden transformar en dependencias léxicas hacia adelante. Sin embargo, estas transformaciones deben realizarse de forma segura para garantizar que la dependencia entre todas las declaraciones permanezca fiel al original.
Las dependencias cíclicas deben procesarse independientemente de las instrucciones vectorizadas.
La precisión de los enteros (tamaño de bits) debe mantenerse durante la ejecución de la instrucción vectorial. Se debe elegir la instrucción vectorial correcta en función del tamaño y comportamiento de los números enteros internos. Además, con tipos de enteros mixtos, se debe tener especial cuidado para promocionarlos o degradarlos correctamente sin perder precisión. Se debe tener especial cuidado con la extensión de signos (porque se empaquetan varios números enteros 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 del punto flotante , a menos que se desactive el cumplimiento de IEEE-754 , en cuyo caso las operaciones serán más rápidas pero los resultados pueden variar ligeramente. Grandes variaciones, incluso ignorando IEEE-754, generalmente significan un error del programador.
Para vectorizar un programa, el optimizador del compilador primero debe comprender las dependencias entre declaraciones y realinearlas, si es necesario. Una vez asignadas las dependencias, el optimizador debe organizar adecuadamente las instrucciones de implementación cambiando los candidatos apropiados a instrucciones vectoriales, que operan en múltiples elementos de datos.
El primer paso es construir el gráfico de dependencia , identificando qué declaraciones dependen de qué otras declaraciones. Esto implica examinar cada declaración e identificar cada elemento de datos a los 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 se cruzan) a la misma región en la memoria.
El gráfico de dependencia contiene todas las dependencias locales con una distancia no mayor que el tamaño del vector. Entonces, si el registro vectorial es de 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 el misma instrucción vectorial.
Supongamos que el tamaño del vector es igual a 4 enteros:
para ( yo = 0 ; yo < 128 ; yo ++ ) { una [ yo ] = una [ yo -16 ]; // 16 > 4, es seguro ignorar a [ i ] = a [ i -1 ]; // 1 < 4, permanece en el gráfico de dependencia } Usando el gráfico, el optimizador puede agrupar los componentes fuertemente conectados (SCC) y separar declaraciones vectorizables del resto.
Por ejemplo, considere un fragmento de programa que contiene tres grupos de instrucciones dentro de un bucle: (SCC1+SCC2), SCC3 y SCC4, en ese orden, en el que sólo el segundo grupo (SCC3) puede ser vectorizado. El programa final contendrá 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 declaraciones, 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 recupera 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.
un [ yo ] = un [ yo ] + un [ yo + 1 ]; La autodependencia mediante escalares se puede vectorizar mediante eliminación de variables .
El marco general para la vectorización de bucles se divide en cuatro etapas:
Algunas vectorizaciones no se pueden verificar completamente en tiempo de compilación. Por ejemplo, las funciones de la biblioteca pueden frustrar la optimización si los datos que procesan los proporciona la persona que llama. Incluso en estos casos, la optimización en tiempo de ejecución aú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 siguiente código se puede vectorizar fácilmente en tiempo de compilación, ya que no depende de parámetros externos. Además, el lenguaje garantiza que ninguna ocupará la misma región en la memoria que cualquier otra variable, ya que son variables locales y viven sólo en la pila de ejecución .
int a [ 128 ]; int b [ 128 ]; // inicializa b para ( i = 0 ; i < 128 ; i ++ ) a [ i ] = b [ i ] + 5 ; Por otro lado, el siguiente código no tiene información sobre las posiciones de la memoria, porque las referencias son punteros y la memoria a la que apuntan puede superponerse.
cálculo vacío ( int * a , int * b ) { int i ; para ( i = 0 ; i < 128 ; i ++ , a ++ , b ++ ) * a = * b + 5 ; } Una verificación rápida 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.
Existen algunas herramientas para analizar dinámicamente aplicaciones existentes para evaluar el potencial latente inherente del paralelismo SIMD, explotable a través de mayores avances en el compilador y/o mediante cambios manuales de código. [1]
Un ejemplo sería un programa para multiplicar dos vectores de datos numéricos. Un enfoque escalar sería algo como:
para ( i = 0 ; i < 1024 ; i ++ ) c [ i ] = a [ i ] * b [ i ]; Esto podría vectorizarse para verse 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 de c[i] a c[i+3] y el procesador de vectores puede realizar cuatro operaciones para una sola instrucción vectorial. Dado que las cuatro operaciones vectoriales se completan aproximadamente al 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 para máquinas vectoriales convencionales, intenta encontrar y explotar el paralelismo SIMD a nivel de bucle. Consta de dos pasos principales como se detalla 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 verdadera dependencia de datos más corta que la longitud del vector. Otros obstáculos incluyen llamadas a funciones y recuentos cortos de iteraciones.
Una vez que se determina que el bucle es vectorizable, se elimina 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 ]; } for ( 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 se dirige específicamente a arquitecturas SIMD modernas con longitudes de vectores 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 ]); } for ( 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 de vectorización automática utilizan el enfoque convencional a nivel de bucle, excepto el compilador IBM XL, [3] 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 pasar por 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 ]; más D [ i ] = D [ i -1 ]; para ( i = 0 ; i < 1024 ; i ++ ) { P = A [ i ] > 0 ; NP = ! PAG ; C [ yo ] = B [ yo ]; ( PAG ) D [ yo ] = D [ yo -1 ]; ( NP ) } donde (P) denota un predicado que protege el enunciado.
para ( i = 0 ; i < 1024 ; i += 4 ) { vP = A [ i : i + 3 ] > ( 0 , 0 , 0 , 0 ); vNP = vec_not ( vP ); C [ yo : yo + 3 ] = B [ yo : yo + 3 ]; ( vP ) ( NP1 , NP2 , NP3 , NP4 ) = vNP ; D [ yo + 3 ] = D [ yo + 2 ]; ( NP4 ) D [ yo + 2 ] = D [ yo + 1 ]; ( NP3 ) D [ yo + 1 ] = D [ yo ]; ( NP2 ) D [ yo ] = D [ yo -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 [ yo + 3 ] = D [ yo + 2 ]; ( NP4 ) D [ yo + 2 ] = D [ yo + 1 ]; ( NP3 ) D [ yo + 1 ] = D [ yo ]; ( NP2 ) D [ yo ] = D [ yo -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 ]; } Tener que ejecutar las instrucciones en todas las rutas de control en 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 cuantas más instrucciones se omiten en el código escalar, mayor se vuelve la sobrecarga de vectorización. Para reducir esta sobrecarga de vectorización, se pueden insertar ramas vectoriales para omitir instrucciones vectoriales de manera similar a la forma en que las ramas escalares omiten 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 [ yo : yo + 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 ); } for ( i = 0 ; i < 1024 ; i += 4 ) { if ( 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 [ yo : yo + 3 ] < ( 0 , 0 , 0 , 0 ); vPB = vec_sel (( 0 , 0 , 0 , 0 ), vT , vPA ); if ( vec_any_ne ( vPB , ( 0 , 0 , 0 , 0 ))) D [ i : i + 3 ] = vec_sel ( D [ i : i + 3 ], E [ i : i + 3 ], vPB ); } } Hay dos cosas a tener en cuenta en el código final con ramas vectoriales; Primero, la instrucción que define el predicado para vPA también se incluye dentro del cuerpo de la rama del vector externo mediante vec_any_gt. En segundo lugar, la rentabilidad de la rama del vector interno 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.
Considere un ejemplo en el que siempre se toma la rama exterior de la línea de base escalar, sin pasar por la mayoría de las instrucciones del 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, ganando potencialmente rendimiento sobre la línea de 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 y la mantenibilidad del programador.