with open link debug checker cache borrar c++ multithreading performance x86

c++ - open - whatsapp cache link



¿Por qué el uso de la misma línea de caché de varios subprocesos no provoca una ralentización grave? (2)

La versión atómica debe garantizar que algún otro subproceso podrá leer el resultado de manera secuencial y coherente. Así que hay vallas para cada escritura.

La versión volátil no hace ninguna relación visible para los otros núcleos, por lo que no intenta sincronizar la memoria para que sea visible en otros núcleos. Para un sistema de subprocesos múltiples que utiliza C ++ 11 o más reciente, volatile no es un mecanismo para la comunicación entre subprocesos.

Mira este fragmento de código:

#include <atomic> #include <thread> typedef volatile unsigned char Type; // typedef std::atomic_uchar Type; void fn(Type *p) { for (int i=0; i<500000000; i++) { (*p)++; } } int main() { const int N = 4; std::thread thr[N]; alignas(64) Type buffer[N*64]; for (int i=0; i<N; i++) { thr[i] = std::thread(&fn, &buffer[i*1]); } for (int i=0; i<N; i++) { thr[i].join(); } }

Este pequeño programa incrementa cuatro bytes adyacentes muchas veces desde cuatro subprocesos diferentes. Antes, utilicé la regla: no use la misma línea de caché de diferentes subprocesos, ya que compartir la línea de caché es malo. Así que esperaba que una versión de cuatro hilos ( N=4 ) fuera mucho más lenta que una versión de un hilo ( N=1 ).

Sin embargo, estas son mis medidas (en una CPU Haswell):

  • N = 1: 1 seg
  • N = 4: 1.2 seg

Entonces N=4 no es mucho más lento. Si uso diferentes líneas de caché (reemplazar *1 con *64 ), entonces N=4 vuelve un poco más rápido: 1.1 seg.

Las mismas medidas para el acceso atómico (intercambiar los comentarios en typedef ), la misma línea de caché:

  • N = 1: 3,1 segundos
  • N = 4: 48 seg

Así que el caso N=4 es mucho más lento (como esperaba). Si se utilizan diferentes líneas de caché, entonces N=4 tiene un rendimiento similar a N=1 : 3.3 seg.

No entiendo la razón detrás de estos resultados. ¿Por qué no obtengo una desaceleración seria en el caso no atómico, N=4 ? Cuatro núcleos tienen la misma memoria en sus cachés, por lo que deben sincronizarlos de alguna manera, ¿no es así? ¿Cómo pueden correr casi perfectamente paralelos? ¿Por qué solo el caso atómico sufre una seria desaceleración?

Creo que necesito entender cómo se actualiza la memoria en este caso. Al principio, ningún núcleo tiene buffer en sus cachés. Después de uno for iteración (en fn ), los 4 núcleos tienen buffer en sus líneas de caché, pero cada núcleo escribe un byte diferente. ¿Cómo se sincronizan estas líneas de caché (en el caso no atómico)? ¿Cómo sabe el caché, qué byte está sucio? ¿O hay algún otro mecanismo para manejar este caso? ¿Por qué este mecanismo es mucho más barato (en realidad, es casi gratis) que el atómico?

Lo que está viendo es básicamente el efecto del reenvío de almacenamiento a carga que permite que cada núcleo funcione de forma casi independiente, a pesar de compartir una línea de caché. Como veremos a continuación, es realmente un caso extraño en el que más contención es mala, hasta cierto punto, ¡y de repente, una mayor contención hace que las cosas realmente se aceleren!

Ahora, con la visión convencional de la contención, su código parece algo que será una alta contención y, por lo tanto, mucho más lento que lo ideal. Sin embargo, lo que sucede es que tan pronto como cada núcleo obtiene una única escritura pendiente en su búfer de escritura, todas las lecturas posteriores se pueden satisfacer desde el búfer de escritura (almacenamiento de reenvío), y las escrituras posteriores solo ingresan en el búfer también. Esto convierte la mayor parte del trabajo en una operación totalmente local. La línea de caché todavía rebota entre los núcleos, pero está desacoplada de la ruta de ejecución del núcleo y solo es necesaria para comprometer las tiendas ahora y luego 1 .

