c++ - Desoptimizar un programa para la canalización en las CPU de la familia Intel Sandybridge

optimization x86 (4)

Puedes usar long double para el cálculo. En x86 debería ser el formato de 80 bits. Solo el legado, x87 FPU tiene soporte para esto.

Algunas deficiencias de x87 FPU:

La falta de SIMD, puede necesitar más instrucciones.
Basado en pila, problemático para arquitecturas súper escalares y canalizadas.
Un conjunto de registros separado y bastante pequeño puede necesitar más conversión de otros registros y más operaciones de memoria.
En el Core i7 hay 3 puertos para SSE y solo 2 para x87, el procesador puede ejecutar menos instrucciones paralelas.

He estado aturdiéndome el cerebro durante una semana tratando de completar esta tarea y espero que alguien aquí pueda guiarme hacia el camino correcto. Permítanme comenzar con las instrucciones del instructor:

Su asignación es lo opuesto a nuestra primera asignación de laboratorio, que fue optimizar un programa de números primos. Su propósito en esta tarea es pesimizar el programa, es decir, hacerlo correr más lento. Ambos son programas intensivos en CPU. Tardan unos segundos en ejecutarse en nuestras PC de laboratorio. No puede cambiar el algoritmo.

Para desoptimizar el programa, use su conocimiento de cómo funciona la tubería Intel i7. Imagine formas de reordenar las rutas de instrucciones para introducir WAR, RAW y otros peligros. Piense en formas de minimizar la efectividad del caché. Sé diabólicamente incompetente.

La asignación dio la opción de programas de Whetstone o Montecarlo. Los comentarios sobre la efectividad de la memoria caché solo se aplican principalmente a Whetstone, pero elegí el programa de simulación Monte-Carlo:

// Un-modified baseline for pessimization, as given in the assignment #include <algorithm> // Needed for the "max" function #include <cmath> #include <iostream> // A simple implementation of the Box-Muller algorithm, used to generate // gaussian random numbers - necessary for the Monte Carlo method below // Note that C++11 actually provides std::normal_distribution<> in // the <random> library, which can be used instead of this function double gaussian_box_muller() { double x = 0.0; double y = 0.0; double euclid_sq = 0.0; // Continue generating two uniform random variables // until the square of their "euclidean distance" // is less than unity do { x = 2.0 * rand() / static_cast<double>(RAND_MAX)-1; y = 2.0 * rand() / static_cast<double>(RAND_MAX)-1; euclid_sq = x*x + y*y; } while (euclid_sq >= 1.0); return x*sqrt(-2*log(euclid_sq)/euclid_sq); } // Pricing a European vanilla call option with a Monte Carlo method double monte_carlo_call_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) { double S_adjust = S * exp(T*(r-0.5*v*v)); double S_cur = 0.0; double payoff_sum = 0.0; for (int i=0; i<num_sims; i++) { double gauss_bm = gaussian_box_muller(); S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm); payoff_sum += std::max(S_cur - K, 0.0); } return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T); } // Pricing a European vanilla put option with a Monte Carlo method double monte_carlo_put_price(const int& num_sims, const double& S, const double& K, const double& r, const double& v, const double& T) { double S_adjust = S * exp(T*(r-0.5*v*v)); double S_cur = 0.0; double payoff_sum = 0.0; for (int i=0; i<num_sims; i++) { double gauss_bm = gaussian_box_muller(); S_cur = S_adjust * exp(sqrt(v*v*T)*gauss_bm); payoff_sum += std::max(K - S_cur, 0.0); } return (payoff_sum / static_cast<double>(num_sims)) * exp(-r*T); } int main(int argc, char **argv) { // First we create the parameter list int num_sims = 10000000; // Number of simulated asset paths double S = 100.0; // Option price double K = 100.0; // Strike price double r = 0.05; // Risk-free rate (5%) double v = 0.2; // Volatility of the underlying (20%) double T = 1.0; // One year until expiry // Then we calculate the call/put values via Monte Carlo double call = monte_carlo_call_price(num_sims, S, K, r, v, T); double put = monte_carlo_put_price(num_sims, S, K, r, v, T); // Finally we output the parameters and prices std::cout << "Number of Paths: " << num_sims << std::endl; std::cout << "Underlying: " << S << std::endl; std::cout << "Strike: " << K << std::endl; std::cout << "Risk-Free Rate: " << r << std::endl; std::cout << "Volatility: " << v << std::endl; std::cout << "Maturity: " << T << std::endl; std::cout << "Call Price: " << call << std::endl; std::cout << "Put Price: " << put << std::endl; return 0; }

