Desoptimizar un progtwig para la tubería en las CPU de la familia Intel Sandybridge

He estado trabajando en mi cerebro durante una semana tratando de completar esta tarea y espero que alguien aquí pueda guiarme hacia el camino correcto. Déjame comenzar con las instrucciones del instructor:

Su tarea es lo opuesto a nuestra primera tarea de laboratorio, que era optimizar un progtwig de números primos. Su propósito en esta tarea es pesimizar el progtwig, es decir, hacerlo más lento. Ambos son progtwigs intensivos en CPU. Tardan unos segundos en ejecutarse en nuestras computadoras de laboratorio. No puedes cambiar el algoritmo.

Para desoptimizar el progtwig, use su conocimiento de cómo funciona la línea de producción Intel i7. Imagine formas de volver a ordenar las rutas de instrucción para introducir WAR, RAW y otros peligros. Piense en maneras de minimizar la efectividad del caché. Sea diabólicamente incompetente.

La asignación dio una opción de progtwigs Whetstone o Monte-Carlo. Los comentarios de eficacia de caché son principalmente aplicables a Whetstone, pero elegí el progtwig de simulación Monte-Carlo:

// Un-modified baseline for pessimization, as given in the assignment #include  // Needed for the "max" function #include  #include  // 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  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(RAND_MAX)-1; y = 2.0 * rand() / static_cast(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(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(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 hecho parecen boost el tiempo de ejecución del código por segundo, pero no estoy del todo seguro de qué puedo cambiar para detener el proceso sin agregar código. Un punto en la dirección correcta sería increíble, agradezco cualquier respuesta.


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

Los aspectos más destacados son:

  • Es una clase de architecture de segundo semestre en una universidad comunitaria (usando el libro de texto Hennessy y Patterson).
  • las computadoras del 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 intrínsecos y la instrucción CLFLUSH .
  • cualquier opción de comstackdor está permitida, al igual que el asm en línea.
  • Escribir su propio algoritmo de raíz cuadrada fue anunciado como estar fuera del pálido

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

Parece que el objective de la tarea era hacer que los alumnos reordenan el trabajo existente para reducir el paralelismo a nivel de instrucción o cosas por el estilo, pero no es malo que la gente haya profundizado más y haya aprendido más.


Tenga en cuenta que esta es una pregunta de architecture de computadora, no una pregunta acerca de cómo hacer C ++ lento en general.

Lectura de fondo importante: el microarch pdf de Agner Fog , y probablemente también lo que todo progtwigdor debería saber sobre la memoria de Ulrich Drepper. Ver también los otros enlaces en la wiki de la etiqueta x86 , especialmente los manuales de optimización de Intel, y el análisis de la microarchitecture Haswell de David Kanter , con diagtwigs .

Muy buena asignación; mucho mejor que los que he visto donde se les pidió a los estudiantes que optimizaran algunos códigos 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 el pipeline de CPU y lo 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 usa matrices, y gran parte del costo son llamadas a funciones de biblioteca exp / log . No hay una manera obvia de tener más o menos paralelismo de nivel de instrucción, y la cadena de dependencia transportada por bucle es muy corta.

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

Las CPU de la familia Intel Sandybridge son diseños agresivos fuera de servicio que emplean muchos transistores y potencia para encontrar el paralelismo y evitar peligros (dependencias) que podrían afectar a un RISC clásico en orden . Por lo general, los únicos riesgos tradicionales que disminuyen la velocidad son las dependencias RAW “verdaderas” que hacen que el rendimiento esté limitado por la latencia.

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