La versión std::atomic no puede usar esta magia en absoluto, ya que tiene que usar operaciones de lock para mantener la atomicidad y anular el búfer de la tienda, por lo que ve el costo total de la contención y el costo de las operaciones atómicas de larga latencia 2 .

Tratemos de recolectar alguna evidencia de que esto es lo que está ocurriendo. Toda la discusión a continuación trata sobre la versión no atomic del punto de referencia que usa volatile para forzar las lecturas y escrituras desde el buffer .

Primero revisemos el ensamblaje, para asegurarnos de que es lo que esperamos:

0000000000400c00 <fn(unsigned char volatile*)>: 400c00: ba 00 65 cd 1d mov edx,0x1dcd6500 400c05: 0f 1f 00 nop DWORD PTR [rax] 400c08: 0f b6 07 movzx eax,BYTE PTR [rdi] 400c0b: 83 c0 01 add eax,0x1 400c0e: 83 ea 01 sub edx,0x1 400c11: 88 07 mov BYTE PTR [rdi],al 400c13: 75 f3 jne 400c08 <fn(unsigned char volatile*)+0x8> 400c15: f3 c3 repz ret

Es sencillo: un bucle de cinco instrucciones con una carga de bytes, un incremento del byte cargado, un almacenamiento de bytes y un incremento de bucle y un salto condicional. Gcc ha hecho un mal salto al dividir el sub y jne , inhibiendo la macrofusión, pero en general está bien y la latencia de reenvío de la tienda limitará el ciclo en cualquier caso.

A continuación, echemos un vistazo a la cantidad de L1D faltantes. Cada vez que un núcleo debe escribir en la línea que ha sido robada, sufrirá una falla de L1D, que podemos medir con perf . Primero, el caso de un solo hilo ( N=1 ):

$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment Performance counter stats for ''./cache-line-increment'': 1070.188749 task-clock (msec) # 0.998 CPUs utilized 2,775,874,257 cycles # 2.594 GHz 2,504,256,018 instructions # 0.90 insn per cycle 501,139,187 L1-dcache-loads # 468.272 M/sec 69,351 L1-dcache-load-misses # 0.01% of all L1-dcache hits 1.072119673 seconds time elapsed

Se trata de lo que esperamos: prácticamente cero errores de L1D (0.01% del total, probablemente principalmente de interrupciones y otros códigos fuera del bucle), solo más de 500,000,000 de hits (el número de veces que hacemos un bucle). Tenga en cuenta también que podemos calcular fácilmente los ciclos por bucle: aproximadamente 5.5, que refleja principalmente el costo del reenvío de almacenamiento a carga, más un ciclo para el incremento, que es una cadena de dependencia transportada ya que la misma ubicación se actualiza repetidamente (y volatile significa que no puede ser incorporado a un registro).

Echemos un vistazo al caso N=4 :

$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment Performance counter stats for ''./cache-line-increment'': 5920.758885 task-clock (msec) # 3.773 CPUs utilized 15,356,014,570 cycles # 2.594 GHz 10,012,249,418 instructions # 0.65 insn per cycle 2,003,487,964 L1-dcache-loads # 338.384 M/sec 61,450,818 L1-dcache-load-misses # 3.07% of all L1-dcache hits 1.569040529 seconds time elapsed

Como era de esperar, las cargas L1 saltan de 500 millones a 2 mil millones, ya que hay 4 hilos cada uno haciendo los 500 millones de cargas. La cantidad de L1D faltantes también aumentó en aproximadamente un factor de 1,000, a unos 60 millones. Aún así, ese número no es mucho comparado con los 2 billones de cargas (y 2 billones de tiendas, no se muestra, pero sabemos que están ahí). Eso es ~ 33 cargas y ~ 33 tiendas por cada falta. También significa 250 ciclos entre cada falta.

