Importante lectura de antecedentes: Microarch pdf, y probablemente también Ulrich Drepper Lo Que Todo Programador Debe Saber Sobre La Memoria. Ver también los otros enlaces en el wiki de etiquetas x86, especialmente los manuales de optimización de Intel, y el análisis de David Kanter de la microarquitectura de Haswell, con diagramas.

Muy buena tarea; mucho mejor que las que he visto donde se les pidió a los estudiantes que optimizaran algunos código para gcc -O0, aprendiendo un montón de trucos que no importan en código real. En este caso, se le pide que aprenda sobre la canalización de CPU y lo use para guiar sus esfuerzos de desoptimización, no solo adivinando a ciegas. La parte más divertida de esto es justificar cada pesimismo con "incompetencia diabólica", no con malicia intencional.

Problemas con la redacción y el código de la asignación :

Las opciones específicas de uarch para este código son limitado. No utiliza ninguna matriz, y gran parte del costo son las llamadas a exp/log funciones de biblioteca. No hay una manera obvia de tener más o menos paralelismo a nivel de instrucción, y la cadena de dependencias en bucle es muy corta.

Me encantaría ver una respuesta que intentara obtener una desaceleración al reorganizar las expresiones para cambiar las dependencias, para reducir ILP solo de dependencias (peligros).No lo he intentado.

Intel Las CPU de la familia Sandybridge son diseños agresivos fuera de orden que gastan muchos transistores y energía para encontrar paralelismo y evitar peligros (dependencias) que molestarían a una tubería RISC clásica en orden. Por lo general, los únicos peligros tradicionales que lo ralentizan son las dependencias "verdaderas" sin procesar que hacen que el rendimiento esté limitado por la latencia.

WAR and WAW hazards para los registros prácticamente no son un problema, gracias al cambio de nombre del registro. (excepto para popcnt/lzcnt/tzcnt, que tienen una dependencia falsa su destino en CPU Intel, a pesar de que es de solo escritura. es decir, WAW siendo manejado como un riesgo BRUTO + una escritura). Para ordenar la memoria, las CPU modernas usan colas de almacenamiento para retrasar la confirmación en caché hasta el retiro, también evitando WAR y WAW hazards.

El nombre de la marca" i7 "se introdujo con Nehalem (sucesor de Core2), y algunos manuales de Intel incluso dicen "Core i7" cuando parecen significar Nehalem, pero mantuvieron "i7" branding para Sandybridge y microarquitecturas posteriores. SnB es cuando la familia P6 evolucionó en una nueva especie, la familia SnB. En muchos sentidos, Nehalem tiene más en común con Pentium III que con Sandybridge (por ejemplo, los puestos de lectura de registro y los puestos de lectura de robo no ocurren en SnB, porque cambió a usar un archivo de registro físico. También una caché uop y un formato uop interno diferente). El término "arquitectura i7" no es útil, porque no tiene sentido agrupar a la familia SnB con Nehalem pero no Core2. (Nehalem introdujo la arquitectura de caché L3 inclusiva compartida para conectar varios núcleos juntos, sin embargo. Y también GPU integradas. Así que a nivel de chip, el nombre tiene más sentido.)

Resumen de las buenas ideas que la incompetencia diabólica puede justificar{[150]]}

Incluso los diabólicamente incompetentes es poco probable que agreguen trabajo obviamente inútil o un bucle infinito, y hacer un lío con las clases de C++/Boost está más allá de alcance de la asignación.

• Multi-hilo con un único compartido std::atomic<uint64_t> contador de bucle, por lo que el número total correcto de iteraciones suceder. Atomic uint64_t es especialmente malo con -m32 -march=i586. Para obtener puntos de bonificación, arregle que esté desalineado y cruce un límite de página con una división desigual (no 4:4).
• False sharing para alguna otra variable no atómica -> orden de memoria mis-speculation pipeline clears, así como caché adicional perder.
• En lugar de usar - en variables FP, XOR el byte alto con 0x80 para voltear el bit de signo, causando que el reenvío de tiendas se detenga.
• Mide el tiempo de cada iteración de forma independiente, con algo aún más pesado que RDTSC. por ejemplo,CPUID / RDTSC o una función de tiempo que hace una llamada al sistema. Las instrucciones de serialización son inherentemente hostiles a la canalización.
• El cambio se multiplica por constantes para dividir por su recíproco ("para facilitar la lectura"). div es lento y no totalmente canalizado.
• Vectoriza el multiply/sqrt con AVX (SIMD), pero no puedes usar vzeroupper antes de las llamadas a las funciones escalar math-library exp() y log(), causando que AVXSSE transition stalls.
• Almacene la salida RNG en una lista enlazada, o en arrays que atraviese fuera de orden. Lo mismo para el resultado de cada iteración, y suma al final.