El nombre de marca “i7” fue presentado 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 microarchitectures posteriores. SnB es cuando la familia P6 se ​​convirtió 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, registrar puestos de lectura y puestos de lectura ROB no ocurren en SnB, porque cambió a usar un archivo de registro físico. También una memoria caché uop y una interna diferente formato uop). El término “architecture i7” no es útil , porque no tiene sentido agrupar la familia SnB con Nehalem, pero no con Core2. (Sin embargo, Nehalem introdujo la architecture compartida de caché L3 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 de que la incompetencia diabólica puede justificar

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

  • std::atomic con un único contador std::atomic bucles std::atomic , por lo que se produce el número total correcto de iteraciones. Atomic uint64_t es especialmente malo con -m32 -march=i586 . Para puntos de bonificación, arregle para que esté desalineada, y cruce un límite de página con una división desigual (no 4: 4).
  • Compartimiento falso para alguna otra variable no atómica -> se borra la tubería de especulación de orden de memoria, así como fallas extra de caché.
  • En lugar de usar - en variables de FP, XOR el byte alto con 0x80 para invertir el bit de signo, provocando paradas de reenvío de tienda .
  • RDTSC cada iteración de forma independiente, con algo incluso 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.
  • El cambio se multiplica por constantes para dividir por su recíproco (“para facilitar la lectura”). div es lento y no está totalmente canalizado.
  • Vectorice el multiplicador / sqrt con AVX (SIMD), pero no use vzeroupper antes de las llamadas a las vzeroupper escalares math-library exp() y log() , lo que provocará la interrupción de la transición AVX < -> SSE .
  • Almacene la salida RNG en una lista vinculada, o en matrices que atraviesa fuera de servicio. Lo mismo para el resultado de cada iteración y sum 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 derivada, o que no parecen justificarse incluso con una incompetencia diabólica. por ejemplo, muchas ideas de gimp-the-compiler que producen asm obviamente diferente / peor.


Múltiples hilos mal

Tal vez use OpenMP para bucles de múltiples hilos 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, especialmente. si tenemos éxito en hacer que cada iteración sea lenta. (Cada hilo calcula un payoff_sum parcial, agregado al final). #omp parallel en ese ciclo probablemente sea una optimización, no una pesimismo.

Multilínea pero obliga a ambos hilos a compartir el mismo contador de bucles (con incrementos atomic para que el número total de iteraciones sea el 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 un ping-ponging real de la línea de caché (siempre que los hilos no se ejecuten en el mismo núcleo físico con hyperthreading, lo que puede no ser tan lento). De todos modos, esto es mucho más lento que el caso sin contestar para lock inc . Y lock cmpxchg8b para incrementar atómicamente un uint64_t en un sistema de 32 bits tendrá que volver a intentarlo en un bucle en lugar de hacer que el hardware arbitrate un inc atómico.

Cree también uso compartido falso , donde varios subprocesos mantienen sus datos privados (por ejemplo, estado RNG) en diferentes bytes de la misma línea de caché. (Intel tutorial al respecto, incluidos los contadores de rendimiento para mirar) . Esto tiene un aspecto específico de microarchitecture : las CPU Intel especulan sobre la omisión de las órdenes erróneas de memoria, y hay un evento de perf de limpieza de orden de la memoria para detectar esto, al menos en P4 . La pena puede no ser tan grande en Haswell. Como señala ese enlace, una instrucción de lock asume que esto sucederá, evitando errores de especulación. 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 progtwig (a menos que use pause ). El verdadero intercambio sin instrucciones de 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 haga que se compartan de forma falsa en la misma línea de caché o en otra para otra variable.


Ideas aleatorias específicas de uarch:

Si puede introducir twigs impredecibles , eso pesimizará sustancialmente el código. Las CPU x86 modernas tienen tuberías bastante largas, por lo que un error de lectura cuesta unos 15 ciclos (cuando se ejecuta desde la memoria caché uop).


Cadenas de dependencia:

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

Derrote la capacidad de la CPU para aprovechar el paralelismo a nivel de instrucción eligiendo un orden de operaciones que tenga una larga cadena de dependencias en lugar de múltiples cadenas cortas de dependencia. Los comstackdores 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 explica a continuación).

Para realmente hacer esto efectivo, aumente la longitud de una cadena de dependencia transportada por bucle. Sin embargo, nada salta a la vista como obvio: los bucles, tal como están escritos, tienen cadenas de dependencia de ciclo muy cortas: solo un complemento FP. (3 ciclos). Varias 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 el 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 las instrucciones de la próxima iteración, cualquier parte de ella que tenga sus entradas listas (es decir, cadena de depósito independiente / separada) puede comenzar a ejecutarse cuando las instrucciones anteriores dejan libres las unidades de ejecución (por ejemplo, están embotellados en la latencia, no en el rendimiento).

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


Use operaciones de 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. FP multiplicado se canaliza en gran medida en los diseños de Intel, y tiene una por cada 0.5c de rendimiento en Haswell y más tarde. FP divsd / divpd solo se canaliza parcialmente . (Aunque Skylake tiene un rendimiento impresionante por 4c para divpd xmm , con una latencia de 13-14c, vs no interconectado 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); está probando claramente una distancia, así que claramente sería apropiado para sqrt() . : P ( sqrt es incluso más lento que div ).

Como lo 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 comstackdor 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 de coma flotante no lo son , incluso sin considerando el desbordamiento / NaN (que es la razón -ffast-math cual -ffast-math no están -ffast-math por defecto). Vea el comentario de Paul para una sugerencia anidada de pow() muy peluda.

Si puede escalar los cálculos a números muy pequeños, entonces las operaciones de matemática FP toman ~ 120 ciclos extra para atrapar al microcódigo cuando una operación en dos números normales produce un denormal . Consulte el pdf de microarmador 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 se cuadraría y descendería hasta 0.0. No veo ninguna forma de justificar el escalamiento necesario con incompetencia (incluso diabólica), solo malicia intencional.


Si puede usar intrínsecos ( )

Use movnti para desalojar sus datos de la memoria caché . Diabólico: es nuevo y está débilmente ordenado, por lo que debería dejar 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 escrituras dispersas donde solo algunas de las ubicaciones estaban calientes). clflush es probablemente imposible sin malicia.

