Vectorización automática

La vectorización automática, en computación paralela, es un caso especial de paralelización automática, en la cual un programa informático es convertido de una implementación escalar, el cual procesa un simple par de operandos en un momento, a una implementación vectorial, el cual procesa una operación en múltiples pares de operandos a la vez. Por ejemplo, las computadoras modernas comunes, incluyendo las super computadoras especializadas, típicamente tienen operaciones vectoriales que realizan operaciones simultáneamente como las siguientes cuatro adiciones. (Vía hardware de tipo SIMD o SPMD):

{\begin{aligned}c_{1}&=a_{1}+b_{1}\\c_{2}&=a_{2}+b_{2}\\c_{3}&=a_{3}+b_{3}\\c_{4}&=a_{4}+b_{4}\end{aligned}}

Sin embargo, en la mayoría de lenguajes de programación uno típicamente escribe ciclos que ordenadamente realizan múltiples adiciones en muchos números. Acá hay un ejemplo de un ciclo, escrito en C:

//Asigna al espacio actual del vector "C[i]", 
//el resultado de la suma del valor de "a[i]", 
//con el valor de "b[i]", usando el index i, dado n.

for (i=0; i<n; i++)
    c[i] = a[i] + b[i];

Un compilador de vectorización transforma estos ciclos en secuencias de operación vectorial. Estas operaciones vectoriales realizan adiciones o sumas en bloques de elementos de longitud cuatro (en nuestro ejemplo mostrado) de las matrices a, b c. La vectorización automática es un tema relevante de investigación estudiado en las ciencias de la computación.

Historia[editar]

Las primeras computadoras usualmente tenían una unidad lógica, la cual ejecutaba una instrucción en un par de operandos al mismo tiempo. En consecuencia, los lenguaje de programación y los programas fueron diseñados para poder ejecutarse en secuencias. Sin embargo, las computadoras modernas pueden hacer múltiples cosas al mismo tiempo. Por lo que, muchos compiladores optimizados realizan vectorización automática, donde partes de programas secuenciales son transformados a operaciones paralelas.

La Vectorización cíclica transforma ciclos procedurales asignándoles una unidad de procesamiento a cada par de operandos. Los programas invierten gran parte de su tiempo en estos ciclos. Por lo tanto, la vectorización puede acelerarlos significativamente, especialmente en grandes conjuntos de datos. La Vectorización cíclica es implementada en el MMX de Intel, el SSE, en AVX, en Power ISA de AltiVec, y en el conjunto de instrucciones de ARM NEON.

Hay muchas restricciones que previenen o limitan la vectorización.^[1] Por lo tanto, varias veces la vectorización puede llegar a ralentizar el proceso de ejecución, por ejemplo debido a la sincronización de Tubería (Pipeline) o a la sincronización de movimientos o transferencia de datos. El análisis de dependencia de bucles identifica los bucles que es posible vectorizar, basándose en la dependencia de datos de las instrucciones presentes dentro de los bucles.

Garantías[editar]

La vectorización automatizada, como cualquier otra optimización de ciclos u otro de optimización del tiempo de compilación, debe preservar exactamente el comportamiento original del programa.

Dependencias de datos[editar]

Todas las dependencias tienen que ser respetadas durante la ejecución para impedir resultados incorrectos o inesperados.

Por lo general, las dependencias que no varían en un ciclo y las dependencias léxicas de tipo backward pueden ser transformadas en dependencias lexicamente directas. Aun así, estas transformaciones tienen que ser hechas correctamente, para poder llegar a asegurar que la dependencia entre todas las declaraciones realizadas permanezca igual al modelo original.

Las dependencias cíclicas tienen que ser procesadas independientemente de las instrucciones vectoriales.

Precisión de los datos[editar]

Una Precisión en los tipos de dato entero tiene que ser mantenida durante la ejecución de instrucciones del vector. La instrucción de vector correcta tiene que ser escogida tomando en cuenta la medida y comportamiento de los enteros internos. Además, con tipos de entero mixto, hay que tener un cuidado extra para aumentar o disminuirlos correctamente sin perder precisión en los datos. El cuidado especial tiene que ser realizado,, tomando en cuenta la operación con extensión de signo (debido a que múltiples enteros están empaquetados dentro del mismo registro) y durante operaciones de cambio, u operaciones con bits de acarreo que de otro modo deberían ser tomados en cuenta.