También cubierto en esta respuesta pero excluido del resumen: sugerencias que serían igual de lento en una CPU no canalizada, o eso no parece ser justificable incluso con incompetencia diabólica. por ejemplo, muchas ideas de gimp-el-compilador que producen obviamente diferentes / peores asm.

Multi-hilo mal

Tal vez use OpenMP para bucles multi-thread con muy pocas iteraciones, con mucho más sobrecarga que ganancia de velocidad. Su código de Monte-carlo tiene suficiente paralelismo para conseguir realmente un aumento de velocidad, sin embargo, esp. si tenemos éxito en hacer cada iteración lenta. (Cada hilo calcula un payoff_sum parcial, añadido al final). #omp parallel en ese bucle probablemente sería una optimización, no una pesimización.

Multi-thread pero fuerza ambos threads a compartir el mismo contador de bucle (con incrementos atomic para que el número total de iteraciones sea correcto). Esto parece diabólicamente lógico. Esto significa usar una variable static como contador de bucle. Esto justifica el uso de atomic para contadores de bucle, y crea real ping-ponging de línea de caché (siempre y cuando los hilos no se ejecutan en el mismo núcleo físico con hyperthreading; eso podría no ser como lento). De todos modos, esto es mucho más lento que el caso sin contender para lock inc. Y lock cmpxchg8b para incrementar atómicamente un uint64_t contendido en un sistema de 32 bits tendrá que reintentar en un bucle en lugar de tener el hardware arbitrar un inc atómico.

También crea false sharing , donde múltiples subprocesos mantienen sus datos privados (por ejemplo, estado RNG) en diferentes bytes del mismo línea de caché. (Tutorial de Intel sobre esto, incluyendo contadores de perf para mirar). Hay un aspecto específico de la microarquitectura en esto: Las CPU Intel especulan sobre el mal orden de la memoria que no sucede, y hay un evento de perf de máquina de orden de memoria para detectar esto, al menos en P4. La penalización podría no ser tan grande en Haswell. Como ese enlace señala, una instrucción locked asume que esto sucederá, evitando la especulación errónea. Una carga normal especula que otros núcleos no invalidarán una línea de caché entre cuando se ejecuta la carga y cuando se retira en orden de programa (a menos que utilice pause). El intercambio verdadero sin lock instrucciones ed suele ser un error. Sería interesante comparar un contador de bucle compartido no atómico con el caso atómico. Para ser realmente pesimista, mantenga el contador de bucle atómico compartido y cause un intercambio falso en la misma línea de caché o en una línea de caché diferente para alguna otra variable.

Aleatorio ideas específicas de uarch:

Si puede introducir cualquier rama impredecible, eso pesimizará el código sustancialmente. Las CPU x86 modernas tienen canalizaciones bastante largas, por lo que una mala interpretación cuesta ~15 ciclos (cuando se ejecuta desde la caché de uop).

Cadenas de dependencias:

Creo que esta era una de las partes previstas de la tarea.

Derrote la capacidad de la CPU para explotar el paralelismo a nivel de instrucción al elegir un orden de operaciones que tenga una cadena de dependencia larga en lugar de múltiples cadenas de dependencia cortas. A los compiladores no se les permite cambiar el orden de las operaciones para los cálculos FP a menos que use -ffast-math, porque eso puede cambiar los resultados (como se explica a continuación).