Utilice combinaciones enteras entre las operaciones de matemática de FP para provocar retrasos de derivación.

Mezclar las instrucciones de SSE y AVX sin el uso apropiado de vzeroupper provoca puestos grandes en pre-Skylake (y una penalización diferente en Skylake ). Incluso sin eso, vectorizar mal puede ser peor que escalar (más ciclos gastaron mezclar datos dentro / fuera de vectores que guardados haciendo las operaciones add / sub / mul / div / sqrt para 4 iteraciones de Montecarlo a la vez, con 256b vectores) . las unidades de ejecución add / sub / mul están completamente segmentadas y de ancho completo, pero div y sqrt en vectores 256b no son tan rápidos como en los vectores 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á extraer los elementos vectoriales de nuevo a escalar y llamar a la función de biblioteca por separado, luego volver a mezclar los resultados en un vector. libm normalmente se comstack para usar solo SSE2, por lo que utilizará las codificaciones SSE heredadas de las instrucciones de escalar matemáticas. Si su código usa 256b vectores y llamadas exp sin hacer un vzeroupper primero, entonces se vzeroupper . Después de regresar, una instrucción AVX-128 como vmovsd para configurar el siguiente vector elemento como un argumento para exp también se detendrá. Y luego exp() se parará de nuevo cuando ejecute una instrucción SSE. Esto es exactamente lo que sucedió en esta pregunta , causando una ralentización de 10 veces. (Gracias @ZBoson).

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


Si se dirige a pre-IvB, o esp. Nehalem, intente hacer que gcc cause puestos de registro parcial con operaciones de 16 bits u 8 bits seguidos por operaciones de 32 bits o de 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 que gcc modifica ah y luego lee ax


Con asm (en línea):

Con el asm (en línea), puede romper la caché uop: un fragmento de código 32B que no se ajusta a tres líneas de caché de 6uop obliga a cambiar el caché uop a los decodificadores. Un ALIGN incompetente que use muchos nop de un solo byte en lugar de un par de nop largos en un blanco de bifurcación 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 la interfaz es un cuello de botella, que no será si logramos pesimizar el rest del código.

Use código de modificación automática para desencadenar despejes de tuberías (también conocidos como bombas nucleares).

No es probable que las paradas de LCP a partir de instrucciones de 16 bits con tiempos demasiado grandes para caber en 8 bits sean útiles. El caché uop en SnB y más tarde significa que solo pagas la penalización de deencoding 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. gcc algunas veces generará tales instrucciones, incluso con -mtune=intel y cuando podría haber usado una instrucción de 32 bits.


Una expresión común para el tiempo es CPUID (para serializar) luego RDTSC . RDTSC cada iteración por separado con un CPUID / RDTSC para asegurarse de que el RDTSC no se reordena con las instrucciones anteriores, lo que ralentizará mucho las cosas. (En la vida real, la forma inteligente de hacer el tiempo es sincronizar todas las iteraciones, en lugar de cronometrarlas por separado y sumrlas).


Causa muchas fallas 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 tus variables. Causa un locking de almacenamiento de tienda haciendo un almacén estrecho (o lectura-modificación-escritura) en solo uno de los bytes. (Ese artículo wiki también cubre muchos otros aspectos microarquitectónicos para colas de carga / tienda). por ejemplo, invierta el signo de un double con XOR 0x80 solo en el byte alto , en lugar de a - operador. El desarrollador diabólicamente incompetente puede haber escuchado que FP es más lento que el entero, y por lo tanto tratar de hacer tanto como sea posible usando operaciones enteras. (Un muy buen comstackdor que apunta a matemática FP en registros SSE posiblemente puede comstackr 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 comstackdor se da cuenta de que está anulando el valor y reemplaza el luego agrega con un restar).


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

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

Usa arreglos en la estructura para relleno (y almacena números aleatorios, para justificar su existencia).

