¿Por qué es que en ciclos separados los suplementos de estigma son mucho más rápidos que en el ciclo combinado?

Supongamos que a1 , b1 , c1 y d1 apuntan a la memoria del montón, y mi código numérico tiene el siguiente bucle principal.

 const int n = 100000; for (int j = 0; j < n; j++) { a1[j] += b1[j]; c1[j] += d1[j]; } 

Este bucle se ejecuta 10.000 veces a través de otro bucle for externo. Para acelerarlo, cambié el código a:

 for (int j = 0; j < n; j++) { a1[j] += b1[j]; } for (int j = 0; j < n; j++) { c1[j] += d1[j]; } 

Compilado en MS Visual C ++ 10.0 con optimización completa y SSE2 habilitado para 32 bits en Intel Core 2 Duo (x64), el primer ejemplo toma 5.5 segundos y el ejemplo con un bucle doble toma solo 1.9 segundos. Mi pregunta es: (Por favor, consulte mi pregunta reconsiderada a continuación)

PD: No estoy seguro de si esto ayudará:

El desmontaje para el primer ciclo básicamente tiene este aspecto (este bloque se repite unas cinco veces en el programa completo):

 movsd xmm0,mmword ptr [edx+18h] addsd xmm0,mmword ptr [ecx+20h] movsd mmword ptr [ecx+20h],xmm0 movsd xmm0,mmword ptr [esi+10h] addsd xmm0,mmword ptr [eax+30h] movsd mmword ptr [eax+30h],xmm0 movsd xmm0,mmword ptr [edx+20h] addsd xmm0,mmword ptr [ecx+28h] movsd mmword ptr [ecx+28h],xmm0 movsd xmm0,mmword ptr [esi+18h] addsd xmm0,mmword ptr [eax+38h] 

Cada bucle en el ejemplo de bucle doble crea este código (el siguiente bloque se repite aproximadamente tres veces):

 addsd xmm0,mmword ptr [eax+28h] movsd mmword ptr [eax+28h],xmm0 movsd xmm0,mmword ptr [ecx+20h] addsd xmm0,mmword ptr [eax+30h] movsd mmword ptr [eax+30h],xmm0 movsd xmm0,mmword ptr [ecx+28h] addsd xmm0,mmword ptr [eax+38h] movsd mmword ptr [eax+38h],xmm0 movsd xmm0,mmword ptr [ecx+30h] addsd xmm0,mmword ptr [eax+40h] movsd mmword ptr [eax+40h],xmm0 

La pregunta resultó ser irrelevante, ya que el comportamiento depende en gran medida del tamaño de las matrices (n) y del caché de la CPU. Entonces, si hay más interés, reformulo la pregunta:

¿Podría darnos una idea detallada de los detalles que conducen a diferentes comportamientos de caché, como se muestra en las cinco áreas en el siguiente gráfico?

También sería interesante señalar las diferencias entre la CPU y las arquitecturas de caché, proporcionando una programación similar para estas CPU.

