Vectorización automática - Automatic vectorization
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 , suelen tener 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 de forma secuencial sumas de muchos números. Aquí hay un ejemplo de un ciclo de este tipo, escrito en C :
for (i = 0; i < n; i++)
c[i] = a[i] + b[i];
Un compilador de vectorización 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 informática.
Fondo
Las primeras computadoras generalmente tenían una unidad lógica, que ejecutaba una instrucción en un par de operandos a la vez. Por tanto, los lenguajes y programas informáticos se diseñaron para ejecutarse en secuencia. Sin embargo, las computadoras modernas pueden hacer muchas cosas a la vez. Entonces, 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 los bucles de procedimiento asignando una unidad de procesamiento a cada par de operandos. Los programas pasan la mayor parte de su tiempo dentro de esos bucles. Por lo tanto, la vectorización puede acelerarlos significativamente, especialmente en grandes conjuntos de datos. Vectorización de bucle está implementada en Intel 's MMX , SSE , y AVX , en ISA Poder ' s AltiVec , y en ARM 's NEON , SVE conjuntos de instrucciones y SVE2.
Muchas limitaciones impiden u obstaculizan 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 de 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.
Garantías
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.
Dependencias de datos
Todas las dependencias deben respetarse durante la ejecución para evitar resultados incorrectos.
En general, las dependencias invariantes de bucle y las dependencias léxicamente hacia adelante se pueden vectorizar fácilmente, y las dependencias léxicamente hacia atrás se pueden transformar en dependencias léxicamente hacia adelante. Sin embargo, estas transformaciones deben realizarse de forma segura para garantizar que la dependencia entre todos los enunciados permanezca fiel al original.
Las dependencias cíclicas deben procesarse independientemente de las instrucciones vectorizadas.
Precisión de datos
La precisión entera (tamaño de bits) debe mantenerse durante la ejecución de la instrucción vectorial. 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 / degradarlos correctamente sin perder precisión. Se debe tener especial cuidado con la extensión de signo (porque varios enteros están empaquetados dentro del mismo registro) y durante las operaciones de cambio, o las 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 la conformidad con IEEE-754 , en cuyo caso las operaciones serán más rápidas pero los resultados pueden variar ligeramente. Las grandes variaciones, incluso ignorar IEEE-754, generalmente significan un error del programador.
Teoría
Para vectorizar un programa, el optimizador del compilador debe primero comprender las dependencias entre declaraciones y realinearlas, si es necesario. Una vez que se mapean 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.
Construyendo el gráfico de dependencia
El primer paso es construir el gráfico de dependencia , identificando qué declaraciones dependen de qué otras declaraciones. Esto implica examinar cada enunciado e identificar cada elemento de datos al que accede el enunciado, mapear modificadores de acceso de matriz a funciones y verificar la dependencia de cada acceso a todos los demás en todos los enunciados. El análisis de alias se puede utilizar para certificar que las diferentes variables acceden (o se cruzan) en 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 deben invalidar la vectorización, ya que no habrá ningún acceso concurrente en el misma instrucción de vector.
Suponga que el tamaño del vector es igual a 4 pulgadas:
for (i = 0; i < 128; i++) {
a[i] = a[i-16]; // 16 > 4, safe to ignore
a[i] = a[i-1]; // 1 < 4, stays on dependency graph
}
Agrupación
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 solo se puede vectorizar el segundo grupo (SCC3). 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 la sentencia, lo que invalidaría las garantías necesarias.
Detectando modismos
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 personales 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 por escalares se puede vectorizar mediante eliminación de variables .
Marco general
El marco general para la vectorización de bucles se divide en cuatro etapas:
- Preludio : donde las variables independientes del ciclo están preparadas para ser utilizadas dentro del ciclo. Normalmente, esto implica moverlos a registros vectoriales con patrones específicos que se utilizarán en instrucciones vectoriales. Este es también el lugar para insertar la verificación de dependencia en tiempo de ejecución. Si la verificación decide que la vectorización no es posible, bifurque a Limpieza .
- Bucle (s) : Todos los bucles vectorizados (o no), separados por grupos de SCC en orden de aparición en el código original.
- Postludio : Devuelve todas las variables, inducciones y reducciones independientes del ciclo.
- Limpieza : implemente bucles simples (no vectorizados) para iteraciones al final de un bucle que no sean un múltiplo del tamaño del vector o para cuando las comprobaciones en tiempo de ejecución prohíban el procesamiento de vectores.
Tiempo de ejecución frente a tiempo de compilación
Algunas vectorizaciones no se pueden comprobar por completo en el momento de la compilación. Por ejemplo, las funciones de la biblioteca pueden anular la optimización si la persona que llama proporciona los datos que procesan. Incluso en estos casos, la optimización en tiempo de ejecución aún puede vectorizar bucles sobre la marcha.
Esta verificación de 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 están pasando 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 ninguno de los dos ocupará la misma región en la memoria que cualquier otra variable, ya que son variables locales y viven solo en la pila de ejecución .
int a[128];
int b[128];
// initialize b
for (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 la memoria, porque las referencias son punteros y la memoria a la que apuntan puede superponerse.
void compute(int *a, int *b)
{
int i;
for (i = 0; i < 128; i++, a++, b++)
*a = *b + 5;
}
Una revisión rápida de tiempo de ejecución en la dirección tanto de un y b , más el espacio iteración del bucle (128) es suficiente para decir si las matrices se superponen o no, lo que revela las dependencias.
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 avances adicionales en el compilador y / o mediante cambios de código manuales.
Técnicas
Un ejemplo sería un programa para multiplicar dos vectores de datos numéricos. Un enfoque escalar sería algo como:
for (i = 0; i < 1024; i++)
c[i] = a[i] * b[i];
Esto podría vectorizarse para que se parezca a lo siguiente:
for (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 de vector. 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 distintos del compilador: uno basado en la técnica de vectorización convencional y el otro basado en el desenrollado de bucles .
Vectorización automática a nivel de bucle
Esta técnica, utilizada para máquinas vectoriales convencionales, intenta encontrar y explotar el paralelismo SIMD a nivel de bucle. Consta de los dos pasos principales siguientes.
- Encuentra un bucle más interno que se pueda vectorizar
- Transforma el bucle y genera códigos vectoriales
En el primer paso, el compilador busca obstáculos que puedan evitar 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 conteos de iteraciones breves.
Una vez que se determina que el bucle es vectorizable, el bucle se elimina por la longitud del vector y cada instrucción escalar dentro del cuerpo del bucle se reemplaza con la instrucción del vector correspondiente. A continuación, se muestran las transformaciones de componentes para este paso utilizando el ejemplo anterior.
- Después de la remoción
for (i = 0; i < 1024; i += 4)
for (j = 0; j < 4; j++)
c[i+j] = a[i+j] * b[i+j];
- Después de la distribución del bucle mediante matrices temporales
for (i = 0; i < 1024; i += 4)
{
for (j = 0; j < 4; j++) tA[j] = A[i+j];
for (j = 0; j < 4; j++) tB[j] = B[i+j];
for (j = 0; j < 4; j++) tC[j] = tA[j] * tB[j];
for (j = 0; j < 4; j++) C[i+j] = tC[j];
}
- Después de reemplazar con códigos vectoriales
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]);
}
Vectorización automática a nivel de bloque básico
Esta técnica relativamente nueva se dirige específicamente a arquitecturas SIMD modernas con longitudes de vector cortas. Aunque los bucles se pueden desenrollar para aumentar la cantidad de paralelismo SIMD en bloques básicos, esta técnica aprovecha el paralelismo SIMD dentro de bloques básicos en lugar de bucles. Los dos pasos principales son los siguientes.
- El bucle más interno se desenrolla por un factor de la longitud del vector para formar un cuerpo de bucle grande.
- Las instrucciones escalares isomórficas (que realizan la misma operación) se empaquetan en una instrucción vectorial si las dependencias no lo impiden.
Para mostrar las transformaciones paso a paso para este enfoque, se usa de nuevo el mismo ejemplo.
- Después del desenrollado del bucle (por la longitud del vector, se supone que es 4 en este caso)
for (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]);
}
- Después de empacar
for (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]);
}
- Después de la generación de código
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 de nivel de bucle convencional, excepto IBM XL Compiler, que utiliza ambos.
En presencia de flujo de control
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. Si el siguiente código se usa como ejemplo para mostrar estas transformaciones;
for (i = 0; i < 1024; i++)
if (A[i] > 0)
C[i] = B[i];
else
D[i] = D[i-1];
- Después de la predicación
for (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 guarda el enunciado.
- Después de la vectorización
for (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)
}
- Después de eliminar los predicados vectoriales
for (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)
}
- Después de eliminar los predicados escalares
for (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;
if (NP4) D[i+3] = D[i+2];
if (NP3) D[i+2] = D[i+1];
if (NP2) D[i+1] = D[i];
if (NP1) D[i] = D[i-1];
}
Reducir la sobrecarga de vectorización en presencia de flujo de control
Tener que ejecutar las instrucciones en todas las rutas de control en código vectorial ha sido uno de los principales factores que ralentiza 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 omiten 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 omitir instrucciones vectoriales de manera similar a la forma en que las ramas escalares omiten instrucciones escalares. A continuación, se utilizan predicados AltiVec para mostrar cómo se puede lograr esto.
- Línea de base escalar (código original)
for (i = 0; i < 1024; i++)
{
if (A[i] > 0)
{
C[i] = B[i];
if (B[i] < 0)
D[i] = E[i];
}
}
- Después de la vectorización en presencia de flujo de control
for (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);
}
- Después de insertar ramas vectoriales
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[i:i+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; En primer lugar, la instrucción que define el predicado para vPA también se incluye dentro del cuerpo de la rama del vector exterior mediante el uso de 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 externa en la línea de base escalar, omitiendo 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 gana rendimiento sobre la línea base escalar.
Vectorización manual
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.