Eso realmente no encaja con el modelo de la línea de caché que rebota erráticamente entre los núcleos, donde tan pronto como un núcleo obtiene la línea, otro núcleo lo exige. Sabemos que las líneas rebotan entre los núcleos que comparten un L2 en quizás 20 a 50 ciclos, por lo que la proporción de un fallo cada 250 ciclos parece demasiado baja.

Dos hipótesis

Un par de ideas vienen a la mente para el comportamiento descrito anteriormente:

  • Quizás la variante de protocolo MESI utilizada en este chip sea "inteligente" y reconozca que una línea está activa entre varios núcleos, pero solo se está realizando una pequeña cantidad de trabajo cada vez que un núcleo obtiene el bloqueo y la línea pasa más tiempo moviéndose entre L1 y L2 que en realidad satisface las cargas y almacena algunos núcleos. A la luz de esto, algunos componentes inteligentes en el protocolo de coherencia deciden imponer algún tipo de "tiempo de propiedad" mínimo para cada línea: después de que un núcleo obtiene la línea, la mantendrá durante N ciclos, incluso si es requerido por otro núcleo (el Otros núcleos solo tienen que esperar).

    Esto ayudaría a equilibrar la sobrecarga de la línea de caché de ping-pong con el trabajo real, a costa de la "imparcialidad" y la capacidad de respuesta de los otros núcleos, algo así como la compensación entre bloqueos injustos y justos, y contrarrestar el efecto [descrito aquí], donde más rápido y más justo es el protocolo de coherencia, peor pueden llevar a cabo algunos bucles (generalmente sintéticos).

    Ahora nunca he oído hablar de algo así (y el enlace inmediatamente anterior muestra que al menos en la era de Sandy-Bridge las cosas se estaban moviendo en la dirección opuesta ), ¡pero ciertamente es posible !

  • El efecto de almacenamiento almacenado descrito realmente está ocurriendo, por lo que la mayoría de las operaciones pueden completarse casi localmente.

Algunas pruebas

Intentemos distinguir dos casos con algunas modificaciones.

Lectura y escritura de bytes distintos

El enfoque obvio es cambiar la función de trabajo fn() para que los subprocesos aún compitan en la misma línea de caché, pero donde el reenvío de la tienda no puede activarse.

¿Qué tal si leemos desde la ubicación x y luego escribimos en la ubicación x + 1 ? Le daremos a cada hilo dos ubicaciones consecutivas (es decir, thr[i] = std::thread(&fn, &buffer[i*2]) ) para que cada hilo esté operando en dos bytes privados. El fn() modificado se ve como:

for (int i=0; i<500000000; i++) unsigned char temp = p[0]; p[1] = temp + 1; }

El bucle del núcleo es prácticamente idéntico al anterior:

400d78: 0f b6 07 movzx eax,BYTE PTR [rdi] 400d7b: 83 c0 01 add eax,0x1 400d7e: 83 ea 01 sub edx,0x1 400d81: 88 47 01 mov BYTE PTR [rdi+0x1],al 400d84: 75 f2 jne 400d78

Lo único que ha cambiado es que escribimos en [rdi+0x1] lugar de [rdi] .

Ahora, como mencioné anteriormente, el bucle original (en la misma ubicación) se está ejecutando bastante lentamente a aproximadamente 5,5 ciclos por iteración, incluso en el caso de un solo subproceso en el mejor de los casos, debido a la load->add->store->load... transportada por el load->add->store->load... dependencia. ¡Este nuevo código rompe esa cadena! La carga ya no depende de la tienda, por lo que podemos ejecutar todo prácticamente en paralelo y espero que este bucle se ejecute a aproximadamente 1,25 ciclos por iteración (5 instrucciones / ancho de CPU de 4).

Aquí está el caso de un solo hilo:

$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment Performance counter stats for ''./cache-line-increment'': 318.722631 task-clock (msec) # 0.989 CPUs utilized 826,349,333 cycles # 2.593 GHz 2,503,706,989 instructions # 3.03 insn per cycle 500,973,018 L1-dcache-loads # 1571.815 M/sec 63,507 L1-dcache-load-misses # 0.01% of all L1-dcache hits 0.322146774 seconds time elapsed