PPS: aquí está el código completo. Utiliza TBB Tick_Count para sincronizar con una resolución más alta, que se puede desactivar sin especificar TBB_TIMING :

 #include <iostream> #include <iomanip> #include <cmath> #include <string> //#define TBB_TIMING #ifdef TBB_TIMING #include <tbb/tick_count.h> using tbb::tick_count; #else #include <time.h> #endif using namespace std; //#define preallocate_memory new_cont enum { new_cont, new_sep }; double *a1, *b1, *c1, *d1; void allo(int cont, int n) { switch(cont) { case new_cont: a1 = new double[n*4]; b1 = a1 + n; c1 = b1 + n; d1 = c1 + n; break; case new_sep: a1 = new double[n]; b1 = new double[n]; c1 = new double[n]; d1 = new double[n]; break; } for (int i = 0; i < n; i++) { a1[i] = 1.0; d1[i] = 1.0; c1[i] = 1.0; b1[i] = 1.0; } } void ff(int cont) { switch(cont){ case new_sep: delete[] b1; delete[] c1; delete[] d1; case new_cont: delete[] a1; } } double plain(int n, int m, int cont, int loops) { #ifndef preallocate_memory allo(cont,n); #endif #ifdef TBB_TIMING tick_count t0 = tick_count::now(); #else clock_t start = clock(); #endif if (loops == 1) { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++){ a1[j] += b1[j]; c1[j] += d1[j]; } } } else { for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { a1[j] += b1[j]; } for (int j = 0; j < n; j++) { c1[j] += d1[j]; } } } double ret; #ifdef TBB_TIMING tick_count t1 = tick_count::now(); ret = 2.0*double(n)*double(m)/(t1-t0).seconds(); #else clock_t end = clock(); ret = 2.0*double(n)*double(m)/(double)(end - start) *double(CLOCKS_PER_SEC); #endif #ifndef preallocate_memory ff(cont); #endif return ret; } void main() { freopen("C:\\test.csv", "w", stdout); char *s = " "; string na[2] ={"new_cont", "new_sep"}; cout << "n"; for (int j = 0; j < 2; j++) for (int i = 1; i <= 2; i++) #ifdef preallocate_memory cout << s << i << "_loops_" << na[preallocate_memory]; #else cout << s << i << "_loops_" << na[j]; #endif cout << endl; long long nmax = 1000000; #ifdef preallocate_memory allo(preallocate_memory, nmax); #endif for (long long n = 1L; n < nmax; n = max(n+1, long long(n*1.2))) { const long long m = 10000000/n; cout << n; for (int j = 0; j < 2; j++) for (int i = 1; i <= 2; i++) cout << s << plain(n, m, j, i); cout << endl; } } 

(Muestra FLOP / s para diferentes valores de n .)

2019

2073
17 дек. Johannes Gerer ambientó el 17 de diciembre. 2011-12-17 23:40 '11 a las 23:40 2011-12-17 23:40
@ 10 respuestas

Tras un análisis adicional de esto, creo que esto (al menos en parte) se debe a la alineación de los cuatro punteros. Esto conducirá a algún conflicto de caché / ruta.

Si entiendo correctamente cómo asignas tus arreglos, lo más probable es que estén alineados con la cadena de la página .

Esto significa que todas sus llamadas en cada ciclo caerán en el mismo archivo de caché. Sin embargo, los procesadores Intel durante algún tiempo tuvieron una asociatividad de caché L1 de 8 vías. Pero en realidad el rendimiento no es completamente uniforme. El acceso a los canales de 4 canales sigue siendo más lento que el de dos vías.

EDIT: De hecho, parece que selecciona todos los arreglos por separado. Por lo general, cuando se solicitan grandes asignaciones, el distribuidor solicita nuevas páginas del sistema operativo. Por lo tanto, existe una alta probabilidad de que se muestren grandes selecciones con el mismo desplazamiento desde el borde de la página.

