performance assembly optimization x86 x86-64

performance - Rendimiento inesperadamente pobre y extrañamente bimodal para loop de tienda en Intel Skylake



assembly optimization (2)

Estoy viendo un rendimiento inesperadamente pobre para un bucle de tienda simple que tiene dos tiendas: una con un paso adelante de 16 bytes y otra que siempre está en la misma ubicación 1 , así:

volatile uint32_t value; void weirdo_cpp(size_t iters, uint32_t* output) { uint32_t x = value; uint32_t *rdx = output; volatile uint32_t *rsi = output; do { *rdx = x; *rsi = x; rdx += 4; // 16 byte stride } while (--iters > 0); }

En el ensamblaje, este bucle probablemente sea 3 :

weirdo_cpp: ... align 16 .top: mov [rdx], eax ; stride 16 mov [rsi], eax ; never changes add rdx, 16 dec rdi jne .top ret

Cuando la región de memoria a la que se accede está en L2, esperaría que esto se ejecute a menos de 3 ciclos por iteración. La segunda tienda sigue llegando a la misma ubicación y debería agregar un ciclo. La primera tienda implica traer una línea desde L2 y, por lo tanto, también desalojar una línea cada 4 iteraciones . No estoy seguro de cómo evalúa el costo de L2, pero incluso si estima conservadoramente que L1 solo puede hacer uno de los siguientes en cada ciclo: (a) comprometer una tienda o (b) recibir una línea de L2 o (c) desalojar una línea a L2, obtendría algo como 1 + 0.25 + 0.25 = 1.5 ciclos para la secuencia de almacenamiento stride-16.

De hecho, comentas en una tienda que obtienes ~ 1.25 ciclos por iteración solo para la primera tienda, y ~ 1.01 ciclos por iteración para la segunda tienda, por lo que 2.5 ciclos por iteración parece una estimación conservadora.

Sin embargo, el rendimiento real es muy extraño. Aquí hay una ejecución típica del arnés de prueba:

Estimated CPU speed: 2.60 GHz output size : 64 KiB output alignment: 32 3.90 cycles/iter, 1.50 ns/iter, cpu before: 0, cpu after: 0 3.90 cycles/iter, 1.50 ns/iter, cpu before: 0, cpu after: 0 3.90 cycles/iter, 1.50 ns/iter, cpu before: 0, cpu after: 0 3.89 cycles/iter, 1.49 ns/iter, cpu before: 0, cpu after: 0 3.90 cycles/iter, 1.50 ns/iter, cpu before: 0, cpu after: 0 4.73 cycles/iter, 1.81 ns/iter, cpu before: 0, cpu after: 0 7.33 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.33 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.34 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.26 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.28 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.31 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.29 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.28 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.29 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.27 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.30 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.30 cycles/iter, 2.81 ns/iter, cpu before: 0, cpu after: 0 7.28 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0 7.28 cycles/iter, 2.80 ns/iter, cpu before: 0, cpu after: 0

Dos cosas son raras aquí.

Primero están los tiempos bimodales: hay un modo rápido y un modo lento . Comenzamos en modo lento, tomando aproximadamente 7.3 ciclos por iteración, y en algún momento hacemos la transición a aproximadamente 3.9 ciclos por iteración. Este comportamiento es consistente y reproducible y los dos tiempos siempre son bastante consistentes agrupados alrededor de los dos valores. La transición se muestra en ambas direcciones, del modo lento al modo rápido y viceversa (y, a veces, varias transiciones en una sola ejecución).

La otra cosa extraña es el muy mal desempeño. Incluso en modo rápido , a aproximadamente 3.9 ciclos, el rendimiento es mucho peor que el peor reparto de 1.0 + 1.3 = 2.3 ciclos que esperaría al sumar cada uno de los casos con una sola tienda (y suponiendo que absolutamente cero trabajado se puede superponer cuando ambas tiendas están en el bucle). En modo lento , el rendimiento es terrible en comparación con lo que cabría esperar según los primeros principios: se necesitan 7.3 ciclos para hacer 2 tiendas, y si lo pones en términos de ancho de banda de la tienda L2, eso es aproximadamente 29 ciclos por tienda L2 (ya que solo almacene una línea de caché completa cada 4 iteraciones).

Se recorded que Skylake tiene un rendimiento de 64B / ciclo entre L1 y L2, que es mucho más alto que el rendimiento observado aquí (aproximadamente 2 bytes / ciclo en modo lento ).

¿Qué explica el bajo rendimiento y el rendimiento bimodal y puedo evitarlo?

También tengo curiosidad si esto se reproduce en otras arquitecturas e incluso en otras cajas de Skylake. Siéntase libre de incluir resultados locales en los comentarios.

Puede encontrar el código de prueba y el arnés en github . Hay un Makefile para Linux o plataformas similares a Unix, pero también debería ser relativamente fácil de construir en Windows. Si desea ejecutar la variante asm , necesitará nasm o yasm para el ensamblado 4 ; si no lo tiene, puede probar la versión C ++.

Posibilidades eliminadas

Aquí hay algunas posibilidades que consideré y eliminé en gran medida. Muchas de las posibilidades se eliminan por el simple hecho de que ve la transición de rendimiento aleatoriamente en el medio del ciclo de evaluación comparativa , cuando muchas cosas simplemente no han cambiado (por ejemplo, si estaba relacionado con la alineación de la matriz de salida, no podría cambiar en el medio de una ejecución ya que se usa el mismo búfer todo el tiempo). Me referiré a esto como la eliminación predeterminada a continuación (incluso para cosas que son eliminación predeterminada, a menudo hay otro argumento que hacer).

  • Factores de alineación: la matriz de salida está alineada a 16 bytes, y he intentado una alineación de hasta 2 MB sin cambios. También eliminado por la eliminación por defecto .
  • Contención con otros procesos en la máquina: el efecto se observa de manera más o menos idéntica en una máquina inactiva e incluso en una máquina muy cargada (p. Ej., Utilizando stress -vm 4 ). El punto de referencia en sí mismo debe ser completamente local-core de todos modos, ya que cabe en L2, y perf confirma que hay muy pocos errores de L2 por iteración (aproximadamente 1 falla cada 300-400 iteraciones, probablemente relacionadas con el código printf ).
  • TurboBoost: TurboBoost está completamente deshabilitado, confirmado por tres lecturas de MHz diferentes.
  • intel_pstate ahorro de energía: el regulador de rendimiento es intel_pstate en modo de performance . No se observan variaciones de frecuencia durante la prueba (la CPU permanece esencialmente bloqueada a 2.59 GHz).
  • Efectos TLB: el efecto está presente incluso cuando el búfer de salida se encuentra en una página enorme de 2 MB. En cualquier caso, las 64 entradas de 4k TLB cubren más que el búfer de salida de 128K. perf no informa ningún comportamiento TLB particularmente extraño.
  • Alias ​​de 4k: las versiones más antiguas y complejas de este punto de referencia mostraron algunos alias de 4k, pero esto se ha eliminado ya que no hay cargas en el punto de referencia (son cargas que podrían alias incorrectamente a las tiendas anteriores). También eliminado por la eliminación por defecto .
  • Conflictos de asociatividad L2: eliminados por la eliminación predeterminada y por el hecho de que esto no desaparece incluso con páginas de 2 MB, donde podemos estar seguros de que el búfer de salida se presenta linealmente en la memoria física.
  • Efectos de hyperthreading: HT está deshabilitado.
  • Captación previa: solo dos de las captadoras previas podrían estar involucradas aquí (la "DCU", también conocidas como captadoras L1 <-> L2), ya que todos los datos viven en L1 o L2, pero el rendimiento es el mismo con todas las captadoras habilitadas o todas deshabilitadas.
  • Interrupciones: no hay correlación entre el conteo de interrupciones y el modo lento. Hay un número limitado de interrupciones totales, en su mayoría ticks de reloj.

toplev.py

toplev.py que implementa el método de análisis de arriba hacia abajo de Intel, y no sorprende que identifique el punto de referencia como vinculado a la tienda:

BE Backend_Bound: 82.11 % Slots [ 4.83%] BE/Mem Backend_Bound.Memory_Bound: 59.64 % Slots [ 4.83%] BE/Core Backend_Bound.Core_Bound: 22.47 % Slots [ 4.83%] BE/Mem Backend_Bound.Memory_Bound.L1_Bound: 0.03 % Stalls [ 4.92%] This metric estimates how often the CPU was stalled without loads missing the L1 data cache... Sampling events: mem_load_retired.l1_hit:pp mem_load_retired.fb_hit:pp BE/Mem Backend_Bound.Memory_Bound.Store_Bound: 74.91 % Stalls [ 4.96%] <== This metric estimates how often CPU was stalled due to store memory accesses... Sampling events: mem_inst_retired.all_stores:pp BE/Core Backend_Bound.Core_Bound.Ports_Utilization: 28.20 % Clocks [ 4.93%] BE/Core Backend_Bound.Core_Bound.Ports_Utilization.1_Port_Utilized: 26.28 % CoreClocks [ 4.83%] This metric represents Core cycles fraction where the CPU executed total of 1 uop per cycle on all execution ports... MUX: 4.65 % PerfMon Event Multiplexing accuracy indicator

Esto realmente no arroja mucha luz: ya sabíamos que debían ser las tiendas estropeando las cosas, pero ¿por qué? La descripción de Intel de la condición no dice mucho.

Here''s un resumen razonable de algunos de los problemas involucrados en la interacción L1-L2.

Actualización de febrero de 2019: ya no puedo reproducir la parte "bimodal" del rendimiento: para mí, en el mismo cuadro i7-6700HQ, el rendimiento ahora es siempre muy lento en los mismos casos, se aplica el rendimiento bimodal lento y muy lento, es decir , con resultados de alrededor de 16-20 ciclos por línea, así:

Este cambio parece haberse introducido en la actualización del microcódigo Skylake de agosto de 2018, revisión 0xC6. El microcódigo anterior, 0xC2 muestra el comportamiento original descrito en la pregunta.

1 Este es un MCVE muy simplificado de mi bucle original, que tenía al menos 3 veces el tamaño y que hizo mucho trabajo adicional, pero exhibió exactamente el mismo rendimiento que esta versión simple, con un cuello de botella en el mismo misterioso problema.

3 En particular, se ve exactamente así si escribe el ensamblaje a mano, o si lo compila con gcc -O1 (versión 5.4.1), y probablemente los compiladores más razonables (se utiliza volatile para evitar hundir el segundo mayormente muerto almacenar fuera del bucle).

4 Sin duda, podría convertir esto a sintaxis MASM con algunas ediciones menores, ya que el ensamblaje es muy trivial. Solicitudes de extracción aceptadas.

Lo que he encontrado hasta ahora. Desafortunadamente, en realidad no ofrece una explicación para el bajo rendimiento, y en absoluto para la distribución bimodal, pero es más un conjunto de reglas para cuándo puede ver el rendimiento y las notas para mitigarlo:

  • El rendimiento de la tienda en L2 parece ser como máximo una línea de caché de 64 bytes por tres ciclos 0 , lo que pone un límite superior de ~ 21 bytes por ciclo en el rendimiento de la tienda. Dicho de otra manera, la serie de tiendas que fallan en L1 y golpean en L2 tomarán al menos tres ciclos por línea de caché tocada.
  • Por encima de esa línea base hay una penalización significativa cuando las tiendas que golpean en L2 se entrelazan con las tiendas en una línea de caché diferente (independientemente de si esas tiendas golpean en L1 o L2).
  • Aparentemente, la penalización es algo mayor para las tiendas cercanas (pero que aún no están en la misma línea de caché).
  • El rendimiento bimodal está al menos superficialmente relacionado con el efecto anterior, ya que en el caso de no intercalar no parece ocurrir, aunque no tengo una explicación más detallada.
  • Si se asegura de que la línea de caché ya está en L1 antes de la tienda, mediante captación previa o una carga ficticia, el rendimiento lento desaparece y el rendimiento ya no es bimodal.

Detalles y fotos

Paso de 64 bytes

La pregunta original usó arbitrariamente un paso de 16, pero comencemos probablemente con el caso más simple: un paso de 64, es decir, una línea de caché completa. Resulta que los diversos efectos son visibles con cualquier paso, pero 64 garantiza un error de caché L2 en cada paso y elimina algunas variables.

Eliminemos también la segunda tienda por ahora, por lo que solo estamos probando una tienda de 64 bytes con más de 64 KB de memoria:

top: mov BYTE PTR [rdx],al add rdx,0x40 sub rdi,0x1 jne top

Al ejecutar esto en el mismo arnés que el anterior, obtengo aproximadamente 3.05 ciclos / tienda 2 , aunque hay bastante variación en comparación con lo que estoy acostumbrado a ver (- incluso puedes encontrar un 3.0 allí).

Por lo tanto, ya sabemos que probablemente no lo vamos a hacer mejor que esto para tiendas sostenidas únicamente para L2 1 . Si bien Skylake aparentemente tiene un rendimiento de 64 bytes entre L1 y L2, en el caso de una secuencia de tiendas, ese ancho de banda debe compartirse para ambos desalojos de L1 y para cargar la nueva línea en L1. 3 ciclos parecen razonables si se tarda, digamos, 1 ciclo cada uno para (a) desalojar la línea sucia de la víctima de L1 a L2 (b) actualizar L1 con la nueva línea de L2 y (c) confirmar la tienda en L1.

¿Qué sucede cuando agrega una segunda escritura en la misma línea de caché (al siguiente byte, aunque resulta que no importa) en el bucle? Me gusta esto:

top: mov BYTE PTR [rdx],al mov BYTE PTR [rdx+0x1],al add rdx,0x40 sub rdi,0x1 jne top

Aquí hay un histograma de la sincronización para 1000 ejecuciones del arnés de prueba para el bucle anterior:

count cycles/itr 1 3.0 51 3.1 5 3.2 5 3.3 12 3.4 733 3.5 139 3.6 22 3.7 2 3.8 11 4.0 16 4.1 1 4.3 2 4.4

Entonces, la mayoría de las veces se agrupan alrededor de 3.5 ciclos. Eso significa que esta tienda adicional solo agregó 0.5 ciclos al tiempo. Podría ser algo así como que el búfer de la tienda puede drenar dos tiendas al L1 si están en la misma línea, pero esto solo ocurre aproximadamente la mitad del tiempo.

Considere que el búfer de la tienda contiene una serie de tiendas como 1, 1, 2, 2, 3, 3 donde 1 indica la línea de caché: la mitad de las posiciones tienen dos valores consecutivos de la misma línea de caché y la otra mitad no. Como el búfer de la tienda está esperando para drenar las tiendas, y el L1 está ocupadamente desalojando y aceptando líneas de L2, el L1 estará disponible para una tienda en un punto "arbitrario", y si está en la posición 1, 1 tal vez almacena el drenaje en un ciclo, pero si está en 1, 2 , toma dos ciclos.

Tenga en cuenta que hay otro pico de aproximadamente el 6% de los resultados alrededor de 3.1 en lugar de 3.5. Ese podría ser un estado estable donde siempre tenemos el resultado afortunado. Hay otro pico de alrededor del 3% en ~ 4.0-4.1: el arreglo "siempre desafortunado".

Probemos esta teoría observando varias compensaciones entre la primera y la segunda tienda:

top: mov BYTE PTR [rdx + FIRST],al mov BYTE PTR [rdx + SECOND],al add rdx,0x40 sub rdi,0x1 jne top

Intentamos todos los valores de FIRST y SECOND de 0 a 256 en pasos de 8. Los resultados, con valores FIRST variables en el eje vertical y SECOND en el horizontal:

Vemos un patrón específico: los valores blancos son "rápidos" (alrededor de los valores 3.0-4.1 discutidos anteriormente para el desplazamiento de 1). Los valores amarillos son más altos, hasta 8 ciclos, y los rojos hasta 10. Los valores atípicos púrpuras son los más altos y, por lo general, son casos en los que se activa el "modo lento" descrito en el OP (generalmente registrando en 18.0 ciclos / iter). Notamos lo siguiente:

  • A partir del patrón de las celdas blancas, vemos que obtenemos el resultado del ciclo rápido ~ 3.5 mientras la segunda tienda esté en la misma línea de caché o la siguiente relativa a la primera tienda. Esto es consistente con la idea anterior de que las tiendas en la misma línea de caché se manejan de manera más eficiente. La razón por la que funciona la segunda tienda en la siguiente línea de caché es que el patrón termina siendo el mismo, excepto por el primer primer acceso: 0, 0, 1, 1, 2, 2, ... vs 0, 1, 1, 2, 2, ... - donde en el segundo caso es la segunda tienda la primera que toca cada línea de caché. Sin embargo, al búfer de la tienda no le importa. Tan pronto como entras en diferentes líneas de caché, obtienes un patrón como 0, 2, 1, 3, 2, ... y aparentemente esto apesta?

  • Los "valores atípicos" púrpuras nunca aparecen en las áreas blancas, por lo que aparentemente están restringidos al escenario que ya es lento (y el lento más aquí lo hace aproximadamente 2.5 veces más lento: de ~ 8 a 18 ciclos).

Podemos alejarnos un poco y ver compensaciones aún mayores:

El mismo patrón básico, aunque vemos que el rendimiento mejora (área verde) a medida que la segunda tienda se aleja (adelante o atrás) de la primera, hasta que empeora nuevamente en un desplazamiento de aproximadamente ~ 1700 bytes. Incluso en el área mejorada solo llegamos en el mejor de los 5.8 ciclos / iteración aún mucho peor que el rendimiento de la misma línea de 3.5.

Si agrega algún tipo de instrucción de carga o captación previa que se ejecuta antes de 3 de las tiendas, desaparecen tanto el rendimiento general lento como los valores atípicos de "modo lento":

Puede trasladar esto al problema original de 16 pasos: cualquier tipo de captación previa o carga en el bucle central, prácticamente insensible a la distancia (incluso si de hecho está detrás ), soluciona el problema y obtiene 2.3 ciclos / iteración, cercano al mejor ideal posible de 2.0, e igual a la suma de las dos tiendas con bucles separados.

Por lo tanto, la regla básica es que las tiendas en L2 sin las cargas correspondientes son mucho más lentas que si las capta previamente el software, a menos que toda la secuencia de la tienda acceda a las líneas de caché en un solo patrón secuencial. Eso es contrario a la idea de que un patrón lineal como este nunca se beneficia de la captación previa de SW.

Realmente no tengo una explicación detallada, pero podría incluir estos factores:

  • Tener otras tiendas en los buffers de la tienda puede reducir la concurrencia de las solicitudes que van a L2. No está claro exactamente cuándo las tiendas que van a faltar en L1 asignan un búfer de la tienda, pero tal vez ocurre cerca de cuando la tienda se va a retirar y hay una cierta cantidad de "lookhead" en el búfer de la tienda para llevar las ubicaciones a L1, por lo que tener tiendas adicionales que no se perderán en L1 perjudica la concurrencia ya que la búsqueda anticipada no puede ver tantas solicitudes que fallarán.
  • Quizás haya conflictos para los recursos L1 y L2, como puertos de lectura y escritura, ancho de banda entre caché, que son peores con este patrón de tiendas. Por ejemplo, cuando las tiendas de diferentes líneas se intercalan, tal vez no puedan drenar tan rápido de la cola de la tienda (ver arriba donde parece que en algunos escenarios más de una tienda puede drenar por ciclo).

Estos comentarios del Dr. McCalpin en los foros de Intel también son bastante interesantes.

0 La mayoría de las veces solo se puede lograr con el transmisor L2 desactivado, ya que de lo contrario la contención adicional en el L2 reduce esto a aproximadamente 1 línea por 3.5 ciclos.

1 Compare esto con las tiendas, donde obtengo casi exactamente 1.5 ciclos por carga, para un ancho de banda implícito de ~ 43 bytes por ciclo. Esto tiene mucho sentido: el ancho de banda L1 <-> L2 es de 64 bytes, pero suponiendo que L1 acepta una línea de L2 o atiende solicitudes de carga del núcleo en cada ciclo (pero no ambos en paralelo), entonces tiene 3 ciclos para dos cargas a diferentes líneas de L2: 2 ciclos para aceptar las líneas de L2 y 1 ciclo para satisfacer dos instrucciones de carga.

2 Con la extracción previa. Como resultado, el prefetcher L2 compite por el acceso al caché L2 cuando detecta el acceso de transmisión: a pesar de que siempre encuentra las líneas candidatas y no va a L3, esto ralentiza el código y aumenta la variabilidad. Las conclusiones generalmente se mantienen con la captación previa activada, pero todo es un poco más lento (aquí hay una gran cantidad de resultados con la captación previa activada; ve aproximadamente 3.3 ciclos por carga, pero con mucha variabilidad).

3 Realmente ni siquiera necesita estar adelante: la captación previa de varias líneas detrás también funciona: supongo que las captaciones / cargas previas se ejecutan rápidamente por delante de las tiendas que tienen cuellos de botella para que puedan avanzar de todos modos. De esta manera, la captación previa es una especie de autocuración y parece funcionar con casi cualquier valor que le pongas.

Sandy Bridge tiene "pre-captadores de hardware de datos L1". Lo que esto significa es que inicialmente cuando realiza su almacenamiento, la CPU tiene que buscar datos de L2 a L1; pero después de que esto haya sucedido varias veces, el pretratador de hardware nota el patrón secuencial agradable y comienza a buscar previamente los datos de L2 a L1, de modo que los datos estén en L1 o "a medio camino de L1" antes de que su código haga su almacenar.