La Precisión en los datos de tipo Float tiene que ser mantenida también, a no ser que no se este considerando el estándar IEEE-754 , en cuyo caso las operaciones serán más rápidas pero los resultados finales pueden llegar a variar ligeramente. Variaciones grandes, incluso ignorando el estándar IEEE-754 normalmente pueden llegar a significar un error de programación.

Teoría[editar]

Para vectorizar un programa, el optimizador del compilador debe primero llegar a entender las dependencias entre las declaraciones y reorganizarlas de ser necesario. Una vez que las declaraciones sean mapeadas o estructuradas correctamente, el optimizador debe organizar adecuadamente las instrucciones organizadas a instrucciones vectoriales, que operan en múltiples elementos de datos.

Construyendo el gráfico de dependencias[editar]

El primer paso para poder construir el Gráfico de dependencias , es identificando qué declaraciones dependen de otras declaraciones. Esto implica examinar cada declaración e identificar cada elemento en los datos que se tienen acceso, mapeando modificadores de acceso de matriz a funciones y comprobando cada dependencia de acceso a 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) a la misma región en la memoria.

El gráfico de dependencias contiene todas las dependencias cuya tamaño sea menor que la medida del vector. Por tanto, si el registro del vector es de 128 bits , y el tipo de Vector es de 32 bits , el tamaño del vector se puede determinar usando 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 vectorial.

Supongamos que el tamaño del vector es igual a 4 datos de tipo int o entero:

for (i = 0; i < 128; i++) {
    a[i] = a[i-16]; // Si 16 > 4, Es seguro de ignorar, por tanto no afectará el resultado
    a[i] = a[i-1]; // Si 1 < 4, permanece en el gráfico de dependencias
}

Agrupamiento[editar]

Utilizando el gráfico, el optimizador vectorial puede entonces agrupar correctamente los Componentes fuertemente conexos (SCC) y separar las declaraciones vectorizables del resto.

Por ejemplo, considerando un fragmento de un programa que contiene tres grupos de declaración dentro de un ciclo: (SCC1+SCC2), SCC3 y SCC4, en cuyo orden, en el cual sólo el segundo grupo (SCC3) puede ser vectorizado. El programa final entonces contendrá tres ciclos, uno para cada grupo, con único el grupo de en medio vectorizado.Ya que el optimizador no puede unir el primer elemento con el último elemento sin afectar el orden de ejecución de la declaración, lo que invalidaría las garantías necesarias.

Detectando expresiones idiomáticas[editar]

Algunas dependencias no tan obvias o más difíciles de identificar pueden optimizarse aún más en función de expresiones idiomáticas específicas.

Por ejemplo, las siguientes autodependencias de datos pueden ser vectorizadas porque el valor de los valores de la derecha (RHS) se puede obtener y almacenar en el valor izquierdo, por lo que no hay forma de que los datos cambien dentro de la asignación.

a[i] = a[i] + a[i+1];

La auto dependencia por escalares puede ser vectoriza usando el Algoritmo de eliminación de variables.

Marco general[editar]

El marco general empleado para la vectorización basada en ciclos está dividido en cuatro pasos o etapas:

Preludio: Es cuando las variables independientes del ciclo son preparadas para ser usadas dentro del mismo. Esto normalmente significa mover las variables a los registros del vector con patrones específicos que serán usados en las instrucciones propias del vector. Este es también un lugar para insertar la verificación de dependencias al momento de ejecución. Si la verificación realizada concluye en que la vectorización no es posible, salta hacia el paso de limpieza.
Bucle(s): Son todos los bucles vectorizados (o no), que son separados por grupos de SCC en orden de aparición en el código original.
Finalización: Devuelve todas las variables, inducciones y reducciones independientes en la ejecución del ciclo
Limpieza: Implementa bucles simples (no vectorizados) para iteraciones al final de un ciclo que no sean múltiplos del tamaño del vector específicado, o en el caso de que las verificaciones en tiempo de ejecución prohíban el procesamiento del vector especificado.

