performance x86-64 sse simd prefetch

performance - ¿Cómo obtengo un beneficio medible de los intrínsecos de captación previa?



x86-64 sse (1)

Si sus datos residen en la memoria, no espere mucho de una aceleración; La recuperación previa de la memoria tiene muy poco disponible para mejorar.

Con 150 ns de tiempo de ciclo, líneas de caché de 64 bytes y velocidad de transferencia de transmisión de 4GB / seg (mi sistema AMD; Intel es más rápido), y utilizando 48 bytes (3 x 128 bits) de cada línea de caché de 64 bytes leída, el sistema es Obteniendo 320 MB de datos utilizables por segundo. La captación previa acerca la tasa al pico de 4000 MB / s. El ahorro total disponible para la captura previa es de 0.92 segundos por cada 320 MB de lectura. A 320 MB / s, 270 segundos (4m 30s) equivalen a 840 GB de tiempo de transferencia de memoria; el programa probablemente no gaste más de una pequeña fracción de esto (<1%, 8GB) en la lectura de la memoria. La eliminación completa de la memoria I / O ahorraría ... 1% del tiempo de ejecución.

El inconveniente de la obtención previa de demasiados datos es que los datos preconfigurados desplazan las cosas útiles de la memoria realmente rápida pero realmente pequeña cerca de la CPU (cachés de nivel 1 y nivel 2, kilobytes, no megabytes). Esto puede explicar el rendimiento pessimal de algunas de las ejecuciones de prueba.

El hecho de desenrollar el bucle aceleró el programa, pero la captura previa tampoco sugirió que el procesamiento en sí sea el cuello de botella principal, no el movimiento de datos.

Usando gcc 4.4.5 (sí ... sé que es viejo) en x86_64. Limitado a las instrucciones SSE2 (o anteriores) por razones de compatibilidad.

Tengo lo que creo que debería ser un caso de libro de texto para obtener grandes beneficios de la obtención previa. Tengo una matriz ("A") de elementos de 32 bits, que no están (y no pueden estar) en orden secuencial. Estos elementos de 32 bits son índices en una matriz de datos más grande ("D") de datos __m128i. Para cada elemento de "A", necesito recuperar los datos __m128i de la ubicación apropiada en "D", realizar una operación en él y almacenarlo nuevamente en la misma ubicación en "D". En realidad, cada "entrada" en D es "SOME_CONST" __m128i es grande. Entonces, si el valor en A es "1", el índice en D es D [1 * SOME_CONST].

Dado que los elementos consecutivos en "A" casi nunca apuntan a ubicaciones secuenciales en "D", tiendo a pensar que el prefetcher de hardware luchará o no logrará nada útil.

Sin embargo, puedo predecir a qué ubicaciones accederé a continuación muy fácilmente, simplemente mirando hacia adelante en "A". Basta de verborrea ... aquí hay un código. La operación que estoy realizando en los datos es tomar los 64 bits inferiores del __m128i y clonarlos a los 64 bits superiores del mismo. Primero el bucle básico, sin lujos ...

// SOME_CONST is either 3 or 4, but this "operation" only needs to happen for 3 for ( i=0; i<arraySize; ++i ) { register __m128i *dPtr = D + (A[i] * SOME_CONST); dPtr[0] = _mm_shuffle_epi32( dPtr[0], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr[1] = _mm_shuffle_epi32( dPtr[1], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr[2] = _mm_shuffle_epi32( dPtr[2], 0 | (1<<2) | (0<<4) | (1<<6) ); // The immediate operand selects: // Bits 0-31 = bits 0-31 // Bits 32-63 = bits 32-63 // Bits 64-95 = bits 0-31 // Bits 96-127 = bits 32-63 // If anyone is more clever than me and knows of a better way to do this in SSE2, // bonus points. ;-) }