Aquí está el código de prueba:

 int main(){ const int n = 100000; #ifdef ALLOCATE_SEPERATE double *a1 = (double*)malloc(n * sizeof(double)); double *b1 = (double*)malloc(n * sizeof(double)); double *c1 = (double*)malloc(n * sizeof(double)); double *d1 = (double*)malloc(n * sizeof(double)); #else double *a1 = (double*)malloc(n * sizeof(double) * 4); double *b1 = a1 + n; double *c1 = b1 + n; double *d1 = c1 + n; #endif // Zero the data to prevent any chance of denormals. memset(a1,0,n * sizeof(double)); memset(b1,0,n * sizeof(double)); memset(c1,0,n * sizeof(double)); memset(d1,0,n * sizeof(double)); // Print the addresses cout << a1 << endl; cout << b1 << endl; cout << c1 << endl; cout << d1 << endl; clock_t start = clock(); int c = 0; while (c++ < 10000){ #if ONE_LOOP for(int j=0;j<n;j++){ a1[j] += b1[j]; c1[j] += d1[j]; } #else for(int j=0;j<n;j++){ a1[j] += b1[j]; } for(int j=0;j<n;j++){ c1[j] += d1[j]; } #endif } clock_t end = clock(); cout << "seconds = " << (double)(end - start) / CLOCKS_PER_SEC << endl; system("pause"); return 0; } 

Resultados de la prueba:

EDITAR: Resultados en Core 2 Real Architecture:

2 x Intel Xeon X5482 Harpertown a 3.2 GHz:

 #define ALLOCATE_SEPERATE #define ONE_LOOP 00600020 006D0020 007A0020 00870020 seconds = 6.206 #define ALLOCATE_SEPERATE //#define ONE_LOOP 005E0020 006B0020 00780020 00850020 seconds = 2.116 //#define ALLOCATE_SEPERATE #define ONE_LOOP 00570020 00633520 006F6A20 007B9F20 seconds = 1.894 //#define ALLOCATE_SEPERATE //#define ONE_LOOP 008C0020 00983520 00A46A20 00B09F20 seconds = 1.993 

observaciones:

  • 6.206 segundos con un ciclo y 2.116 segundos con dos ciclos. Esto reproduce con precisión los resultados del OP.

  • En las dos primeras pruebas, las matrices se asignan por separado. Notará que todos tienen la misma alineación con respecto a la página.

  • En las segundas dos pruebas, las matrices se empaquetan juntas para romper esta alineación. Aquí notarás que ambos ciclos son más rápidos. Además, el segundo ciclo (doble) ahora es más lento, como suele esperarse.

Como señala @Stephen Cannon en los comentarios, es muy probable que esta alineación cause un falso alisado en términos de carga / almacenamiento o caché. Lo pensé y descubrí que Intel en realidad tiene un contador de hardware para suavizar las direcciones parciales :

http://software.intel.com/sites/products/documentation/doclib/stdxe/2013/~amplifierxe/pmw_dp/events/partial_address_alias.html


5 Regiones - Explicaciones

Región 1:

Es facil El conjunto de datos es tan pequeño que prevalecen los costos generales, como el ciclo y la ramificación.

Región 2:

Aquí, cuando los tamaños de los datos aumentan, el número de gastos generales relativos disminuye y el rendimiento está "saturado". Aquí, dos ciclos son más lentos, porque tiene el doble de hilos y ramas.

No estoy seguro de lo que está sucediendo aquí ... La alineación aún puede tener un efecto, ya que Agner Fog menciona conflictos de caché de banco . (Este enlace se aplica a Sandy Bridge, pero la idea debería aplicarse a Core 2.)

Región 3:

En este punto, los datos ya no caben en el caché L1. Por lo tanto, el rendimiento está limitado por el ancho de banda L1 ↔ L2.

Región 4:

Lo que observamos es la disminución del rendimiento en un ciclo. Y, como ya se mencionó, esto se debe a la alineación, que (lo más probable) causa el bloqueo de falsos alias en los bloques de almacenamiento / carga del procesador.

Sin embargo, para que se produzca un suavizado falso, debe haber un paso suficientemente grande entre los conjuntos de datos. Por eso no lo ves en la región 3.

Región 5:

En este punto, nada cabe en el caché. Así que estás conectado por el ancho de banda de la memoria.


2019

1585
18 дек. La respuesta es mística 18 dic. 2011-12-18 00:17 '11 a las 0:17 2011-12-18 00:17

OK, la respuesta correcta definitivamente debería hacer algo con el caché del procesador. Pero usar el argumento del caché puede ser bastante complicado, especialmente sin datos.

Hay muchas respuestas que llevaron a mucha discusión, pero déjalos enfrentar esto: los problemas de caché pueden ser muy complejos y no unidimensionales. Son muy dependientes del tamaño de los datos, por lo que mi pregunta fue injusta: resultó ser muy interesante en el gráfico de caché.

@ La respuesta mística convenció a muchas personas (incluyéndome a mí), probablemente porque él era el único que parecía confiar en los hechos, pero era solo un "punto de datos" de la verdad.

Por eso combiné su prueba (utilizando una distribución continua o separada) y la respuesta @James Answer.

Los gráficos a continuación muestran que la mayoría de las respuestas, y especialmente la mayoría de los comentarios a la pregunta y las respuestas, pueden considerarse completamente erróneas o verdaderas, según el escenario específico y los parámetros utilizados.

Tenga en cuenta que mi pregunta inicial fue n = 100.000 . Este punto (por casualidad) exhibe un comportamiento especial:

  • Tiene la mayor discrepancia entre una y dos versiones del ciclo (casi tres veces)

  • Este es el único punto donde el bucle único (es decir, la distribución continua) excede la versión de dos bucles. (Esto hizo posible la respuesta mística).

Resultado utilizando datos inicializados:

2019

203
18 дек. Respuesta dada por Johannes Gerer 18 de diciembre 2011-12-18 04:29 '11 a las 4:29 2011-12-18 04:29

El segundo ciclo incluye mucha menos actividad de caché, por lo que el procesador es más fácil de mantener los requisitos de memoria.

69
17 дек. Respuesta dada cachorro 17 de diciembre 2011-12-17 23:47 '11 a las 23:47 2011-12-17 23:47

Imagine que está trabajando en una máquina donde n era el valor correcto para poder almacenar simultáneamente dos de sus arreglos en la memoria, pero la cantidad total de memoria disponible a través del almacenamiento en caché del disco aún era suficiente para almacenar los cuatro.

Suponiendo una política de almacenamiento en caché LIFO simple, este código:

 for(int j=0;j<n;j++){ a[j] += b[j]; } for(int j=0;j<n;j++){ c[j] += d[j]; } 

primero hará que a y b carguen en la RAM, y luego se trabajará completamente en la RAM. Cuando comienza el segundo ciclo, d cargan desde el disco en la RAM y funcionan.

otro ciclo

 for(int j=0;j<n;j++){ a[j] += b[j]; c[j] += d[j]; } 

generará dos matrices y una página en otras dos cada vez que se realice el bucle . Esto obviamente será mucho más lento.

Probablemente no vea el almacenamiento en caché del disco en sus pruebas, pero probablemente vea los efectos secundarios de alguna otra forma de almacenamiento en caché.


Parece que hay un poco de confusión / malentendido aquí, así que intentaré aclarar un poco con el ejemplo.

Diga n = 2 y estamos trabajando con bytes. Por lo tanto, en mi escenario, solo tenemos 4 bytes de RAM, y el resto de la memoria es mucho más lento (por ejemplo, 100 veces más acceso).

Suponiendo una política de almacenamiento en caché bastante estúpida, si un byte no está en el caché, póngalo allí y obtenga el siguiente byte mientras estamos en él, obtendrá una secuencia de comandos como esta:

  • Con

     for(int j=0;j<n;j++){ a[j] += b[j]; } for(int j=0;j<n;j++){ c[j] += d[j]; } 
  • cacheamos a[0] y a[1] luego b[0] y b[1] y configuramos a[0] = a[0] + b[0] a la caché - ahora hay cuatro bytes en la caché, a[0], a[1] b[0], b[1] . Costo = 100 + 100.

  • establece a[1] = a[1] + b[1] en el caché. Costo = 1 + 1.
  • Repita para c y d .
  • Costo total = (100 + 100 + 1 + 1) * 2 = 404

  • Con

     for(int j=0;j<n;j++){ a[j] += b[j]; c[j] += d[j]; } 
  • cacheamos a[0] y a[1] luego b[0] y b[1] y configuramos a[0] = a[0] + b[0] a la caché - ahora hay cuatro bytes en la caché, a[0], a[1] b[0], b[1] . Costo = 100 + 100.

  • elimine a[0], a[1], b[0], b[1] de la caché y caché c[0] c[1] luego d[0] d[1] y establezca c[0] = c[0] + d[0] en el caché. Costo = 100 + 100.
  • Sospecho que estás empezando a ver a dónde voy.
  • Costo total = (100 + 100 + 100 + 100) * 2 = 800

Este es un escenario clásico de caché de basura.

41
18 дек. La respuesta es dada por OldCurmudgeon 18 de diciembre. 2011-12-18 04:36 '11 a las 4:36 2011-12-18 04:36

Esto no se debe a un código diferente, sino a causa del almacenamiento en caché: la RAM es más lenta que los registros del procesador, y la memoria caché está dentro de la CPU para evitar escribir la RAM cada vez que cambia la variable. Pero el caché es pequeño, ya que RAM, por lo tanto, solo muestra parte de él.

El primer código cambia las direcciones de la memoria remota, alternándolas en cada ciclo, por lo que es necesario descartar constantemente el caché.

El segundo código no se alterna: simplemente se mueve a direcciones adyacentes dos veces. Esto hace que todas las tareas se completen en el caché, cancelando solo después de iniciar el segundo ciclo.

29
17 дек. Respuesta dada por Emilio Garavaglia el 17 de diciembre. 2011-12-17 23:49 '11 a las 11:49 PM 2011-12-17 23:49

No puedo repetir los resultados discutidos aquí.

No sé si la culpa es del código de prueba incorrecto, o qué, pero estos dos métodos están dentro del 10% uno del otro en mi máquina utilizando el siguiente código, y un ciclo suele ser un poco más rápido que dos, como es de esperar.

Los tamaños de los arreglos variaron de 2 ^ 16 a 2 ^ 24 usando ocho ciclos. Tuve cuidado de inicializar los arreglos originales para que la asignación += no pidiera a la FPU que agregue basura de memoria, interpretada como doble.

InitToZero[j] con varios esquemas, como colocar la asignación b[j] , d[j] para InitToZero[j] dentro de los ciclos, así como usar += b[j] = 1 y += d[j] = 1 , y Obtuve resultados bastante consistentes.

Como era de esperar, la inicialización de d dentro del bucle utilizando InitToZero[j] le dio una ventaja al enfoque combinado, ya que se llevaron a cabo de manera precisa antes de asignar a y c , pero aún dentro del 10%. Ve a averiguarlo.

Hardware: Dell XPS 8500 con 3 procesadores Core i7 a 3,4 GHz y 8 GB de memoria. Para 2 ^ 16 a 2 ^ 24, usando ocho ciclos, el tiempo acumulado fue 44,987 y 40,965 respectivamente. Visual C ++ 2010 está totalmente optimizado.

PD: cambié los ciclos de cuenta atrás a cero, y el método combinado fue un poco más rápido. Rascarse la cabeza Observe el nuevo tamaño de la matriz y el número de ciclos.

 // MemBufferMystery.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <iostream> #include <cmath> #include <string> #include <time.h> #define dbl double #define MAX_ARRAY_SZ 262145 //16777216 // AKA (2^24) #define STEP_SZ 1024 // 65536 // AKA (2^16) int _tmain(int argc, _TCHAR* argv[]) { long i, j, ArraySz = 0, LoopKnt = 1024; time_t start, Cumulative_Combined = 0, Cumulative_Separate = 0; dbl *a = NULL, *b = NULL, *c = NULL, *d = NULL, *InitToOnes = NULL; a = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); b = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); c = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); d = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); InitToOnes = (dbl *)calloc( MAX_ARRAY_SZ, sizeof(dbl)); // Initialize array to 1.0 second. for(j = 0; j< MAX_ARRAY_SZ; j++) { InitToOnes[j] = 1.0; } // Increase size of arrays and time for(ArraySz = STEP_SZ; ArraySz<MAX_ARRAY_SZ; ArraySz += STEP_SZ) { a = (dbl *)realloc(a, ArraySz * sizeof(dbl)); b = (dbl *)realloc(b, ArraySz * sizeof(dbl)); c = (dbl *)realloc(c, ArraySz * sizeof(dbl)); d = (dbl *)realloc(d, ArraySz * sizeof(dbl)); // Outside the timing loop, initialize // b and d arrays to 1.0 sec for consistent += performance. memcpy((void *)b, (void *)InitToOnes, ArraySz * sizeof(dbl)); memcpy((void *)d, (void *)InitToOnes, ArraySz * sizeof(dbl)); start = clock(); for(i = LoopKnt; i; i--) { for(j = ArraySz; j; j--) { a[j] += b[j]; c[j] += d[j]; } } Cumulative_Combined += (clock()-start); printf("\n %6i miliseconds for combined array sizes %i and %i loops", (int)(clock()-start), ArraySz, LoopKnt); start = clock(); for(i = LoopKnt; i; i--) { for(j = ArraySz; j; j--) { a[j] += b[j]; } for(j = ArraySz; j; j--) { c[j] += d[j]; } } Cumulative_Separate += (clock()-start); printf("\n %6i miliseconds for separate array sizes %i and %i loops \n", (int)(clock()-start), ArraySz, LoopKnt); } printf("\n Cumulative combined array processing took %10.3f seconds", (dbl)(Cumulative_Combined/(dbl)CLOCKS_PER_SEC)); printf("\n Cumulative seperate array processing took %10.3f seconds", (dbl)(Cumulative_Separate/(dbl)CLOCKS_PER_SEC)); getchar(); free(a); free(b); free(c); free(d); free(InitToOnes); return 0; } 

No estoy seguro de por qué se decidió que MFLOPS era un indicador relevante. Aunque la idea era centrarse en el acceso a la memoria, intenté minimizar el tiempo de flotación. Fui a += , pero no estoy seguro de por qué.

Una asignación directa sin cálculos sería una prueba más precisa del tiempo de acceso a la memoria y crearía una prueba que sería uniforme independientemente del número de ciclos. Tal vez me perdí algo en la conversación, pero vale la pena pensarlo dos veces. Si el signo más no está incluido en la tarea, el tiempo acumulado es casi el mismo y es de 31 segundos.

18
30 дек. La respuesta la da el usuario 1899861 30 de diciembre. 2012-12-30 04:34 '12 a las 4:34 2012-12-30 04:34

Esto se debe a que el procesador no tiene tantos fallos de caché (donde tiene que esperar a que los datos de la matriz provengan de los chips de RAM). Sería interesante ajustar el tamaño de los arreglos todo el tiempo para que exceda el tamaño del nivel de caché 1 (L1) y luego el nivel de caché 2 (L2) de su procesador y calcule el tiempo empleado en ejecutar el código contra el tamaño de los arreglos. La gráfica no debe ser directa, como cabría esperar.

15
17 дек. Respuesta dada por James el 17 de diciembre. 2011-12-17 23:52 '11 a las 11:52 PM 2011-12-17 23:52

El primer bucle alterna la entrada en cada variable. El segundo y el tercero solo hacen pequeños saltos de tamaño de elemento.

Intenta escribir dos líneas paralelas de 20 cruces con un bolígrafo y una hoja, separados por 20 centímetros. Intente terminar una y luego otra línea una vez e intente nuevamente presionando la cruz en cada línea alternativamente.

13
17 авг. La respuesta se da Guillaume Kiz 17 ago. 2012-08-17 18:23 '12 a las 18:23 2012-08-17 18:23

Pregunta original

¿Por qué un ciclo es mucho más lento que dos?


Conclusión:

El caso 1 es un problema clásico de interpolación que no es efectivo. También creo que esta fue una de las razones principales por las que muchas arquitecturas de máquinas y desarrolladores han terminado de crear y diseñar sistemas de múltiples núcleos con la capacidad de ejecutar aplicaciones de múltiples subprocesos, así como la programación paralela.

Teniendo en cuenta esto, utilice este enfoque, sin afectar la forma en que el hardware, el sistema operativo y los compiladores trabajan juntos para resaltar el montón, que incluye el trabajo con RAM, caché, archivos de paginación, etc .; Las matemáticas que subyacen a estos algoritmos nos muestran cuál de estas dos opciones es la mejor solución. Podemos usar la analogía, donde Boss o Summation , que será un For Loop , que debería moverse entre B trabajadores A y B , podemos ver fácilmente que el caso 2 es al menos 1/2 , con qué rapidez, si no un poco más, caso 1 debido a la diferencia en la distancia requerida para el viaje y el tiempo empleado entre los trabajadores. Estas matemáticas son casi virtuales y coinciden perfectamente tanto con Bench Mark Times como con la diferencia en las instrucciones de montaje.

Ahora comenzaré a explicar cómo funciona todo a continuación.


Evaluando el problema

Código OP:

 const int n=100000; for(int j=0;j<n;j++){ a1[j] += b1[j]; c1[j] += d1[j]; } 

Como bien

 for(int j=0;j<n;j++){ a1[j] += b1[j]; } for(int j=0;j<n;j++){ c1[j] += d1[j]; } 

Consideración

Teniendo en cuenta la pregunta OP original sobre dos variantes de bucles for y su pregunta corregida sobre el comportamiento de las memorias caché, así como muchas otras respuestas excelentes y comentarios útiles; Я хотел бы попытаться сделать что-то другое здесь, используя другой подход к этой ситуации и проблеме.


Подход