Entonces, aproximadamente 1.65 ciclos por iteración 3 , aproximadamente tres veces más rápido en comparación con el incremento de la misma ubicación.

¿Qué tal 4 hilos?

$ perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses ./cache-line-increment Performance counter stats for ''./cache-line-increment'': 22299.699256 task-clock (msec) # 3.469 CPUs utilized 57,834,005,721 cycles # 2.593 GHz 10,038,366,836 instructions # 0.17 insn per cycle 2,011,160,602 L1-dcache-loads # 90.188 M/sec 237,664,926 L1-dcache-load-misses # 11.82% of all L1-dcache hits 6.428730614 seconds time elapsed

Así que es aproximadamente 4 veces más lento que el mismo caso de ubicación. Ahora, en lugar de ser solo un poco más lento que el caso de un solo hilo, es aproximadamente 20 veces más lento. ¡Esta es la contención que has estado buscando! Ahora también que la cantidad de fallas L1D también se ha incrementado en un factor de 4, lo que explica muy bien la degradación del rendimiento y es consistente con la idea de que cuando el reenvío de almacenamiento a carga no puede ocultar la contención, las fallas aumentarán mucho.

Aumentar la distancia entre tiendas

Otro enfoque sería aumentar la distancia en tiempo / instrucciones entre la tienda y la carga posterior. Podemos hacer esto incrementando las ubicaciones consecutivas de SPAN en el método fn() , en lugar de siempre la misma ubicación. Por ejemplo, si SPAN es 4, incrementa consecutivamente 4 ubicaciones como:

for (long i=0; i<500000000 / 4; i++) { p[0]++; p[1]++; p[2]++; p[3]++; }

Tenga en cuenta que todavía estamos incrementando 500 millones de ubicaciones en total, simplemente distribuyendo los incrementos entre 4 bytes. Intuitivamente, usted esperaría que el rendimiento general aumentara, ya que ahora tiene una dependencia de SPAN paralelo con longitud 1/SPAN , por lo que en el caso anterior puede esperar que el rendimiento mejore en un factor de 4, ya que las 4 cadenas paralelas pueden proceder aproximadamente 4 veces más. rendimiento total.

Esto es lo que realmente obtenemos por tiempo (medido en ciclos) para el 1 hilo y 3 hilo 4 , para los valores SPAN de 1 a 20:

Inicialmente, se ve un aumento sustancial en el rendimiento tanto en casos de subprocesos simples como en varios; el aumento de un SPAN de uno a dos y tres es cercano al teórico esperado en el caso del paralelismo perfecto para ambos casos.

El caso de un solo hilo alcanza una asíntota de aproximadamente 4.25 veces más rápido que la escritura de una sola ubicación: en este punto, la latencia de reenvío de la tienda no es el cuello de botella y otros cuellos de botella se han hecho cargo (IPC máx. Y contención de puerto de tienda, en su mayoría).

Sin embargo, el estuche multi-hilo es muy diferente. Una vez que alcanza un SPAN de aproximadamente 7, el rendimiento empeora rápidamente, nivelando aproximadamente 2,5 veces peor que el caso SPAN=1 y casi 10 veces peor en comparación con el mejor rendimiento en SPAN=5 . Lo que sucede es que el reenvío de almacenamiento a carga deja de ocurrir porque el almacén y la carga subsiguiente están lo suficientemente separados en tiempo / ciclos que el almacén se ha retirado a L1, por lo que la carga realmente tiene que obtener la línea y participar en MESI.

También se grafican los fallos L1D, que como se mencionó anteriormente es indicativo de "transferencias de línea de caché" entre los núcleos. El caso de un solo hilo tiene prácticamente cero, y no están correlacionados con el rendimiento. Sin embargo, el rendimiento del caso de subprocesos múltiples prácticamente rastrea exactamente la falta de memoria caché. Con los valores de SPAN en el rango de 2 a 6, donde el reenvío de tiendas sigue funcionando, hay proporcionalmente menos errores. Evidentemente, el núcleo es capaz de "almacenar" más almacenes entre cada transferencia de línea de caché ya que el bucle del núcleo es más rápido.