He intentado una serie de formas diferentes de esparcir prefinquiricos intrínsecos allí, y ninguno ha resultado en ningún tipo de aceleración todavía. Por ejemplo, intenté desenrollar el bucle para tener un paso de 2 o incluso 4 elementos, pero no ayudó ...

// Assume the "A" array size is appropriately padded so that overruns don''t // result in SIGSEGV accessing uninitialized memory in D. register __m128i *dPtr0, *dPtr1, *dPtr2, *dPtr3, *dPtr4, *dPtr5, *dPtr6, *dPtr7; dPtr4 = D + (A[0] * SOME_CONST); dPtr5 = D + (A[1] * SOME_CONST); dPtr6 = D + (A[2] * SOME_CONST); dPtr7 = D + (A[3] * SOME_CONST); for ( i=0; i<arraySize; i+=4 ) { dPtr0 = dPtr4; dPtr1 = dPtr5; dPtr2 = dPtr6; dPtr3 = dPtr7; dPtr4 = D + (A[i+4] * SOME_CONST); _mm_prefetch( dPtr4, _MM_HINT_NTA ); _mm_prefetch( dPtr4+1, _MM_HINT_NTA ); // Is it needed? Tried both ways dPtr5 = D + (A[i+5] * SOME_CONST); _mm_prefetch( dPtr5, _MM_HINT_NTA ); _mm_prefetch( dPtr5+1, _MM_HINT_NTA ); // Is it needed? Tried both ways dPtr6 = D + (A[i+6] * SOME_CONST); _mm_prefetch( dPtr6, _MM_HINT_NTA ); _mm_prefetch( dPtr6+1, _MM_HINT_NTA ); // Is it needed? Tried both ways dPtr7 = D + (A[i+7] * SOME_CONST); _mm_prefetch( dPtr7, _MM_HINT_NTA ); _mm_prefetch( dPtr7+1, _MM_HINT_NTA ); // Is it needed? Tried both ways dPtr0[0] = _mm_shuffle_epi32( dPtr0[0], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr0[1] = _mm_shuffle_epi32( dPtr0[1], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr0[2] = _mm_shuffle_epi32( dPtr0[2], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr1[0] = _mm_shuffle_epi32( dPtr1[0], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr1[1] = _mm_shuffle_epi32( dPtr1[1], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr1[2] = _mm_shuffle_epi32( dPtr1[2], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr2[0] = _mm_shuffle_epi32( dPtr2[0], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr2[1] = _mm_shuffle_epi32( dPtr2[1], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr2[2] = _mm_shuffle_epi32( dPtr2[2], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr3[0] = _mm_shuffle_epi32( dPtr3[0], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr3[1] = _mm_shuffle_epi32( dPtr3[1], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr3[2] = _mm_shuffle_epi32( dPtr3[2], 0 | (1<<2) | (0<<4) | (1<<6) ); }

Esa es la versión de 4 elementos, pero también probé con solo 2 en caso de que fuera demasiada información para ser utilizada. También intenté usar _MM_HINT_NTA y _MM_HINT_T0. No hay diferencia apreciable de alguna manera.

También probé una variante más simple, que solo intenta poner tanto espacio como parezca razonable entre la captación previa y cuándo se usará:

#define PREFETCH_DISTANCE 10 // trying 5 overnight, will see results tomorrow... for ( i=0; i<arraySize; ++i ) { register __m128i *dPtrFuture, *dPtr; dPtrFuture = D + (A[i + PREFETCH_DISTANCE] * SOME_CONST); _mm_prefetch( dPtrFuture, _MM_HINT_NTA ); // tried _MM_HINT_T0 too _mm_prefetch( dPtrFuture + 1, _MM_HINT_NTA ); // tried _MM_HINT_T0 too dPtr = D + (A[i] * SOME_CONST); dPtr[0] = _mm_shuffle_epi32( dPtr[0], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr[1] = _mm_shuffle_epi32( dPtr[1], 0 | (1<<2) | (0<<4) | (1<<6) ); dPtr[2] = _mm_shuffle_epi32( dPtr[2], 0 | (1<<2) | (0<<4) | (1<<6) ); }

