Optimizar una implementación de NEON XOR

optimization arm

Question

Intentando uint32 una gran matriz uint32 , decidí usar el coprocesador NEON.

Implementé dos versiones c :

versión 1:

uint32_t xor_array_ver_1(uint32_t *array, int size)
{
    uint32x2_t acc = vmov_n_u32(0);
    uint32_t acc1 = 0;
    for (; size != 0; size -= 2) {
        uint32x2_t vec;
        vec = vld1_u32(array);
        array += 2;
        acc = veor_u32(acc, vec);
    }
    acc1 = vget_lane_u32(acc,0) ^ vget_lane_u32(acc,1);
    return acc1;
}

versión 2:

uint32_t xor_array_ver_2(uint32_t *array, int size)
{
    uint32x4_t acc = vmovq_n_u32(0);
    uint32_t acc1 = 0;

    for (; size != 0; size -= 4) {
        uint32x4_t vec;
        vec = vld1q_u32(array);
        array += 4;
        acc = veorq_u32(acc, vec);
    }

    acc1 ^= vgetq_lane_u32(acc,0);
    acc1 ^= vgetq_lane_u32(acc,1);
    acc1 ^= vgetq_lane_u32(acc,2);
    acc1 ^= vgetq_lane_u32(acc,3);

    return acc1;
}

Comparando las 2 versiones anteriores con la implementación xor tradicional:

for (i=0; i<arr_size; i++)
        val ^= my_array[i];

Observé 2 problemas:

1. La versión 1 tiene el mismo rendimiento.
2. La versión 2 es más de un 30% mejor.

1. ¿Puedo reescribirlo para ser aún mejor? donde my_array está declarado como uint32_t my_array[BIG_LENGTH];
2. ¿Hay alguna forma que no sea de NEON en la que pueda mejorar el rendimiento del código de xoring normal? desenrollar el bucle no proporciona ninguna mejora.

Answer 1

Lo más probable es que esto tenga limitado el ancho de banda de la memoria: una vez que satura el ancho de banda de DRAM disponible, lo cual debería ser bastante fácil de hacer con solo una operación de ALU por carga, no obtendrá ningún beneficio adicional de la optimización.

Si es posible, intente combinar su XOR con otra operación con los mismos datos; de esa forma amortizará el costo de los fallos de caché.

Answer 2

No escribo para ARM, y no estoy familiarizado con NEON en absoluto, pero tenía el siguiente pensamiento, que depende de que ARM NEON sea una arquitectura en línea, que no sé si es ...

Si Paul R tiene razón acerca de que su ancho de banda de memoria está saturado, esto puede tener poco o ningún beneficio, pero ¿qué ocurre si reestructura ligeramente su código de la siguiente manera ...

uint32_t xor_array_ver_2(uint32_t *array, int size)
{
  // Caveat:  ''size'' must be a positive multiple of 4, otherwise this
  //          code will loop for a very long time... and almost certainly
  //          segfault (or whatever term your system uses).

  uint32x4_t acc = vmovq_n_u32(0);
  uint32x4_t next_vec = vld1q_u32(array);
  uint32_t acc1 = 0;

  for (size-=4, array+=4; size != 0; size-=4) {
     uint32x4_t vec = next_vec;
     array += 4;
     next_vec = vld1q_u32(array);
     acc = veorq_u32(acc, vec);
  }
  acc = veorq_u32(acc, next_vec);

  acc1 ^= vgetq_lane_u32(acc,0);
  acc1 ^= vgetq_lane_u32(acc,1);
  acc1 ^= vgetq_lane_u32(acc,2);
  acc1 ^= vgetq_lane_u32(acc,3);

  return acc1;
}

.... con el objetivo de comenzar con la carga del siguiente elemento vectorial antes de que sea necesario para el siguiente ciclo.

Otro pequeño giro que podrías probar es esto:

uint32_t xor_array_ver_2(uint32_t *array, int size)
{
  // Caveat:  ''size'' must be a positive multiple of 4, otherwise this
  //          code will loop for a very long time... and almost certainly
  //          segfault (or whatever term your system uses).

  uint32x4_t acc = vmovq_n_u32(0);
  uint32x4_t next_vec = vld1q_u32(&array[size-4]);
  uint32_t acc1 = 0;

  for (size-=8; size>=0; size-=4) {
     uint32x4_t vec = next_vec;
     next_vec = vld1q_u32(&array[size]);
     acc = veorq_u32(acc, vec);
  }
  acc = veorq_u32(acc, next_vec);

  acc1 ^= vgetq_lane_u32(acc,0);
  acc1 ^= vgetq_lane_u32(acc,1);
  acc1 ^= vgetq_lane_u32(acc,2);
  acc1 ^= vgetq_lane_u32(acc,3);

  return acc1;
}