Los cambios que he realizado parecen aumentar el tiempo de ejecución del código en un segundo, pero no estoy completamente seguro de qué puedo cambiar para detener la tubería sin agregar código. Un punto en la dirección correcta sería increíble, agradezco cualquier respuesta.

Actualización: el profesor que asignó esta tarea publicó algunos detalles

Los aspectos más destacados son:

Es una clase de arquitectura del segundo semestre en un colegio comunitario (usando el libro de texto de Hennessy y Patterson).
las computadoras de laboratorio tienen CPU Haswell
Los estudiantes han estado expuestos a la instrucción CPUID y a cómo determinar el tamaño de la memoria caché, así como a las instrucciones intrínsecas y CLFLUSH .
cualquier opción del compilador está permitida, y también lo está en línea asm.
Se anunció que escribir su propio algoritmo de raíz cuadrada está fuera de juego

Los comentarios de Cowmoogun sobre el meta hilo indican que no estaba claro que las optimizaciones del compilador pudieran ser parte de esto, y asumieron -O0 , y que un aumento del 17% en el tiempo de ejecución era razonable.

Por lo tanto, parece que el objetivo de la tarea era lograr que los estudiantes reordenen el trabajo existente para reducir el paralelismo en el nivel de instrucción o cosas por el estilo, pero no es algo malo que la gente haya profundizado y aprendido más.

Tenga en cuenta que esta es una pregunta de arquitectura informática, no una pregunta sobre cómo hacer que C ++ sea lento en general.

Respuesta tardía, pero no creo que hayamos abusado de las listas vinculadas y del TLB lo suficiente.

Use mmap para asignar sus nodos, de modo que use principalmente el MSB de la dirección. Esto debería resultar en largas cadenas de búsqueda TLB, una página tiene 12 bits, dejando 52 bits para la traducción, o alrededor de 5 niveles que debe atravesar cada vez. Con un poco de suerte, deben ir a la memoria cada vez para buscar 5 niveles más 1 acceso de memoria para llegar a su nodo, el nivel superior probablemente estará en la memoria caché en algún lugar, por lo que podemos esperar un acceso de memoria de 5 *. Coloque el nodo de manera que avance con el peor borde para que leer el siguiente puntero cause otras 3-4 búsquedas de traducción. Esto también podría destruir totalmente el caché debido a la gran cantidad de búsquedas de traducción. Además, el tamaño de las tablas virtuales puede hacer que la mayoría de los datos del usuario se paginen en el disco por un tiempo adicional.

Al leer desde la lista enlazada individual, asegúrese de leer desde el principio de la lista cada vez para causar un retraso máximo en la lectura de un solo número.

Algunas cosas que puede hacer para que las cosas funcionen tan mal como sea posible:

compile el código para la arquitectura i386. Esto evitará el uso de SSE y las instrucciones más recientes y forzará el uso de la FPU x87.
use std::atomic variables std::atomic todas partes. Esto los hará muy caros debido a que el compilador se ve obligado a insertar barreras de memoria en todo el lugar. Y esto es algo que una persona incompetente podría hacer para "garantizar la seguridad del hilo".
asegúrese de acceder a la memoria de la peor manera posible para que el prefetcher pueda predecir (columna mayor frente a fila principal).
para hacer que sus variables sean más caras, puede asegurarse de que todas tengan una ''duración de almacenamiento dinámico'' (asignación asignada) asignándolas con new lugar de permitirles tener ''duración de almacenamiento automática'' (asignación de pila).
asegúrese de que toda la memoria que asigne esté alineada de manera extraña y evite por completo la asignación de páginas grandes, ya que hacerlo sería demasiado eficiente para TLB.
hagas lo que hagas, no construyas tu código con el optimizador de compiladores habilitado. Y asegúrese de habilitar los símbolos de depuración más expresivos que pueda (no hará que el código se ejecute más lentamente, pero desperdiciará algo de espacio extra en el disco).