Tiempo de Ejecución vs. Tiempo de Compilación[editar]

Algunas vectorizaciones pueden no ser completamente revisadas en tiempo de compilación. Por ejemplo, las funciones de librería pueden vencer la optimización, si la información que procesan está dada por el llamado. Incluso en estos casos, la optimización en el tiempo-ejecución puede ser vectorizable en ciclos en-vuelo.

Esta revisión en tiempo de ejecución está hecha en la etapa de preludio y dirige el flujo del análisis del vector a instrucciones vectorizables si es posible,en caso contrario revierte a un procesamiento estándar vectorial, tomando en cuenta las variables que está siendo usadas en los registros o variables escalares.

El siguiente código fácilmente puede ser vectorizado en tiempo de compilación, ya que no depende de parámetros externos .También, los lenguajes de programación garantizan que tampoco ocupará la misma región en memoria como cualquier otra variable, ya que son variables locales y viven sólo en la pila al momento de la ejecución del ciclo.

int a[128];
int b[128];
// initialize b

for (i = 0; i<128; i++)
  a[i] = b[i] + 5;

Por otro lado, el ejemplo de código que se expone a continuación no tiene información en las posiciones de memoria, porque las referencias son punteros, por lo que 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 comprobación rápida al momento de ejecución de la dirección de memoria de a y b, más el espacio de iteración del bucle (128 veces de iteración) es suficiente para saber si las matrices se superponen o no, revelando así cualquier dependencia requerida.

Existen algunas herramientas para analizar dinámicamente las aplicaciones existentes con la finalidad de poder evaluar el potencial latente, inherente para el paralelismo SIMD, el cual viene siendo explotable a través de avances adicionales del compilador y / o mediante cambios manuales en el código.^[2]

Técnicas[editar]

Un ejemplo sería un programa para multiplicar dos vectores de datos numéricos. Una aproximación escalar sería algo como:

 for (i = 0; i < 1024; i++)
    C[i] = A[i]*B[i];

Esto podría ser vectorizado para parecerse a algo como el siguiente código:

  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 vectores. 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 aproximaciones de compiladores distintos : uno basado en la técnica de vectorización convencional y el otro basado en desenroscado de bucles .

Vectorización automática a nivel de bucle[editar]

Esta técnica, utilizada para máquinas de vector convencional, intenta encontrar y explotar SIMD paralelismo en el nivel de bucle. Consta de dos pasos importantes.

Encontrar un bucle interior que puede ser vectorizable
Transformar el bucle y generar códigos de vector

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 a la hora de la vectorización incluyen llamadas a funciones y recuentos de iteraciones cortas.

Una vez que se determina que el bucle es vectorizable, el bucle se corta mediante 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, las transformaciones de componentes para este paso se demuestran utilizando el siguiente ejemplo.

Después del stripmining

for (i = 0; i < 1024; i+=4)
    for (ii = 0; ii < 4; ii++)
       C[i+ii] = A[i+ii]*B[i+ii];

Después de la distribución en bucle utilizando matrices temporales

  for (i = 0; i < 1024; i+=4)
  {
    for (ii = 0; ii < 4; ii++) tA[ii] = A[i+ii];
    for (ii = 0; ii < 4; ii++) tB[ii] = B[i+ii];
    for (ii = 0; ii < 4; ii++) tC[ii] = tA[ii]*tB[ii];
    for (ii = 0; ii < 4; ii++) C[i+ii] = tC[ii];
  }

Después de reemplazar con códigos de vector

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[editar]

Esta, relativamente, nueva técnica apunta específicamente a arquitecturas modernas SIMD con longitudes de vector corto.^[3] 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 expuestos:

El ciclo más interno se desenrolla por un factor de la longitud del vector para formar un cuerpo de ciclo grande.
Las instrucciones escalares isomorfas (que realizan la misma operación) se empaquetan en una instrucción vectorial si las dependencias no impiden hacerlo.

