una - GCC: diferencia de vectorización entre dos bucles similares

matrices en matlab programacion

Question

Al compilar con gcc -O3 , ¿por qué el siguiente ciclo no vectoriza (automáticamente):

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foo () {
  int i, j;

  for (i=0; i<SIZE; i++){
    for (j=i; j<SIZE; j++) {
      a[i] = b[i] > c[j] ? b[i] : c[j];
    }
  }
  return a[0];
}

cuando el siguiente lo hace?

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foov () {
  int i, j;

  for (i=0; i<SIZE; i++){
    for (j=i; j<SIZE; j++) {
      a[i] += b[i] > c[j] ? b[i] : c[j];
    }
  }
  return a[0];
}

La única diferencia es si el resultado de la expresión en el ciclo interno se asigna a un [i], o si se agrega a un [i] .

Para la referencia -ftree-vectorizer-verbose=6 da la siguiente salida para el primer bucle (que no se vectoriza).

v.c:8: note: not vectorized: inner-loop count not invariant.
v.c:9: note: Unknown alignment for access: c
v.c:9: note: Alignment of access forced using peeling.
v.c:9: note: not vectorized: live stmt not supported: D.2700_5 = c[j_20];

v.c:5: note: vectorized 0 loops in function.

Y el mismo resultado para el bucle que vectoriza es:

v.c:8: note: not vectorized: inner-loop count not invariant.
v.c:9: note: Unknown alignment for access: c
v.c:9: note: Alignment of access forced using peeling.
v.c:9: note: vect_model_load_cost: aligned.
v.c:9: note: vect_model_load_cost: inside_cost = 1, outside_cost = 0 .
v.c:9: note: vect_model_simple_cost: inside_cost = 1, outside_cost = 1 .
v.c:9: note: vect_model_reduction_cost: inside_cost = 1, outside_cost = 6 .
v.c:9: note: cost model: prologue peel iters set to vf/2.
v.c:9: note: cost model: epilogue peel iters set to vf/2 because peeling for alignment is unknown .
v.c:9: note: Cost model analysis:
  Vector inside of loop cost: 3
  Vector outside of loop cost: 27
  Scalar iteration cost: 3
  Scalar outside cost: 7
  prologue iterations: 2
  epilogue iterations: 2
  Calculated minimum iters for profitability: 8

v.c:9: note:   Profitability threshold = 7

v.c:9: note: Profitability threshold is 7 loop iterations.
v.c:9: note: LOOP VECTORIZED.
v.c:5: note: vectorized 1 loops in function.

Answer 1

El primer ciclo es equivalente a

#define SIZE (65536)

int a[SIZE], b[SIZE], c[SIZE];

int foo () {
  int i, j;

  for (i=0; i<SIZE; i++){
    a[i] = b[i] > c[SIZE - 1] ? b[i] : c[SIZE - 1];
  }
  return a[0];
}

El problema con la expresión original es que realmente no tiene mucho sentido, por lo que no es demasiado sorprendente que gcc no pueda vectorizarlo.

Answer 2

El primero simplemente cambia trivialmente un [] muchas veces (temporal). El segundo usa el último valor de a [] cada vez (no temporal).

Hasta una versión de parche, puede usar la variable "volátil" para vectorizar.

Utilizar

int * c=malloc(sizeof(int));

para hacerlo alineado;

v.c:9: note: Unknown alignment for access: c

Muestra que "c" tiene un área de almacenamiento diferente que b y a.

Asumo instrucciones tipo "movaps" para ser "vectorizadas" (de la lista de instrucciones SSE-AVX)

Aquí: http://gcc.gnu.org/projects/tree-ssa/vectorization.html#using

los ejemplos 6 y 7 muestran dificultades similares.

Answer 3

El vectorizador GCC probablemente no es lo suficientemente inteligente como para vectorizar el primer ciclo. El caso de suma es más fácil de vectorizar porque a + 0 == a . Considere SIZE==4 :

  0 1 2 3 i
0 X
1 X X
2 X X X
3 X X X X
j

X denota las combinaciones de i y j cuando a se le asignará o aumentará. Para el caso de la suma, podemos calcular los resultados de b[i] > c[j] ? b[i] : c[j] b[i] > c[j] ? b[i] : c[j] para, digamos, j==1 e i==0..4 y póngalo en el vector D Entonces solo necesitamos poner a D[2..3] y agregar el vector resultante a a[0..3] . Para el caso de la asignación, es un poco más complicado. No solo debemos D[2..3] cero D[2..3] , sino también cero A[0..1] y solo luego combinar los resultados. Supongo que aquí es donde el vectorizador está fallando.

Answer 4

En el primer caso : el código sobrescribe la misma ubicación de memoria a[i] en cada iteración. Esto secuencia secuencialmente el bucle ya que las iteraciones de bucle no son independientes.
(En realidad, solo se necesita realmente la iteración final, por lo que se podría eliminar todo el ciclo interno).

En el segundo caso : GCC reconoce el bucle como una operación de reducción, para lo cual tiene manejo especial de casos para vectorizar.

La vectorización del compilador a menudo se implementa como una especie de "coincidencia de patrones". Es decir, el compilador analiza el código para ver si se ajusta a un patrón determinado que puede vectorizar. Si lo hace, se vectoriza. Si no es así, entonces no es así.

Esto parece ser un caso de esquina donde el primer bucle no se ajusta a ninguno de los patrones precodificados que GCC puede manejar. Pero el segundo caso se ajusta al patrón de "reducción vectorizable".

Aquí está la parte relevante del código fuente de GCC que escupe el mensaje "not vectorized: live stmt not supported: "

http://svn.open64.net/svnroot/open64/trunk/osprey-gcc-4.2.0/gcc/tree-vect-analyze.c

if (STMT_VINFO_LIVE_P (stmt_info))
{
    ok = vectorizable_reduction (stmt, NULL, NULL);

    if (ok)
        need_to_vectorize = true;
    else
        ok = vectorizable_live_operation (stmt, NULL, NULL);

    if (!ok)
    {
        if (vect_print_dump_info (REPORT_UNVECTORIZED_LOOPS))
        {
            fprintf (vect_dump, 
                "not vectorized: live stmt not supported: ");
            print_generic_expr (vect_dump, stmt, TDF_SLIM);
        }
        return false;
    }
}

De solo la línea:

vectorizable_reduction (stmt, NULL, NULL);

Está claro que GCC está comprobando si coincide con un patrón de "reducción vectorializable".