Answer 3

Es un hecho bien conocido que los intrínsecos de neón en gcc chupan mal. No estoy seguro de si fue mejorado, pero hacer la misma tarea en asm debería darle una mejora mucho mejor que un 30% en comparación con c. Probablemente necesites desenrollar el bucle interno antes que nada. Una forma fácil de transformar los intrínsecos al asm correcto es usar armcc (compilador del brazo) que funciona con intrínsecos.

Por lo tanto, primero intente desenrollar su versión c simple (pseudo código):

for (i=arr_size; i<arr_size; i -= 4)
{
    val1 ^= my_array[0];
    val2 ^= my_array[1];
    val1 ^= my_array[2];
    val2 ^= my_array[3];
    my_array += 4;
}

hacer algo como eso con neón debería darte mejores resultados. Eventualmente, debes cambiar a neon asm, es bastante simple (Personalmente, me resulta más fácil escribir que los intrínsecos).

Aquí está la sugerencia NEON asm (No está probado, depende de usted averiguar cómo armarlo)

//data has to be suitably aligned (it has to be 8 or 16 byte aligned, not sure).
//dataSize in bytes has to be multiple of 64 and has to be at least 128.
//function does xor of uint32_t values and returns the result.
unsigned xor_array_64(const void *data, int dataSize);

xor_array_64:
      vldm r0!,{d0-d7}
      subs r1,r1,#0x40
0:
      pld [r0, #0xC0]
      vldm r0!,{d16-d23}
      veor q0, q0, q8
      veor q1, q1, q9
      veor q2, q2, q10
      veor q3, q3, q11
      subs r1,r1,#0x40
      bge 0b

      veor q0, q0, q1
      veor q2, q2, q3
      veor q0, q0, q2
      veor d0, d0, d1

      vtrn.32 d1, d0
      veor d0, d0, d1

      vmov r0, s0
      bx lr

Answer 4

Una respuesta larga sin ningún fragmento de código.

Límites de hardware

Primero debes preguntarte, ¿qué espero? ¿Quieres escribir el código más rápido posible? ¿Cómo puedes verificar eso? Comience, por ejemplo, escribiendo algunas pruebas sobre lo que su hardware puede lograr. Como señalaron las personas, esto será mayormente limitado al ancho de banda de la memoria, pero luego necesita saber qué tan rápido es su interfaz de memoria. Averigüe las características de capacidad / rendimiento de su plataforma L1, L2 y ram, luego sabrá lo que puede esperar a lo sumo para diferentes tamaños de búfer.

Compilador

¿Estás usando el último compilador? La siguiente pregunta es: ¿está utilizando las herramientas disponibles para usted en su mejor momento? La mayoría de los compiladores no intentan optimizar su código agresivamente, a menos que así lo indique. ¿Los estás configurando para tu mejor ganancia? ¿Está habilitando la optimización completa (gcc: -O3), vectorización (gcc: -ftree-vectorize -ftree-vectorizer-verbose = 1)? ¿Establece indicadores de configuración correctos para su plataforma (-mcpu -mfpu)?

¿Estás verificando el código objeto generado por el compilador? Para un bucle tan simple, esto sería muy fácil y le ayudará a probar muchas opciones de configuración y verificar el código producido.

Ajustes

¿Está comprobando si el uso de punteros restringidos mejora el rendimiento?

¿Qué hay de la información de alineación ? (Por ejemplo, no menciona en sus ejemplos intrínsecos pero espera que el tamaño sea un múltiplo de 2 o 4 y, por supuesto, que con el uso de cuadripléjicos puede crear una mejora del% 30).

¿Qué hay también sobre tratar de alinear en el tamaño de la línea de caché?

Capacidades de hardware

¿Sabes de qué es capaz tu hardware? Por ejemplo Cortex-A9 se presenta como "Superescalar de tema especulativo fuera de orden". ¿Puedes aprovechar las capacidades de emisión dual?

Entonces la respuesta está en algún lugar entre "depende" y "necesitas experimentar".