Para mostrar transformaciones paso a paso para este enfoque, se utiliza nuevamente el mismo ejemplo.

Después de desarrollar el ciclo (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 empaquetar

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 del vector.

La mayoría de los compiladores comerciales de vectorización automática utilizan el enfoque convencional de nivel de ciclo, excepto el compilador IBM XL, que usa ambos enfoques.^[4]

En presencia del flujo de control[editar]

La presencia de sentencias condicionales if en el cuerpo del bucle requiere la ejecución de instrucciones en todas las rutas de control para fusionar múltiples instancias de una variable. Un enfoque general es pasar por una secuencia de transformaciones de código: predicación → vectorización (utilizando uno de los métodos anteriores) → eliminar predicados vectoriales → eliminar predicados escalares.^[5] Si se usa el siguiente código 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)
  }

Dónde (P) denota un predicado guardando la declaración.

Después de que vectorization

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 remover 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 remover 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];
  }

Reducción de la sobrecarga vectorial en presencia de flujo de control[editar]

Tener que ejecutar las instrucciones en todas las rutas de control en el código vectorial ha sido uno los principales factores que ralentizan el código vectorial respecto a la línea base escalar. Entre más complejo se vuelva el flujo de control y más instrucciones sean omitidas, mayor será la sobrecarga de vectorización. Para reducir esta sobrecarga de vectorización, se pueden insertar ramas de vector para omitir las instrucciones de vector de forma similar a como las ramas escalares omiten las instrucciones escalares.^[6] A continuación, los predicados AltiVec se utilizan para mostrar cómo esto puede ser logrado.

Línea 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; primero, la instrucción de definición de predicado para vPA también se incluye dentro del cuerpo de la rama del vector externo 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 donde siempre se toma la rama externa en la línea base escalar, sin pasar por la mayoría de las instrucciones en el cuerpo del bucle. El caso intermedio anterior, sin ramificaciones vectoriales, ejecuta todas las instrucciones vectoriales. El código final, con ramificaciones vectoriales, ejecuta tanto la comparación como la ramificación en modo vectorial, potencialmente ganando rendimiento sobre la línea base escalar.

Vectorización manual[editar]

En la mayoría de compiladores C y #C++, es posible utilizar funciones intrínsecas para vectorizar manualmente, a expensas del esfuerzo y capacidad de mantenimiento del programador.

Véase también[editar]

Referencias[editar]

↑ Mittal, Sparsh; Anand, Osho; Kumarr, Visnu P (May 2019). «A Survey on Evaluating and Optimizing Performance of Intel Xeon Phi».
↑ [1]
↑ Larsen, S.; Amarasinghe, S. (2000). «Exploiting superword level parallelism with multimedia instruction sets». ACM SIGPLAN Notices 35 (5): 145-156. doi:10.1145/358438.349320.
↑ "Code Optimization with IBM XL Compilers" (PDF). June 2004. Archived from the original (PDF) on 2010-06-10.
↑ . 2005. pp. 165-175. ISBN 0-7695-2298-X. doi:10.1109/CGO.2005.33. Falta el |título= (ayuda)
↑ . 2007. pp. 280-291. doi:10.1109/PACT.2007.41. Falta el |título= (ayuda)

Datos: Q16529632

[phiSurvey-1] Mittal, Sparsh; Anand, Osho; Kumarr, Visnu P (May 2019). «A Survey on Evaluating and Optimizing Performance of Intel Xeon Phi».

[2] [1]

[3] Larsen, S.; Amarasinghe, S. (2000). «Exploiting superword level parallelism with multimedia instruction sets». ACM SIGPLAN Notices 35 (5): 145-156. doi:10.1145/358438.349320.

[ibm2-4] "Code Optimization with IBM XL Compilers" (PDF). June 2004. Archived from the original (PDF) on 2010-06-10.

[5] . 2005. pp. 165-175. ISBN 0-7695-2298-X. doi:10.1109/CGO.2005.33. Falta el |título= (ayuda)

[6] . 2007. pp. 280-291. doi:10.1109/PACT.2007.41. Falta el |título= (ayuda)

[1]

[2]

[3]

[4]

[5]

[6]