Para que esto sea realmente efectivo, aumente la longitud de una cadena de dependencias portadas en bucle. Sin embargo, nada salta a la vista: Los bucles tal como están escritos tienen cadenas de dependencia muy cortas: solo un FP add. (3 ciclos). Múltiples iteraciones pueden tener sus cálculos en vuelo a la vez, porque pueden comenzar mucho antes del payoff_sum += al final de la iteración anterior. (log() y exp toman muchas instrucciones, pero no mucho más que la ventana fuera de orden de Haswell para encontrar paralelismo: ROB size=192 uops de dominio fusionado, y scheduler size=60 uops de dominio no fusionado. Tan pronto como la ejecución de la iteración actual progrese lo suficientemente lejos como para dejar espacio para las instrucciones de la siguiente iteración a emitir, cualquier parte de la misma que tenga sus entradas listas (es decir, cadena dep independiente/separada) pueden comenzar a ejecutarse cuando las instrucciones más antiguas dejan las unidades de ejecución libres (por ejemplo, porque están bloqueadas en latencia, no en rendimiento.).

El estado RNG será casi con toda seguridad una cadena de dependencias más larga que la addps.

Use operaciones más lentas/más FP (esp. más división):

Dividir por 2.0 en lugar de multiplicar por 0.5, y así sucesivamente. FP multiply está fuertemente canalizado en Intel diseña, y tiene uno por 0.5 c de rendimiento en Haswell y posteriores. FP divsd/divpd solo está parcialmente canalizado . (Aunque Skylake tiene un impresionante rendimiento de uno por 4c para divpd xmm, con latencia de 13-14c, vs no canalizado en absoluto en Nehalem (7-22c)).

El do { ...; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0); está claramente probando una distancia, por lo que claramente sería apropiado para sqrt(). : P (sqrt es incluso más lento que div).

Como sugiere @ Paul Clayton, reescribir expresiones con asociativo / distributivo los equivalentes pueden introducir más trabajo (siempre y cuando no uses -ffast-math para permitir que el compilador vuelva a optimizar). (exp(T*(r-0.5*v*v)) podría convertirse en exp(T*r - T*v*v/2.0). Tenga en cuenta que mientras que la matemática en números reales es asociativa, la matemática en coma flotante es no, incluso sin considerar overflow / NaN (por lo que -ffast-math no está activado por defecto). Ver Comentario de Pablo para una sugerencia anidada muy peluda pow().

Si puede escalar los cálculos a números muy pequeños, entonces FP math ops tome ~120 ciclos adicionales para atrapar al microcódigo cuando una operación en dos números normales produce un denormal. Vea el microarch pdf de Agner Fog para los números y detalles exactos. Esto es poco probable ya que tiene una gran cantidad de multiplicaciones, por lo que el factor de escala sería cuadrado y el flujo inferior hasta 0.0. No veo ninguna manera de justificar la escala necesaria con incompetencia (incluso diabólica), solo malicia intencional.

Si puedes usar intrínsecos (<immintrin.h>)

Use movnti para desalojar sus datos de la caché. Diabólico: es nuevo y débilmente ordenado, por lo que debería permitir que la CPU lo ejecute más rápido, ¿verdad? O vea esa pregunta vinculada para un caso donde alguien estaba en peligro de hacer exactamente esto (para escrituras dispersas donde solo algunas de las ubicaciones estaban calientes). clflush es probablemente imposible, sin malicia.

Use mezclas de enteros entre operaciones matemáticas de FP para causar retrasos de bypass.

Mezcla de SSE y AVX instrucciones sin el uso adecuado de vzeroupper provoca grandes puestos en pre-Skylake (y una pena diferente en Skylake). Incluso sin eso, vectorizar mal puede ser peor que escalar (más ciclos gastados barajando datos dentro/fuera de vectores que guardados haciendo las operaciones add/sub/mul/div/sqrt para 4 iteraciones de Monte Carlo a la vez, con vectores 256b). las unidades de ejecución add/sub/mul están completamente canalizadas y de ancho completo, pero div y sqrt en vectores 256b no son tan rápidos como en 128b vectores (o escalares), por lo que la aceleración no es dramática para double.

exp() y log() no tienen soporte de hardware, por lo que esa parte requeriría extraer elementos vectoriales de nuevo a escalar y llamar a la función de biblioteca por separado, luego barajar los resultados de nuevo en un vector. libm normalmente se compila para usar solo SSE2, por lo que utilizará las codificaciones legacy-SSE de instrucciones matemáticas escalares. Si su código utiliza vectores 256b y llama exp sin hacer un vzeroupper primero, entonces se detiene. Despues volviendo, una instrucción AVX-128 como vmovsd para configurar el siguiente elemento vectorial como un arg para exp también se detendrá. Y luego exp() se detendrá de nuevo cuando ejecute una instrucción SSE. Esto es exactamente lo que sucedió en esta pregunta, causando una desaceleración 10x. (Gracias @ZBoson).

Ver también Los experimentos de Nathan Kurz con Intel math lib vs.glibc para este código. El futuro glibc vendrá con implementaciones vectorizadas de exp() y así en.

Si se dirige a pre-IvB, o esp. Nehalem, tratar de conseguir gcc para causar paradas de registro parcial con operaciones de 16 bits o 8 bits seguido de operaciones de 32 bits o 64 bits. En la mayoría de los casos, gcc usará movzx después de una operación de 8 o 16 bits, pero aquí hay un caso donde gcc modifica ah y luego lee ax

Con asm (en línea):

Con asm (en línea), podría romper la caché de uop: Un fragmento de código de 32B que no cabe en tres caché de 6uop lines fuerza un cambio de la caché uop a los decodificadores. Un ALIGN incompetente usando muchos nops de un solo byte en lugar de un par de nops largos en un objetivo de rama dentro del bucle interno podría hacer el truco. O coloque el relleno de alineación después de la etiqueta, en lugar de antes. : P Esto solo importa si el frontend es un cuello de botella, que no lo será si logramos pesimizar el resto del código.

Use código auto-modificable para activar los clears de canalización (también conocido como máquinas nucleares).

LCP stalls de instrucciones de 16 bits con inmediatez demasiado grande para caber en 8 bits es poco probable que sea útil. La caché de uop en SnB y posteriores significa que solo paga la penalización de decodificación una vez. En Nehalem (el primer i7), podría funcionar para un bucle que no encaja en el búfer de bucle 28 uop. gcc a veces generará tales instrucciones, incluso con -mtune=intel y cuando podría haber utilizado una instrucción de 32 bits.

Un modismo común para el tiempo es CPUID (serializar) entonces RDTSC. Cronometrar cada iteración por separado con un CPUID/RDTSC para asegurarse de que el RDTSC no está reordenado con instrucciones anteriores, lo que ralentizará las cosas un lote. (En la vida real, la forma inteligente de cronometrar es cronometrar todas las iteraciones juntas, en lugar de cronometrar cada una por separado y sumarlas).

Causa muchos errores de caché y otras ralentizaciones de memoria

Use un union { double d; char a[8]; } para algunas de sus variables. Causa a tienda-puesto de expedición haciendo un almacén estrecho (o Lectura-Modificación-Escritura) a solo uno de los bytes. (Ese artículo wiki también cubre muchas otras cosas de microarquitectura para las colas de carga/tienda). por ejemplo, voltea el signo de un double usando XOR 0x80 solo en el byte alto, en lugar de un operador -. El diabólicamente incompetente desarrollador puede haber oído que FP es más lento que integer, y por lo tanto tratar de hacer tanto como sea posible utilizando integer ops. (Un compilador muy bueno que apunta a FP matemáticas en ESS registros, posiblemente, puede compilar este a xorps con una constante en el otro xmm registrarse, pero la única manera en que esto no es terrible para x87 es si el compilador se da cuenta de que es negar el valor y reemplaza a la siguiente con una resta.)

Use volatile si está compilando con -O3 y no está usando std::atomic, para forzar al compilador a almacenar/recargar todo el lugar. Las variables globales (en lugar de locales) también forzarán algunos almacenes/recargas, pero el C++ el orden débil del modelo de memoria no requiere que el compilador derrame/vuelva a cargar a la memoria todo el tiempo.

Reemplace las VAR locales con miembros de una estructura grande, para que pueda controlar el diseño de la memoria.

Use arrays en la estructura para el relleno (y almacenar números aleatorios, para justificar su existencia).

Elija su diseño de memoria para todo va en una línea diferente en el mismo "conjunto" en la caché L1. Es solo asociativo de 8 vías, es decir, cada uno el set tiene 8 "formas". Las líneas de caché son 64B.

Aún mejor, poner las cosas exactamente 4096B aparte, ya que las cargas tienen una dependencia falsa en las tiendas a diferentes páginas pero con el mismo desplazamiento dentro de una página. Las CPU agresivas fuera de orden usan Desambiguación de memoria para averiguar cuándo se pueden reordenar las cargas y los almacenes sin cambiar los resultados, y la implementación de Intel tiene falsos positivos que impiden que las cargas comiencen temprano. Probablemente solo comprueben bits por debajo de la desplazamiento de página, por lo que la comprobación puede comenzar antes de que el TLB haya traducido los bits altos de una página virtual a una página física. Así como la guía de Agner, ver una respuesta de Stephen Canon, y también una sección cerca del final de la respuesta de @Krazy Glew sobre la misma pregunta. (Andy Glew fue uno de los arquitectos de la microarquitectura P6 original de Intel.)

Use __attribute__((packed)) para permitirle alinear mal las variables para que abarquen la línea de caché o incluso los límites de las páginas. (Así que una carga de uno double necesita datos de dos líneas de caché). Las cargas desalineadas no tienen penalización en ninguna uarch de Intel i7, excepto cuando se cruzan líneas de caché y líneas de página. Las divisiones de línea de caché todavía toman ciclos adicionales. Skylake reduce drásticamente la penalización por cargas de división de páginas, de 100 a 5 ciclos. (Sección 2.1.3). Tal vez relacionado con ser capaz de hacer dos paseos de página en paralelo.

Una división de página en un atomic<uint64_t> debería ser casi el peor caso, esp. si es 5 bytes en una página y 3 bytes en la otra página, o cualquier otra cosa que no sea 4: 4. Incluso las divisiones por el medio son más eficientes para las divisiones de línea de caché con vectores 16B en algunos uarches, IIRC. Ponga todo en un alignas(4096) struct __attribute((packed)) (para ahorrar espacio, por supuesto), incluyendo una matriz para el almacenamiento de los resultados de RNG. Lograr la desalineación usando uint8_t o uint16_t para algo antes del contador.

Si puede hacer que el compilador use modos de direccionamiento indexados, derrotará a uop micro-fusion. Tal vez usando #define s para reemplazar variables escalares simples con my_data[constant].

Si puede introducir un nivel adicional de indirección, por lo que las direcciones de carga/almacenamiento no se conocen temprano, eso puede pesimizar aún más.

Matrices transversales en orden no contiguo

Creo que podemos llegar a una justificación incompetente para introducir una matriz en primer lugar: Nos permite separar la generación de números aleatorios del uso de números aleatorios. Los resultados de cada iteración también se pueden almacenar en una matriz, que se resumirá más adelante (con una incompetencia más diabólica).

Para "aleatoriedad máxima", podríamos tener un bucle de hilo sobre la matriz aleatoria escribiendo nuevos números aleatorios en ella. El hilo que consume los números aleatorios podría generar un índice aleatorio para cargar un número aleatorio. (Hay algo de trabajo aquí, pero la microarquitectura ayuda a que las direcciones de carga se conozcan temprano para que cualquier posible latencia de carga se pueda resolver antes de que se necesiten los datos cargados.) Tener un lector y writer en diferentes núcleos causará que se borre la tubería de especulación errónea que ordena la memoria (como se discutió anteriormente para el caso de uso compartido falso).

Para la máxima pesimización, haga un bucle sobre su matriz con una zancada de 4096 bytes (es decir, 512 dobles). por ejemplo,

for (int i=0 ; i<512; i++)
    for (int j=i ; j<UPPER_BOUND ; j+=512)
        monte_carlo_step(rng_array[j]);

Así que el patrón de acceso es 0, 4096, 8192,...,
8, 4104, 8200, ...
16, 4112, 8208, ...

Esto es lo que obtendrías por acceder a una matriz 2D como double rng_array[MAX_ROWS][512] en el orden incorrecto (haciendo loop sobre filas, en lugar de columnas dentro de una fila en el bucle interno, como sugiere @JesperJuhl). Si la incompetencia diabólica puede justificar una matriz 2D con dimensiones como esa, la incompetencia del mundo real de la variedad jardín justifica fácilmente el bucle con el patrón de acceso incorrecto. Esto sucede en código real en la vida real.

Ajuste los límites del bucle si es necesario para usar muchas páginas diferentes en lugar de reutilizar las mismas pocas páginas, si el array no es tan grande. La prefetching de hardware no funciona (tampoco) en todas las páginas. El prefetcher puede rastrear un flujo hacia adelante y un flujo hacia atrás dentro de cada página (que es lo que sucede aquí), pero solo actuará sobre él si el ancho de banda de memoria no está saturado con no-prefetch.

Esto también generará muchos errores de TLB, a menos que las páginas se fusionen en una página hugepage (Linux hace esto de manera oportunista para asignaciones anónimas (no respaldadas por archivos) como malloc/new ese uso mmap(MAP_ANONYMOUS)).

En lugar de una matriz para almacenar la lista de resultados, podría usar una lista enlazada . Luego, cada iteración requeriría una carga de seguimiento de puntero (un riesgo de dependencia real sin PROCESAR para la dirección de carga de la siguiente carga). Con un mal asignador, es posible que logre dispersar los nodos de la lista en la memoria, derrotando la caché. Con un asignador diabólicamente incompetente, podría poner cada nodo al principio de su propia página. (por ejemplo, asignar con mmap(MAP_ANONYMOUS) directamente, sin dividir páginas o rastrear tamaños de objetos para soportar correctamente free).

Estos no son realmente específicos de la microarquitectura, y tienen poco que ver con la canalización (la mayoría de estos también serían una desaceleración en una CPU no canalizada).

Algo fuera de tema: hacer que el compilador genere peor código / haga más trabajo:

Use C++11 std::atomic<int> y std::atomic<double> para el código más pesado. Las MFENCEs y las instrucciones ed lockson bastante lentas incluso sin contención de otro hilo.

-m32 hará más lento el código, porque x87 el código será peor que el código SSE2. La convención de llamadas de 32 bits basada en la pila toma más instrucciones, y pasa incluso args FP en la pila a funciones como exp().