¿Ejemplos de captura previa?

¿Alguien puede dar un ejemplo o un enlace a un ejemplo que utiliza __builtin_prefetch en GCC (o simplemente la instrucción asm prefetcht0 en general) para obtener una ventaja de rendimiento sustancial? En particular, me gustaría que el ejemplo cumpla con los siguientes criterios:

  1. Es un ejemplo simple, pequeño e independiente.
  2. Al eliminar la instrucción __builtin_prefetch , se __builtin_prefetch rendimiento.
  3. Reemplazar la instrucción __builtin_prefetch con el acceso de memoria correspondiente produce una degradación del rendimiento.

Es decir, quiero que el ejemplo más breve muestre __builtin_prefetch realizando una optimización que no podría gestionarse sin él.

Aquí hay una pieza real de código que he sacado de un proyecto más grande. (Lo siento, es el más corto que puedo encontrar que tuvo una aceleración notable de la captación previa.) Este código realiza una transposición de datos muy grande.

Este ejemplo utiliza las instrucciones de captación previa de SSE, que pueden ser las mismas que emite GCC.

Para ejecutar este ejemplo, deberá comstackr esto para x64 y tener más de 4 GB de memoria. Puede ejecutarlo con un tamaño de datos más pequeño, pero será demasiado rápido para el tiempo.

 #include  using std::cout; using std::endl; #include  #include  #include  

Cuando lo ejecuto con ENABLE_PREFETCH habilitado, este es el resultado:

 bytes = 4294967296 Starting Data Transpose... Done Time: 0.725 seconds Press any key to continue . . . 

Cuando lo ejecuto con ENABLE_PREFETCH desactivado, este es el resultado:

 bytes = 4294967296 Starting Data Transpose... Done Time: 0.822 seconds Press any key to continue . . . 

Así que hay un 13% de aceleración de la captación previa.

EDITAR:

Aquí hay algunos más resultados:

 Operating System: Windows 7 Professional/Ultimate Compiler: Visual Studio 2010 SP1 Compile Mode: x64 Release Intel Core i7 860 @ 2.8 GHz, 8 GB DDR3 @ 1333 MHz Prefetch : 0.868 No Prefetch: 0.960 Intel Core i7 920 @ 3.5 GHz, 12 GB DDR3 @ 1333 MHz Prefetch : 0.725 No Prefetch: 0.822 Intel Core i7 2600K @ 4.6 GHz, 16 GB DDR3 @ 1333 MHz Prefetch : 0.718 No Prefetch: 0.796 2 x Intel Xeon X5482 @ 3.2 GHz, 64 GB DDR2 @ 800 MHz Prefetch : 2.273 No Prefetch: 2.666 

La búsqueda binaria es un ejemplo simple que podría beneficiarse de la captación previa explícita. El patrón de acceso en una búsqueda binaria parece bastante aleatorio para el captador previo de hardware, por lo que hay pocas posibilidades de que prediga con precisión qué recuperar.

En este ejemplo, prefiero las dos ubicaciones “intermedias” posibles de la siguiente iteración de bucle en la iteración actual. Es probable que nunca se use uno de los prefetches, pero el otro lo hará (a menos que sea la iteración final).

  #include 

Cuando compilo y ejecuto este ejemplo con DO_PREFETCH activado, veo una reducción del 20% en el tiempo de ejecución:

  $ gcc c-binarysearch.c -DDO_PREFETCH -o with-prefetch -std=c11 -O3 $ gcc c-binarysearch.c -o no-prefetch -std=c11 -O3 $ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./with-prefetch Performance counter stats for './with-prefetch': 356,675,702 L1-dcache-load-misses # 41.39% of all L1-dcache hits 861,807,382 L1-dcache-loads 8.787467487 seconds time elapsed $ perf stat -e L1-dcache-load-misses,L1-dcache-loads ./no-prefetch Performance counter stats for './no-prefetch': 382,423,177 L1-dcache-load-misses # 97.36% of all L1-dcache hits 392,799,791 L1-dcache-loads 11.376439030 seconds time elapsed 

Tenga en cuenta que estamos haciendo el doble de cargas de caché L1 en la versión de búsqueda previa. De hecho, estamos trabajando mucho más, pero el patrón de acceso a la memoria es más amigable con la tubería. Esto también muestra la compensación. Si bien este bloque de código se ejecuta más rápido de forma aislada, hemos cargado una gran cantidad de basura en las memorias caché y esto puede ejercer más presión sobre otras partes de la aplicación.