Otra forma de verlo es que, en el caso en disputa, las fallas de L1D son básicamente constantes por unidad de tiempo (lo que tiene sentido, ya que están básicamente ligadas a la latencia L1-> L2-> L1, más alguna sobrecarga del protocolo de coherencia), por lo que Cuanto más trabajo pueda hacer entre las transferencias de línea de caché, mejor.

Aquí está el código para el caso multi-span:

void fn(Type *p) { for (long i=0; i<500000000 / SPAN; i++) { for (int j = 0; j < SPAN; j++) { p[j]++; } } }

La secuencia de comandos bash para ejecutar perf para todos los valores SPAN de 1 a 20:

PERF_ARGS=${1:--x, -r10} for span in {1..20}; do g++ -std=c++11 -g -O2 -march=native -DSPAN=$span cache-line-increment.cpp -lpthread -o cache-line-increment perf stat ${PERF_ARGS} -e cycles,L1-dcache-loads,L1-dcache-load-misses,machine_clears.count,machine_clears.memory_ordering ./cache-line-increment done

Finalmente, "transponga" los resultados a un CSV adecuado:

FILE=result1.csv; for metric in cycles L1-dcache-loads L1-dcache-load-misses; do { echo $metric; grep $metric $FILE | cut -f1 -d,; } > ${metric}.tmp; done && paste -d, *.tmp

Una prueba final

Hay una prueba final que puede hacer para demostrar que cada núcleo realiza efectivamente la mayor parte de su trabajo en privado: use la versión del punto de referencia donde los subprocesos trabajan en la misma ubicación (que no cambia las características de rendimiento) examine la suma de los valores de contador finales (necesitaría contadores int lugar de char ). Si todo fuera atómico, tendría una suma de 2 mil millones, y en el caso no atómico de cuán cercano está el valor a ese valor es una medida aproximada de la frecuencia con la que los núcleos pasaban alrededor de las líneas. Si los núcleos funcionan casi totalmente en privado, el valor sería más cercano a 500 millones que a 2 mil millones, y supongo que eso es lo que encontrará.

Con algunos incrementos más inteligentes, incluso puede hacer que cada subproceso haga un seguimiento de la frecuencia con la que el valor que incrementaron provino de su último incremento en lugar de otro incremento de subprocesos (por ejemplo, utilizando algunos bits del valor para esconder un identificador de subproceso). Con una prueba aún más inteligente, prácticamente se podría reconstruir la forma en que la línea de caché se movía entre los núcleos (¿hay un patrón, por ejemplo, el núcleo A prefiere transferir al núcleo B?) Y qué núcleos son los que más contribuyen al valor final, etc.

Todo eso queda como un ejercicio :).

1 Además de eso, si Intel tiene un búfer de tienda coalescente donde las tiendas posteriores que se superponen completamente matan a las tiendas anteriores, solo tendría que confirmar un valor en L1 (la tienda más reciente) cada vez que obtenga la línea.

2 Realmente no puede separar los dos efectos aquí, pero lo haremos más adelante al derrotar el reenvío de almacenamiento a carga.

3 Un poco más de lo que esperaba, tal vez una mala programación que lleve a la presión del puerto. Si gcc solo fusionara todos los sub y jne , se ejecutará a 1.1 ciclos por iteración (aún peor que el 1.0 que yo esperaría). Hará que use -march=haswell lugar de -march=native pero no volveré y cambiaré todos los números.

4 Los resultados se mantienen con 4 hilos también: pero solo tengo 4 núcleos y ejecuto cosas como Firefox en segundo plano, por lo que usar 1 núcleo menos hace que las mediciones sean mucho menos ruidosas. Medir el tiempo en ciclos también ayuda mucho.