Nota: Esta respuesta básicamente solo resume mis comentarios que @Peter Cordes ya incorporó en su muy buena respuesta. Sugiérale que obtenga su voto a favor si solo tiene uno de sobra :)

Lectura importante de antecedentes: el microarchivo de Agner Fog , y probablemente también lo que todo programador debe saber sobre la memoria de Ulrich Drepper. Vea 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 Haswell, con diagramas .

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

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

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

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

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

Los peligros WAR y WAW para los registros no son un problema, gracias al cambio de nombre de los registros . (excepto popcnt / lzcnt / tzcnt , que tienen una dependencia falsa de su destino en las CPU de Intel , aunque sea de solo escritura, es decir, WAW se maneja como un peligro RAW + una escritura). Para el pedido de memoria, las CPU modernas usan colas de almacenamiento para retrasar la confirmación en la memoria caché hasta el retiro, evitando también los peligros WAR y WAW .

¿Por qué mulss solo toma 3 ciclos en Haswell, diferente de las tablas de instrucciones de Agner? tiene más información sobre el cambio de nombre de registro y la ocultación de la latencia de FMA en un bucle de producto FP dot.

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 la marca "i7" para Sandybridge y microarquitecturas posteriores. SnB es cuando la familia P6 evolucionó hacia una nueva especie, la familia SnB . En muchos sentidos, Nehalem tiene más en común con Pentium III que con Sandybridge (p. Ej., Las paradas de lectura de registro y las paradas de lectura ROB no ocurren en SnB, porque cambió a usar un archivo de registro físico. También un caché uop y un interno diferente formato uop). El término "arquitectura i7" no es útil , porque tiene poco sentido agrupar la familia SnB con Nehalem pero no con Core2. (Sin embargo, Nehalem introdujo la arquitectura de caché L3 inclusiva compartida para conectar múltiples núcleos. Y también GPU integradas. Por lo tanto, a nivel de chip, la denominación tiene más sentido).

Resumen de las buenas ideas que la incompetencia diabólica puede justificar

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

Hilo múltiple con un solo contador de bucle std::atomic<uint64_t> , por lo que se produce el número total correcto de iteraciones. Atomic uint64_t es especialmente malo con -m32 -march=i586 . Para obtener puntos de bonificación, haga arreglos para que se desalinee y cruce un límite de página con una división desigual (no 4: 4).
Falso uso compartido de alguna otra variable no atómica -> borra la canalización de especulación errónea del orden de memoria, así como errores adicionales de caché.
En lugar de usar - en variables FP, XOR el byte alto con 0x80 para voltear el bit de signo, causando paradas de reenvío de la tienda .
RDTSC 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 realiza una llamada al sistema. Las instrucciones de serialización son intrínsecamente hostiles.
Cambia las multiplicaciones por constantes para dividir por sus recíprocos ("para facilitar la lectura"). div es lento y no está totalmente canalizado.
Vectorice la multiplicación / sqrt con AVX (SIMD), pero no puede usar vzeroupper antes de las llamadas a las vzeroupper escalar de la biblioteca matemática exp() y log() , causando paradas de transición AVX <-> SSE .
Almacene la salida de RNG en una lista vinculada o en matrices que atraviese fuera de orden. Lo mismo para el resultado de cada iteración, y suma al final.

También se cubre en esta respuesta, pero se excluye del resumen: sugerencias que serían igual de lentas en una CPU no interconectada, o que no parecen justificables incluso con una incompetencia diabólica. por ejemplo, muchas ideas de compilación gimp-the-compiler que producen asm obviamente diferentes / peores.

Multihilo mal