De la documentación :

  for (i = 0; i < n; i++) { a[i] = a[i] + b[i]; __builtin_prefetch (&a[i+j], 1, 1); __builtin_prefetch (&b[i+j], 0, 1); /* ... */ } 

Aprendí mucho de las excelentes respuestas proporcionadas por @JamesScriven y @Mystical. Sin embargo, sus ejemplos dan un impulso modesto: el objective de esta respuesta es presentar un ejemplo (debo confesar algo artificial), donde la captación previa tiene un mayor impacto (alrededor del factor 4 en mi máquina).

Hay tres posibles cuellos de botella para las architectures modernas: velocidad de CPU, ancho de banda de memoria y latencia de memoria. La captura previa se trata de reducir la latencia de los accesos a la memoria.

En un escenario perfecto, donde la latencia corresponde a los pasos de cálculo X, tendríamos un oracle, que nos diría a qué memoria accederíamos en X pasos de cálculo, se lanzaría la captación previa de estos datos y llegaría solo a Cálculo del tiempo X: pasos más adelante.

Para muchos algoritmos estamos (casi) en este mundo perfecto. Para un simple for-loop es fácil predecir qué datos se necesitarán X pasos más adelante. La ejecución fuera de servicio y otros trucos de hardware están haciendo un muy buen trabajo aquí, ocultando la latencia casi por completo.

Esa es la razón, por la cual hay una mejora tan modesta para el ejemplo de @Mystical: el captador previo ya es bastante bueno; simplemente no hay mucho margen de mejora. La tarea también está vinculada a la memoria, por lo que probablemente no quede mucho ancho de banda, podría convertirse en el factor limitante. Pude ver, en el mejor de los casos, una mejora del 8% en mi máquina.

La idea crucial del ejemplo de @JamesScriven: ni nosotros ni la CPU conocemos la siguiente dirección de acceso antes de que se obtengan los datos actuales de la memoria: esta dependencia es muy importante, de lo contrario, la ejecución desordenada daría lugar a una mirada anticipada. y el hardware sería capaz de captar previamente los datos. Sin embargo, como podemos especular sobre un solo paso, no hay mucho potencial. No pude obtener más del 40% en mi máquina.

Así que manipulemos la competencia y preparemos los datos de tal forma que sepamos a qué dirección se accede en X pasos, pero imposibilite que el hardware lo descubra debido a las dependencias de los datos aún no accedidos (consulte el progtwig completo al final de la respuesta):

 //making random accesses to memory: unsigned int next(unsigned int current){ return (current*10001+328)%SIZE; } //the actual work is happening here void operator()(){ //set up the oracle - let see it in the future oracle_offset steps unsigned int prefetch_index=0; for(int i=0;i 

Algunas observaciones:

  1. los datos están preparados de tal manera que el oracle siempre está en lo cierto.
  2. Sorprendentemente, cuanto menor sea la tarea vinculada a la CPU, mayor será la aceleración: podemos ocultar la latencia casi por completo, por lo tanto, la aceleración es CPU-time+original-latency-time/CPU-time .

Comstackndo y ejecutando clientes potenciales:

 >>> g++ -std=c++11 prefetch_demo.cpp -O3 -o prefetch_demo >>> ./prefetch_demo #preloops time no prefetch time prefetch factor ... 7 1.0711102260000001 0.230566831 4.6455521002498408 8 1.0511602149999999 0.22651144600000001 4.6406494398521474 9 1.049024333 0.22841439299999999 4.5926367389641687 .... 

a una aceleración entre 4 y 5.


Listado de prefetch_demp.cpp :

 //prefetch_demo.cpp #include  #include  #include  #include  const int SIZE=1024*1024*1; const int STEP_CNT=1024*1024*10; unsigned int next(unsigned int current){ return (current*10001+328)%SIZE; } template struct Worker{ std::vector mem; double result; int oracle_offset; void operator()(){ unsigned int prefetch_index=0; for(int i=0;i &mem_): mem(mem_), result(0.0), oracle_offset(0) {} }; template  double timeit(Worker &worker){ auto begin = std::chrono::high_resolution_clock::now(); worker(); auto end = std::chrono::high_resolution_clock::now(); return std::chrono::duration_cast(end-begin).count()/1e9; } int main() { //set up the data in special way! std::vector keys(SIZE); for (int i=0;i without_prefetch(keys); Worker with_prefetch(keys); std::cout< <"#preloops\ttime no prefetch\ttime prefetch\tfactor\n"; std::cout<