Inicialmente espero que este código se detenga, pero una vez que aparezca "PREFETCH_DISTANCE" en el bucle, esperaba que hubiera un aumento de velocidad lo suficientemente bueno. La mayoría de estas variantes causan no más de .2 segundos de diferencia de tiempo de ejecución en millones de iteraciones, lo que lleva un tiempo total de CPU de 4m: 30s en esta máquina en particular (que está inactiva a menos que yo). Las diferencias parecen ser indistinguibles del "ruido" en los datos.

¿Tengo razón al suponer que la captura previa debería poder ayudarme aquí? Si es así, ¿qué estoy haciendo mal?

Todos los pensamientos útiles e interesantes son apreciados.

EDITAR:

Creé un ejemplo artificial que realmente aleatoriza los datos en A. Jugué con los tamaños de búfer desde 64 MB hasta 6400 MB. Descubrí que obtengo una enorme ganancia al desenrollar el bucle y al pre-calcular las direcciones de los siguientes 4 elementos cuando realizo mi operación en el actual 4. Pero mi tiempo de ejecución se ve afectado por un factor de> 10x si intento realizar una captación previa Cualquiera de las direcciones que he pre-calculado. Realmente me estoy rascando la cabeza en este caso. Mi código artificial independiente es:

#include <xmmintrin.h> #include <stdlib.h> #include <time.h> #include <stdio.h> #define QUEUE_ELEMENTS 1048576 #define DATA_ELEMENT_SIZE 4 * sizeof( __m128i ) #define DATA_ELEMENTS QUEUE_ELEMENTS #define QUEUE_ITERATIONS 100000 #define LOOP_UNROLL_4 #define LOOP_UNROLL_2 #ifdef LOOP_UNROLL_4 #define UNROLL_CONST 4 #else #ifdef LOOP_UNROLL_2 #define UNROLL_CONST 2 #else #define UNROLL_CONST 1 #endif #endif int main( void ) { unsigned long long randTemp; unsigned long i, outerLoop; unsigned long *workQueue; __m128i *data, *dataOrig; clock_t timeStamp; workQueue = malloc( QUEUE_ELEMENTS * sizeof( unsigned long ) ); dataOrig = malloc( (DATA_ELEMENTS * DATA_ELEMENT_SIZE) + 2 ); if ( (unsigned long long) dataOrig & 0xf ) { data = (__m128i *) (((unsigned long long) dataOrig & ~0xf) + 0x10); // force 16-byte (128-bit) alignment } else data = dataOrig; // Not initializing data, because its contents isn''t important. for ( i=0; i<QUEUE_ELEMENTS; ++i ) { randTemp = (unsigned long long)rand() * (unsigned long long) QUEUE_ELEMENTS / (unsigned long long) RAND_MAX; workQueue[i] = (unsigned long) randTemp; } printf( "Starting work.../n" ); // Actual work happening below... start counting. timeStamp = clock(); for ( outerLoop = 0; outerLoop < QUEUE_ITERATIONS; ++outerLoop ) { register __m128i *dataPtr0, *dataPtr1, *dataPtr2, *dataPtr3; register __m128i *dataPtr4, *dataPtr5, *dataPtr6, *dataPtr7; #ifdef LOOP_UNROLL_2 dataPtr4 = data + (workQueue[0] * DATA_ELEMENT_SIZE); dataPtr5 = data + (workQueue[1] * DATA_ELEMENT_SIZE); #endif #ifdef LOOP_UNROLL_4 dataPtr6 = data + (workQueue[2] * DATA_ELEMENT_SIZE); dataPtr7 = data + (workQueue[3] * DATA_ELEMENT_SIZE); #endif for ( i=0; i<QUEUE_ELEMENTS; i+=UNROLL_CONST ) { #ifdef LOOP_UNROLL_2 dataPtr0 = dataPtr4; dataPtr4 = data + (workQueue[i+4] * DATA_ELEMENT_SIZE); // _mm_prefetch( dataPtr4, _MM_HINT_T0 ); dataPtr1 = dataPtr5; dataPtr5 = data + (workQueue[i+5] * DATA_ELEMENT_SIZE); // _mm_prefetch( dataPtr5, _MM_HINT_T0 ); #endif #ifdef LOOP_UNROLL_4 dataPtr2 = dataPtr6; dataPtr6 = data + (workQueue[i+6] * DATA_ELEMENT_SIZE); // _mm_prefetch( dataPtr6, _MM_HINT_T0 ); dataPtr3 = dataPtr7; dataPtr7 = data + (workQueue[i+7] * DATA_ELEMENT_SIZE); // _mm_prefetch( dataPtr7, _MM_HINT_T0 ); #endif #if !defined( LOOP_UNROLL_2 ) && !defined( LOOP_UNROLL_4 ) dataPtr0 = data + (workQueue[i] * DATA_ELEMENT_SIZE); #endif _mm_shuffle_epi32( dataPtr0[0], 0 | (1<<2) | (0<<4) | (1<<6) ); _mm_shuffle_epi32( dataPtr0[1], 0 | (1<<2) | (0<<4) | (1<<6) ); _mm_shuffle_epi32( dataPtr0[2], 0 | (1<<2) | (0<<4) | (1<<6) ); // Per original code, no need to perform operation on dataPtrx[3] #ifdef LOOP_UNROLL_2 _mm_shuffle_epi32( dataPtr1[0], 0 | (1<<2) | (0<<4) | (1<<6) ); _mm_shuffle_epi32( dataPtr1[1], 0 | (1<<2) | (0<<4) | (1<<6) ); _mm_shuffle_epi32( dataPtr1[2], 0 | (1<<2) | (0<<4) | (1<<6) ); #endif #ifdef LOOP_UNROLL_4 _mm_shuffle_epi32( dataPtr2[0], 0 | (1<<2) | (0<<4) | (1<<6) ); _mm_shuffle_epi32( dataPtr2[1], 0 | (1<<2) | (0<<4) | (1<<6) ); _mm_shuffle_epi32( dataPtr2[2], 0 | (1<<2) | (0<<4) | (1<<6) ); _mm_shuffle_epi32( dataPtr3[0], 0 | (1<<2) | (0<<4) | (1<<6) ); _mm_shuffle_epi32( dataPtr3[1], 0 | (1<<2) | (0<<4) | (1<<6) ); _mm_shuffle_epi32( dataPtr3[2], 0 | (1<<2) | (0<<4) | (1<<6) ); #endif } if ( (outerLoop % 1000) == 0 ) { putchar( ''.'' ); fflush( stdout ); } } timeStamp = clock() - timeStamp; printf( "/nRun was %lu seconds./n", timeStamp / CLOCKS_PER_SEC ); free( dataOrig ); free( workQueue ); return 0; }

  • Mi tiempo de ejecución con LOOP_UNROLL_2 es ​​de 40 segundos.
  • Mi tiempo de ejecución con LOOP_UNROLL_4 es de 20 segundos.
  • Mi tiempo de ejecución sin ningún tipo de desenrollado es de 80 segundos.
  • Cuando habilito los prefetches, el tiempo de ejecución es tan largo que simplemente mato el proceso en lugar de esperar.

Incluso escribí un bucle desenrollado de 8x, y aún así se escalaba perfectamente a 10 segundos de tiempo de ejecución. Me sorprende que no se saturara allí porque en ese momento me quedaría sin registros, con 16 punteros únicos. Entonces, ¿qué puedo aprender de esto? ¿Que mi código de bucle interno es tan estricto que queda muy opacado por la sobrecarga en la propia construcción del bucle? ¿Hay algún error en este código que no esté viendo? Todas las construcciones fueron con gcc -O2 .