Tal vez use OpenMP para bucles multihilo con muy pocas iteraciones, con mucho más sobrecarga que ganancia de velocidad. Sin embargo, su código monte-carlo tiene suficiente paralelismo para obtener una aceleración, esp. si logramos hacer que cada iteración sea lenta. (Cada hilo calcula un payoff_sum parcial, agregado al final). #omp parallel en ese bucle probablemente sería una optimización, no una pesimización.

Multihilo pero obliga a ambos hilos a compartir el mismo contador de bucles (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 bucles. Esto justifica el uso de atomic para los contadores de bucles y crea ping-ponging real de línea de caché (siempre que los hilos no se ejecuten en el mismo núcleo físico con hyperthreading; eso podría no ser tan lento). De todos modos, esto es mucho más lento que el caso no disputado para lock inc . Y lock cmpxchg8b para incrementar atómicamente un uint64_t contendido en un sistema de 32 bits tendrá que volver a intentarlo en un bucle en lugar de hacer que el hardware arbitre un inc atómico.

También cree un intercambio falso , donde varios subprocesos mantienen sus datos privados (por ejemplo, estado RNG) en diferentes bytes de la misma línea de caché. (Tutorial de Intel al respecto, incluidos los contadores de rendimiento para mirar) . Hay un aspecto específico de la microarquitectura en esto : las CPU de Intel especulan que no ocurre un pedido incorrecto de memoria, y hay un evento de rendimiento de máquina limpia de orden de memoria para detectar esto, al menos en P4 . La penalización podría no ser tan grande en Haswell. Como señala ese enlace, una instrucción lock supone 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 el momento en que se ejecuta la carga y cuando se retira en el orden del programa (a menos que use pause ). El intercambio verdadero sin instrucciones lock suele ser un error. Sería interesante comparar un contador de bucle compartido no atómico con el caso atómico. Para realmente pesimizar, mantenga el contador de bucle atómico compartido y provoque un intercambio falso en la misma línea de caché o en otra diferente para alguna otra variable.

Ideas aleatorias específicas de uarch:

Si puede introducir ramas impredecibles , eso pesimizará sustancialmente el código. Las CPU x86 modernas tienen tuberías bastante largas, por lo que una predicción errónea cuesta ~ 15 ciclos (cuando se ejecuta desde la caché uop).

Cadenas de dependencia:

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

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

Para que esto sea realmente efectivo, aumente la longitud de una cadena de dependencia transportada en bucle. Sin embargo, nada salta a la vista como obvio: los bucles tal como están escritos tienen cadenas de dependencia transportadas en bucles muy cortas: solo una adición de FP. (3 ciclos). Las iteraciones múltiples pueden tener sus cálculos en vuelo a la vez, porque pueden comenzar mucho antes de 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: tamaño ROB = 192 uops de dominio fusionado, y tamaño del planificador = 60 uops de dominio no fusionado . Tan pronto como la ejecución de la iteración actual progresa lo suficiente como para dejar espacio para que se emitan las instrucciones de la próxima iteración, cualquier parte de ella que tenga listas sus entradas (es decir, una cadena dep independiente / separada) puede comenzar a ejecutarse cuando las instrucciones anteriores dejan libres las unidades de ejecución (por ejemplo, porque tienen cuellos de botella en la latencia, no en el rendimiento).

El estado de RNG seguramente será una cadena de dependencia de bucle más larga que los addps .

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

Divida por 2.0 en lugar de multiplicar por 0.5, y así sucesivamente. La multiplicación de FP está fuertemente canalizada en los diseños de Intel, y tiene uno por cada rendimiento de 0.5c en Haswell y versiones posteriores. FP divsd / divpd solo está parcialmente canalizado . (Aunque Skylake tiene un rendimiento impresionante por 4c para divpd xmm , con una latencia de 13-14c, vs no está canalizado en absoluto en Nehalem (7-22c)).

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

Como sugiere @Paul Clayton, la reescritura de expresiones con equivalentes asociativos / distributivos puede introducir más trabajo (siempre que no utilice -ffast-math para permitir que el compilador se 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 si bien las matemáticas en números reales son asociativas, las matemáticas en coma flotante no lo son , incluso sin considerando el desbordamiento / NaN (razón por la cual -ffast-math no está -ffast-math por defecto). Vea el comentario de Paul para una sugerencia de pow() anidada muy peluda.

Si puede reducir los cálculos a números muy pequeños, entonces las operaciones matemáticas de FP requieren ~ 120 ciclos adicionales para capturar el microcódigo cuando una operación en dos números normales produce un denormal . Consulte el pdf de microarchivo de Agner Fog para conocer los números y detalles exactos. Esto es poco probable ya que tiene muchas multiplicaciones, por lo que el factor de escala sería cuadrado y se desbordaría hasta 0.0. No veo ninguna manera de justificar la escala necesaria con incompetencia (incluso diabólica), solo malicia intencional.

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

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

Utilice la combinación aleatoria de enteros entre las operaciones matemáticas de FP para provocar retrasos de derivación.

La vzeroupper de instrucciones SSE y AVX sin el uso adecuado de vzeroupper provoca grandes puestos en pre-Skylake (y una penalización 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 256b vectores) . Las unidades de ejecución add / sub / mul están totalmente canalizadas y de ancho completo, pero div y sqrt en los vectores de 256b no son tan rápidos como en los vectores de 128b (o escalares), por lo que la aceleración no es dramática para el double .

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

Consulte también los experimentos de Nathan Kurz con lib de matemáticas vs. glibc de Intel para este código . Future Glibc vendrá con implementaciones vectorizadas de exp() y así sucesivamente.

Si apunta a pre-IvB, o esp. Nehalem, intenta que gcc provoque paradas de registro parcial con operaciones de 16 bits u 8 bits seguidas 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 en el que gcc modifica ah y luego lee ax

Con (en línea) asm:

Con el asm (en línea), puede romper la memoria caché uop: un fragmento de código de 32B que no cabe en tres líneas de caché 6uop fuerza un cambio de la memoria caché uop a los decodificadores. Una ALIGN incompetente usando muchos nop s de byte único en lugar de un par de nop 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, lo cual no será si logramos pesimizar el resto del código.

Utilice el código de modificación automática para activar la eliminación de canalizaciones (también conocido como máquinas nucleares).

Es improbable que los bloqueos de LCP a partir de instrucciones de 16 bits con elementos inmediatos demasiado grandes para caber en 8 bits sean útiles. El caché uop en SnB y posterior 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 cabe en el búfer de bucle de 28 uop. A veces, gcc generará tales instrucciones, incluso con -mtune=intel y cuando podría haber usado una instrucción de 32 bits.

Un idioma común para el tiempo es CPUID (para serializar) y luego RDTSC . RDTSC cada iteración por separado con un CPUID / RDTSC para asegurarte de que el RDTSC no se reordena con instrucciones anteriores, lo que ralentizará mucho las cosas. (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 una union { double d; char a[8]; } union { double d; char a[8]; } union { double d; char a[8]; } para algunas de sus variables. Causar un bloqueo de reenvío de tienda haciendo una tienda estrecha (o Leer-Modificar-Escribir) a solo uno de los bytes. (Ese artículo wiki también cubre muchas otras cosas de microarquitectura para colas de carga / almacenamiento). por ejemplo, voltear el signo de un double usando XOR 0x80 solo en el byte alto , en lugar de un operador - . El desarrollador diabólicamente incompetente puede haber escuchado que FP es más lento que un entero y, por lo tanto, intenta hacer todo lo posible utilizando operaciones enteras. (Un compilador muy bueno dirigido a FP math en registros SSE posiblemente compile esto en un xorps con una constante en otro registro xmm, pero la única forma en que esto no es terrible para x87 es si el compilador se da cuenta de que está negando el valor y reemplaza el luego agregue con una resta.)

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

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

Use matrices en la estructura para rellenar (y almacenar números aleatorios, para justificar su existencia).

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

Aún mejor, separe las cosas exactamente 4096B, ya que las cargas tienen una dependencia falsa de las tiendas en diferentes páginas pero con el mismo desplazamiento dentro de una página . Las CPU fuera de servicio agresivas utilizan la desambiguación de la memoria para determinar cuándo se pueden reordenar las cargas y las tiendas sin cambiar los resultados , y la implementación de Intel tiene falsos positivos que evitan que las cargas comiencen temprano. Probablemente solo verifican bits por debajo del desplazamiento de la página, por lo que la verificación puede comenzar antes de que el TLB haya traducido los bits altos de una página virtual a una página física. Además de la guía de Agner, vea 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 la página. (Por lo tanto, una carga de un double necesita datos de dos líneas de caché). Las cargas desalineadas no tienen penalización en ningún Intel i7 uarch, excepto cuando cruzan líneas de caché y líneas de página. Las divisiones de línea de caché aún requieren ciclos adicionales . Skylake reduce drásticamente la penalización por cargas divididas de página, de 100 a 5 ciclos. (Sección 2.1.3) . Quizás relacionado con la posibilidad de hacer dos caminatas de página en paralelo.

Una división de página en un atomic<uint64_t> debería ser el peor de los casos , especialmente. si son 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 en el medio son más eficientes para divisiones de línea de caché con vectores 16B en algunas uarches, IIRC. Ponga todo en un alignas(4096) struct __attribute((packed)) (para ahorrar espacio, por supuesto), incluida una matriz para el almacenamiento de los resultados RNG. Logre 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, eso derrotará a la micro fusión de uop . Quizás 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.

Arreglos 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 podrían almacenarse en una matriz, para sumarlos más tarde (con más incompetencia diabólica).

Para "máxima aleatoriedad", podríamos tener un hilo en bucle 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 microarquitecturalmente ayuda a que las direcciones de carga se conozcan temprano, por lo que cualquier latencia de carga posible se puede resolver antes de que se necesiten los datos cargados). Tener un lector y un escritor en diferentes núcleos provocará errores en el orden de la memoria -la tubería de especulación se borra (como se discutió anteriormente para el caso de falso intercambio).

Para una pesimación máxima, recorra su matriz con una zancada de 4096 bytes (es decir, 512 dobles). p.ej

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

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

Esto es lo que obtendría al acceder a una matriz 2D como double rng_array[MAX_ROWS][512] en el orden incorrecto (bucle sobre filas, en lugar de columnas dentro de una fila en el bucle interno, como lo sugiere @JesperJuhl). Si la incompetencia diabólica puede justificar una matriz 2D con dimensiones como esa, la incompetencia de la variedad del jardín en el mundo real 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 páginas, si la matriz no es tan grande. La captación previa de hardware no funciona (tampoco / en absoluto) en todas las páginas. El prefetcher puede rastrear una transmisión hacia adelante y una hacia atrás dentro de cada página (que es lo que sucede aquí), pero solo actuará si el ancho de banda de la memoria no está saturado con la no captación previa.

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

En lugar de una matriz para almacenar la lista de resultados, puede usar una lista vinculada . Luego, cada iteración requeriría una carga de búsqueda de puntero (un peligro de dependencia RAW verdadero para la dirección de carga de la próxima carga). Con un mal asignador, puede lograr dispersar los nodos de la lista en la memoria, derrotando la memoria caché. Con un asignador diabólicamente incompetente, podría colocar cada nodo al comienzo de su propia página. (p. ej., asigne con mmap(MAP_ANONYMOUS) directamente, sin dividir páginas o rastrear tamaños de objeto para soportar correctamente de forma free ).

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

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

Use C ++ 11 std::atomic<int> y std::atomic<double> para obtener el código más pesimista. Las instrucciones MFENCE y lock son bastante lentas incluso sin la contención de otro hilo.

-m32 hará que el código sea más lento, porque el código x87 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 los argumentos FP en la pila a funciones como exp() . atomic<uint64_t>::operator++ en -m32 requiere un bucle de lock cmpxchg8B (i586). (¡Así que usa eso para los contadores de bucles! [Risa malvada]).

-march=i386 también pesimizará (gracias @Jesper). FP se compara con fcom son más lentos que 686 fcomi . Pre-586 no proporciona una tienda atómica de 64 bits (y mucho menos un cmpxchg), por lo que todas atomic operaciones atomic 64 bits se compilan para llamadas a funciones de libgcc (que probablemente se compila para i686, en lugar de usar un bloqueo). Pruébelo en el enlace Godbolt Compiler Explorer en el último párrafo.

Use long double / sqrtl / sqrtl para mayor precisión y lentitud adicional en ABIs donde sizeof ( long double ) es 10 o 16 (con relleno para alineación). (IIRC, Windows de 64 bits usa 8byte de long double equivalente a double . (De todos modos, la carga / almacenamiento de operandos FP de 10byte (80 bits) es 4/7 uops, vs. float o double solo toma 1 uop cada uno para fld m64/m32 / fst ) Forzar x87 con derrotas long double auto-vectorización incluso para gcc -m64 -march=haswell -O3 .

Si no utiliza atomic<uint64_t> contadores de bucles atomic<uint64_t> , use el long double para todo, incluidos los contadores de bucles.

atomic<double> compila, pero las operaciones de lectura-modificación-escritura como += no son compatibles (incluso en 64 bits). atomic<long double> tiene que llamar a una función de biblioteca solo para cargas / tiendas atómicas. Probablemente sea realmente ineficiente, porque el x86 ISA no admite naturalmente cargas / almacenes atómicos de 10 bytes , y la única forma en que puedo pensar sin bloquear ( cmpxchg16b ) requiere el modo de 64 bits.

En -O0 , romper una gran expresión asignando partes a variables temporales causará más almacenamiento / recarga. Sin volatile o algo así, esto no importará con la configuración de optimización que usaría una compilación real de código real.

Las reglas de alias de C permiten que un char alias cualquier cosa, por lo que el almacenamiento a través de un char* obliga al compilador a almacenar / recargar todo antes / después de la tienda de bytes, incluso a -O3 . (Este es un problema para el código de vectorización automática que opera en una matriz de uint8_t , por ejemplo).

Pruebe los contadores de bucle uint16_t para forzar el truncamiento a 16 bits, probablemente mediante el uso de un tamaño de operando de 16 bits (posibles paradas) y / o instrucciones adicionales de movzx (seguro). El desbordamiento firmado es un comportamiento indefinido , por lo tanto, a menos que use -fwrapv o al menos -fno-strict-overflow , los contadores de bucle firmado no tienen que volver a firmar cada vez que se repite , incluso si se usan como compensaciones para punteros de 64 bits.

Fuerza la conversión de entero a float y viceversa. Y / o double <=> conversiones float . Las instrucciones tienen una latencia mayor que una, y escalar int-> float ( cvtsi2ss ) está mal diseñado para no poner a cero el resto del registro xmm. (gcc inserta un pxor adicional para romper dependencias, por esta razón).

Configure con frecuencia la afinidad de su CPU con una CPU diferente (sugerida por @Egwor). razonamiento diabólico: no desea que un núcleo se sobrecaliente al ejecutar su hilo durante mucho tiempo, ¿verdad? Tal vez cambiar a otro núcleo permitirá que ese turbo central tenga una mayor velocidad de reloj. (En realidad: están tan térmicamente cerca el uno del otro que es muy poco probable, excepto en un sistema de múltiples sockets). Ahora solo haga el ajuste incorrecto y hágalo con demasiada frecuencia. Además del tiempo invertido en el estado del subproceso de guardado / restauración del sistema operativo, el nuevo núcleo tiene cachés L2 / L1 fríos, caché uop y predictores de ramificación.

Introducir frecuentes llamadas innecesarias al sistema puede ralentizarlo, sin importar cuáles sean. Aunque algunos importantes pero simples como gettimeofday pueden implementarse en el espacio de usuario con, sin transición al modo kernel. (glibc en Linux hace esto con la ayuda del kernel, ya que el kernel exporta código en el vdso ).

Para obtener más información sobre la sobrecarga de llamadas del sistema (incluidas las fallas de caché / TLB después de regresar al espacio de usuario, no solo el cambio de contexto en sí), el documento FlexSC tiene un excelente análisis de contador de rendimiento de la situación actual, así como una propuesta para el sistema de procesamiento por lotes llamadas de procesos de servidor de múltiples subprocesos masivos.