Elija su diseño de memoria para que todo pase a una línea diferente en el mismo “conjunto” en la caché L1 . Solo es asociativo de 8 vías, es decir, cada conjunto tiene 8 “formas”. Las líneas de caché son 64B.

Mejor aún, coloque las cosas exactamente 4096B separadas, 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 servicio utilizan la desambiguación de 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 verifiquen bits debajo del desplazamiento de 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 microarchitecture P6 original de Intel).

Use __attribute__((packed)) para permitirle alinear mal las variables para que abarquen los límites de la línea de caché o incluso de la página. (Entonces, 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 páginas. Las divisiones de línea de caché todavía toman ciclos extra . Skylake reduce drásticamente la penalización de las cargas divididas de página, de 100 a 5 ciclos. (Sección 2.1.3) . Quizás relacionado con poder hacer dos caminatas de página en paralelo.

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

Si puede hacer que el comstackdor use modos de direccionamiento indexados, eso derrotará a la microfusión de uop . Tal vez usando #define s para reemplazar variables escalares simples con my_data[constant] .

Si puede introducir un nivel adicional de direccionamiento indirecto, entonces las direcciones de carga / almacenamiento no se conocen desde el principio, lo que puede hacer que se pesen aún más.


Matrices de poligonales en orden no contiguo

Creo que podemos encontrar 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 sumr luego (con una incompetencia más diabólica).

Para “aleatoriedad máxima”, podríamos tener un hilo que recorre el conjunto aleatorio y escribir nuevos números aleatorios en él. El hilo que consume los números aleatorios podría generar un índice aleatorio para cargar un número aleatorio. (Aquí hay algo de make-how, pero microarquitectivamente ayuda a que las direcciones de carga se conozcan temprano, por lo que cualquier posible latencia de carga se puede resolver antes de que se necesiten los datos cargados). Tener un lector y escritor en diferentes núcleos causará errores en la ordenación de la memoria -la depuración de la especulación se borra (como se discutió anteriormente para el caso de compartir falsa).

Para una máxima pesimización, 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 

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 (haciendo un bucle sobre las 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 en 2D con dimensiones como esa, la incompetencia en el mundo real de una variedad de jardín justifica fácilmente el bucle con un patrón de acceso incorrecto. Esto sucede en un código real en la vida real.

Ajuste los límites de bucle si es necesario para usar muchas páginas diferentes en lugar de reutilizar las mismas pocas páginas, si la matriz no es tan grande. La recuperación previa de hardware no funciona (tampoco / en absoluto) en todas las páginas. El captador previo puede rastrear una secuencia hacia adelante y hacia atrás dentro de cada página (que es lo que sucede aquí), pero solo actuará sobre ella si el ancho de banda de la memoria no está saturado con la captura no previa.

Esto también generará muchas fallas TLB, a menos que las páginas se fusionen en una página enorme ( Linux lo hace de forma 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 . Entonces, cada iteración requeriría una carga de persecución del puntero (un verdadero peligro de dependencia RAW para la dirección de carga de la próxima carga). Con un mal asignador, puede administrar dispersar los nodos de lista en la memoria, derrotando el caché. Con un asignador diabólicamente incompetente, podría poner cada nodo al comienzo de su propia página. (por ejemplo, asignar con mmap(MAP_ANONYMOUS) directamente, sin dividir las páginas ni hacer un seguimiento de los tamaños de los objetos para admitir correctamente de forma free ).


Estos no son realmente específicos de microarchitecture, 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 integrada).

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

Utilice C ++ 11 std::atomic y std::atomic para el código más pesimista. Las instrucciones MFENCE y lock son bastante lentas incluso sin 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 stack toma más instrucciones, y pasa incluso args FP en la stack a funciones como exp() . atomic::operator++ en -m32 requiere un bucle lock cmpxchg8B (i586). (¡Así que usa eso para los contadores de bucle! [Risa malvada]).

-march=i386 también se pesimizará (gracias @Jesper). Los FP comparados con fcom son más lentos que 686 fcomi . Pre-586 no proporciona una tienda atómica de 64 bits (por no hablar de cmpxchg), por lo que todas atomic operaciones atomic 64 bits comstackn las llamadas a la función libgcc (que probablemente se comstack para i686, en lugar de usar un locking). Pruébelo en el enlace Godbolt Compiler Explorer en el último párrafo.

Use long double / sqrtl / sqrtl long double para mayor precisión y lentitud adicional en ABI donde sizeof ( long double ) es 10 o 16 (con relleno para la alineación). (IIRC, Windows de 64 bits utiliza 8 veces el long double equivalente al double . (De todos modos, la carga / almacenamiento de operandos de FP de 10byte (80bit) es de 4/7 uops, contra float o solo double tomando 1 upa para fld m64/m32 / fst ) Forzar x87 con auto-vectorización de derrotas long double incluso para gcc -m64 -march=haswell -O3 .

Si no utiliza atomic contadores de bucle atomic , use el long double para todo, incluidos los contadores de bucle.

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


En -O0 , dividir una gran expresión asignando partes a vars temporales causará más almacenamiento / recargas. Sin volatile o algo así, esto no importará con las configuraciones de optimización que una construcción real de código real usaría.

Las reglas de alias de C permiten a un char alias de cualquier cosa, por lo que almacenar a través de un char* obliga al comstackdor a almacenar / recargar todo antes / después del byte-store, incluso en -O3 . (Este es un problema para el código de auto-vectorización 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 16 bits de tamaño de operando ( movzx potenciales) y / o instrucciones extra movzx (seguro). El desbordamiento firmado es un comportamiento indefinido , por lo tanto, a menos que utilice -fwrapv o al menos -fno-strict-overflow , los contadores de bucle con signo no tienen que volver a firmarse de nuevo en cada iteración , incluso si se utilizan como desplazamientos a punteros de 64 bits.


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


Establezca con frecuencia su afinidad de CPU a una CPU diferente (sugerida por @Egwor). razonamiento diabólico: no quieres que un núcleo se sobrecaliente para que no ejecute el hilo durante mucho tiempo, ¿o sí? Quizás cambiar a otro núcleo permitirá que ese núcleo turbo scope una velocidad de reloj más alta. (En realidad: están tan cerca térmicamente entre sí que esto es muy poco probable, excepto en un sistema multi-socket). Ahora solo afine la afinación y hágalo con demasiada frecuencia. Además del tiempo invertido en el estado de subprocesos de guardar / restaurar OS, el nuevo núcleo tiene cachés L2 / L1 fríos, caché uop y predictores de bifurcación.

La introducción de 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 núcleo exporta código en el vdso ).

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

Algunas cosas que puede hacer para que las cosas rindan lo peor posible:

  • comstackr el código para la architecture i386. Esto evitará el uso de SSE y las instrucciones más nuevas y forzará el uso de la FPU x87.

  • use std::atomic variables std::atomic todas partes. Esto los hará muy costosos debido a que el comstackdor 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 lo pronostique (columna principal vs. fila principal).

  • para que sus variables sean más caras, puede asegurarse de que todas tengan ‘duración de almacenamiento dynamic’ (stack asignada) asignándolas con new lugar de dejarlas con ‘duración de almacenamiento automática’ (stack asignada).

  • asegúrese de que toda la memoria que asigna esté muy extrañamente alineada y evite asignar grandes páginas, ya que hacerlo sería demasiado eficiente para TLB.

  • Hagas lo que hagas, no construyas tu código con el optimizador de comstackdores 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 lento, pero perderá algo de espacio extra en el disco).

Nota: Esta respuesta básicamente resume mis comentarios de que Peter Cordes ya ha incorporado su muy buena respuesta. Sugiere que obtenga tu voto positivo si solo tienes uno de repuesto 🙂

Puedes usar el long double para computación. En x86 debería ser el formato de 80 bits. Solo el legado, la FPU x87 tiene soporte para esto.

Pocas deficiencias de la FPU x87:

  1. Lack of SIMD, may need more instructions.
  2. Stack based, problematic for super scalar and pipelined architectures.
  3. Separate and quite small set of registers, may need more conversion from other registers and more memory operations.
  4. On the Core i7 there are 3 ports for SSE and only 2 for x87, the processor can execute less parallel instructions.

Late answer but I don’t feel we have abused linked lists and the TLB enough.

Use mmap to allocate your nodes, such that your mostly use the MSB of the address. This should result in long TLB lookup chains, a page is 12 bits, leaving 52 bits for the translation, or around 5 levels it must travers each time. With a bit of luck they must go to memory each time for 5 levels lookup plus 1 memory access to get to your node, the top level will most likely be in cache somewhere, so we can hope for 5*memory access. Place the node so that is strides the worst border so that reading the next pointer would cause another 3-4 translation lookups. This might also totally wreck the cache due to the massive amount of translation lookups. Also the size of the virtual tables might cause most of the user data to be paged to disk for extra time.

When reading from the single linked list, make sure to read from the start of the list each time to cause maximum delay in reading a single number.