He estado atormentando mi 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 tarea es lo opuesto a nuestra primera tarea 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 lo que 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 CPUIDinstrucción y a cómo determinar el tamaño del caché, así como a los intrínsecos y la CLFLUSHinstrucción.
• 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 asumió-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 las personas hayan 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.

Lecturas importantes: 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 elx86etiqueta wiki, 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 pidió a los estudiantes que optimizaran un códigogcc -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 que la use para guiar sus esfuerzos de 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 el texto 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 exp/ logfunciones de biblioteca. No hay una manera 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 causar problemas en una tubería clásica en orden de RISC . Por lo general, los únicos riesgos 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 . (a excepción depopcnt/lzcnt/tzcnt, que tienen una dependencia falsa de su destino en las CPU de Intel , aunque es 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 tienda 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 de punto FP.

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 de ROB no ocurren en SnB, porque cambió a usar un archivo de registro físico. También un caché uop y una memoria interna diferente formato uop). El término "arquitectura i7" no es útil, porque tiene poco sentido agrupar a 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. Entonces, a nivel de chip, el nombre 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.

• Multihilo con un solo contador de bucle compartido std::atomic<uint64_t> , por lo que ocurre 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 para 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 .
• Calcula cada iteración independientemente, con algo aún más pesado que RDTSC. por ejemplo CPUID/ RDTSCo una función de tiempo que hace 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.
• Vectoriza la multiplicación / sqrt con AVX (SIMD), pero no se usa vzeroupperantes de las llamadas a la biblioteca matemática escalar exp()y las log()funciones, lo que provoca 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 parcial payoff_sum, agregado al final). #omp parallelen 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 atomicincrementos para que el número total de iteraciones sea correcto). Esto parece diabólicamente lógico. Esto significa usar una staticvariable como contador de bucles. Esto justifica el uso de atomiclos contadores de bucles y crea ping-ponging real de línea de caché (siempre que los subprocesos 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 lock inc. Y lock cmpxchg8bpara incrementar atómicamente un contendiente uint64_ten un sistema de 32 bits tendrá que volver a intentarlo en un bucle en lugar de hacer que el hardware arbitre un atómico inc.

También cree un uso compartido 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 lockinstrucción de educación 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 cuando la carga se ejecuta y cuando se retira en orden de programa (a menos que lo usespause ). El intercambio verdadero sin lockinstrucciones de edición 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 alguna rama impredecible , 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 los use -ffast-math, porque eso puede cambiar los resultados (como se discute 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 un complemento de FP. (3 ciclos). Las iteraciones múltiples pueden tener sus cálculos en vuelo a la vez, porque pueden comenzar mucho antes payoff_sum +=del final de la iteración anterior. ( log()y exptome 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 progrese 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, cadena de depósito independiente / separada) puede comenzar a ejecutarse cuando las instrucciones más antiguas abandonan las unidades de ejecución gratis (por ejemplo, porque tienen cuellos de botella en la latencia, no en el rendimiento).

El estado RNG seguramente será una cadena de dependencia de bucle más larga que la 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 rendimiento de 0.5c en Haswell y versiones posteriores. FP divsd/ divpdsolo está parcialmente canalizado . (Aunque Skylake tiene un rendimiento impresionante por cada 4c divpd xmm, con una latencia de 13-14c, frente a no estar conectado en absoluto en Nehalem (7-22c)).

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

Como sugiere @Paul Clayton, la reescritura de expresiones con equivalentes asociativos / distributivos puede introducir más trabajo (siempre y cuando no se use -ffast-mathpara permitir que el compilador se vuelva a optimizar). (exp(T*(r-0.5*v*v))podría convertirse 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 considerar el desbordamiento / NaN (por -ffast-mathlo que no está activado de manera predeterminada). Vea el comentario de Paul para una pow()sugerencia anidada muy peluda .

Si puede reducir los cálculos a números muy pequeños, entonces las operaciones matemáticas de FP toman ~ 120 ciclos adicionales para atrapar al microcódigo cuando una operación en dos números normales produce un denormal . Vea 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 forma de justificar la escala necesaria con incompetencia (incluso diabólica), solo malicia intencional.

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

Use movntipara desalojar sus datos de la memoria caché . Diabólico: es nuevo y está 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 en el que alguien estaba en peligro de hacer exactamente esto (para escritos dispersos donde solo algunas de las ubicaciones estaban calientes). clflushEs 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 combinación de instrucciones SSE y AVX sin el uso adecuado de vzerouppercausa 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 de 128b (o escalares), por lo que la aceleración no es dramáticadouble.

exp()y log()no tiene 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 mezclar 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 256b vectores y llamadas expsin hacer un vzeroupperprimer intento , entonces se detiene. Después de regresar, una instrucción AVX-128 como vmovsdconfigurar el siguiente elemento vectorial como argumento para exptambién se detendrá. Y luego se 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).

Vea también los experimentos de Nathan Kurz con lib de matemáticas vs. glibc de Intel para este código . El futuro 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 se usará movzxdespués de una operación de 8 o 16 bits, pero aquí hay un caso en el que gcc modifica ahy luego leeax

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. Un incompetente que ALIGNusa 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 ser 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 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=intely cuando podría haber utilizado una instrucción de 32 bits.

Un idioma común para el tiempo es CPUID(serializar) entoncesRDTSC . Tiempo cada iteración por separado con un CPUID/ RDTSCa asegúrese de que el RDTSCno se reordena con las instrucciones anteriores, lo que retrasará las cosas un montón . (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 a 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, voltee el signo de un doubleXOR 0x80 usando solo 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 matemáticas de FP en registros SSE posiblemente compile esto en unxorps 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 la siguiente suma con una resta.

Úselo volatilesi está compilando -O3y no está utilizando 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 agresivas fuera de servicio 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).

Utilícelo __attribute__((packed))para alinear mal las variables de modo que abarquen la línea de caché o incluso los límites de la página. (Entonces, una carga de uno doublenecesita 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 de división 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. Lograr la desalineación usando uint8_to uint16_tpara algo antes del mostrador.

Si puede hacer que el compilador use modos de direccionamiento indexados, eso derrotará a la micro fusión de uop . Quizás usando #defines 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 "aleatoriedad máxima", 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 puede resolverse 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, repita su matriz con un paso 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 para 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 de jardines 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 un flujo hacia adelante y uno hacia atrás dentro de cada página (que es lo que sucede aquí), pero solo actuará en él si el ancho de banda de la 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 enorme ( Linux lo hace de manera oportunista para asignaciones anónimas (no respaldadas por archivos) como malloc/ newque usanmmap(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 poner cada nodo al comienzo de su propia página. (p. ej., asignar mmap(MAP_ANONYMOUS)directamente, sin dividir páginas o rastrear tamaños de objetos para soportar adecuadamente 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 el código más pesimista. Las lockinstrucciones MFENCE y ed son bastante lentas incluso sin la contención de otro hilo.

-m32hará 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 similares exp(). atomic<uint64_t>::operator++on -m32requiere un lock cmpxchg8Bbucle (i586). (¡Así que usa eso para los contadores de bucles! [Risa malvada]).

-march=i386también pesimizará (gracias @Jesper). FP se compara con fcomson 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 las atomicoperaciones de 64 bits se compilan para llamadas a funciones 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/ explpara mayor precisión y lentitud adicional en las ABI donde sizeof ( long double) es 10 o 16 (con relleno para alineación). (IIRC, Windows de 64 bits usa 8bytes long doubleequivalentes a double. De todos modos, la carga / almacenamiento de operandos FP de 10 bytes (80 bits) es de 4/7 uops, floato doublesolo toma 1 uop por fld m64/m32/ fst). Forzar x87 con long doublederrotas auto-vectorización incluso para gcc -m64 -march=haswell -O3.

Si no usa atomic<uint64_t>contadores de bucle, úselo long doublepara todo, incluidos los contadores de bucle.

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 vars temporales causará más almacenamiento / recarga. Sin volatileo 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 a chara alias cualquier cosa, por lo que almacenar a través de un char*obliga al compilador a almacenar / recargar todo antes / después de la tienda de bytes, incluso en -O3. (Este es un problema para el código deuint8_t vectorización automática que opera en una matriz de , por ejemplo).

Pruebe uint16_tlos contadores de bucle para forzar el truncamiento a 16 bits, probablemente utilizando un tamaño de operando de 16 bits (posibles paradas) y / o movzxinstrucciones adicionales (seguro). El desbordamiento firmado es un comportamiento indefinido , por lo que, a menos que use -fwrapvo 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.

Forzar la conversión de entero a floaty de nuevo. Y / o double<=> floatconversiones. 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 extra pxorpara 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 esto es altamente improbable, excepto en un sistema multi-socket) Ahora solo haga el ajuste incorrecto y hágalo con demasiada frecuencia. Además del tiempo empleado en el estado del subproceso de almacenamiento / 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 gettimeofdaypueden implementarse en el espacio de usuario con, sin transición al modo kernel. (glibc en Linux hace esto con la ayuda del núcleo, ya que el núcleo 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.

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 e instrucciones más recientes y forzará el uso de la FPU x87.

• usa std::atomicvariables en 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 versus fila mayor).

• 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) al asignarlas en newlugar de permitirles que tengan una "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 :)

Puedes usar long doublepara 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:

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

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 dar como resultado 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 a la 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 a la memoria de 5 *. Coloque el nodo de manera tal que avance 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 durante 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.