soporta - ¿Cómo puedo causar una falta de caché de instrucciones?

metadata share facebook

Question

Se me ha asignado la tarea de generar una cierta cantidad de errores de caché de datos y errores de caché de instrucciones. He podido manejar la porción de caché de datos sin problema.

Así que me quedo con la generación de los errores de la memoria caché No tengo ni idea de qué causa estos. ¿Alguien puede sugerir un método para generarlos?

Estoy usando GCC en Linux.

Answer 1

Además de todas las otras formas mencionadas aquí, otra forma muy confiable de forzar una falta de memoria caché de instrucciones es tener un código de auto-modificación.

Si escribe en una página de código en la memoria (asumiendo que configuró el sistema operativo para permitir esto), entonces, por supuesto, la línea correspondiente de caché de instrucciones se vuelve inmediatamente inválida, y el procesador se ve obligado a recuperarla.

Por cierto, no es la predicción de rama lo que provoca una falla icache, sino simplemente la bifurcación . Se pierde la memoria caché de instrucciones cuando el procesador intenta ejecutar una instrucción que no se ha ejecutado recientemente. El x86 moderno es lo suficientemente inteligente como para obtener previamente las instrucciones en secuencia, por lo que es muy poco probable que pierda el icache simplemente caminando hacia adelante de una instrucción a la siguiente. Pero cualquier rama (condicional o de otro tipo) salta a una nueva dirección fuera de secuencia. Si la nueva dirección de instrucción no se ha ejecutado recientemente y no está cerca del código que ya estaba ejecutando, es probable que esté fuera de la memoria caché, y el procesador debe detenerse y esperar a que lleguen las instrucciones de la RAM principal. Esto es exactamente como el caché de datos.

Algunos procesadores muy modernos (i7 reciente) pueden ver las próximas sucursales en el código y comenzar el icache antes de buscar los posibles objetivos, pero muchos no (consolas de videojuegos). La obtención de datos de la RAM principal a icache es totalmente diferente de la etapa de "obtención de instrucciones" de la tubería, que es de lo que se trata la predicción de rama.

"Obtención de instrucciones" es parte de la tubería de ejecución de la CPU y se refiere a llevar un código de operación de icache a la unidad de ejecución de la CPU, donde puede comenzar a decodificar y hacer el trabajo. Eso es diferente de la búsqueda de "caché de instrucciones", que debe ocurrir muchos ciclos antes e implica que el circuito de caché realice una solicitud a la unidad de memoria principal para enviar algunos bytes a través del bus. La primera es una interacción entre dos etapas de la tubería de la CPU. El segundo es una interacción entre la tubería y el caché de memoria y la RAM principal, que es un circuito mucho más complicado. Los nombres son confusamente similares, pero son operaciones totalmente separadas.

Por lo tanto, otra forma de causar errores en la caché de instrucciones sería escribir (o generar) muchas funciones realmente grandes, de modo que el segmento de código sea enorme. Luego, llame salvajemente de una función a otra, para que, desde el punto de vista de la CPU, esté haciendo GOTOs locos en toda la memoria.

Answer 2

Como las personas han explicado, una falta de memoria caché de instrucciones es conceptualmente lo mismo que una falta de memoria caché de datos: las instrucciones no están en la memoria caché. Esto se debe a que el contador del programa del procesador (PC) ha saltado a un lugar que no se ha cargado en el caché, o se ha vaciado porque el caché se llenó, y esa línea de caché fue la elegida para el desalojo (generalmente menos recientemente usado).

Es un poco más difícil generar suficiente código a mano para forzar una falta de instrucción que forzar una falta de caché de datos.

Una forma de obtener gran cantidad de código, con poco esfuerzo, es escribir un programa que genere código fuente.

Por ejemplo, escriba un programa para generar una función con una instrucción de cambio enorme (en C) [Advertencia, sin probar]:

printf("void bigswitch(int n) {/n    switch (n) {");
for (int i=1; i<100000; ++i) {
    printf("        case %d: n += %d;/n", n, n+i/2);
}
printf("    }/n    return n;}/n");

Luego, puede llamar a esto desde otra función, y puede controlar qué tan grande es el salto a lo largo de la línea de caché.

Una propiedad de una instrucción de conmutación es que el código puede forzarse para ejecutarse hacia atrás o en patrones al elegir el parámetro. Por lo tanto, puede trabajar con los mecanismos de pre-captura y predicción, o tratar de trabajar contra ellos.

La misma técnica se podría aplicar para generar muchas funciones también, para garantizar que la memoria caché pueda ''romperse'' a voluntad. Por lo tanto, es posible que tenga bigswitch001, bigswitch002, etc. Puede llamar a este mediante un interruptor que también genera.

Si puede hacer que cada función (aproximadamente) tenga un número de líneas de i-cache de tamaño y también genere más funciones de las que caben en el caché, entonces el problema de generar errores de caché de instrucciones se vuelve más fácil de controlar.

Puede ver exactamente qué tan grande es una función, una instrucción de cambio completa, o cada tramo de una instrucción de cambio volcando el ensamblador (usando gcc -S), u objdump el archivo .o. Así que podría "ajustar" el tamaño de una función ajustando el número de declaraciones de case: . También puede elegir cuántas líneas de caché son afectadas, mediante una elección juiciosa del parámetro a bigswitchNNN ().

Answer 3

Para las faltas de caché de instrucciones, debe ejecutar segmentos de código que están muy separados. Dividir su lógica entre múltiples llamadas a funciones sería una forma de hacerlo.

Answer 4

Su proyecto requiere un conocimiento del hardware de caché del sistema de destino, que incluye, entre otros, su tamaño de caché (el tamaño general del caché), el tamaño de la línea de caché (entidad de caché más pequeña), la asociatividad y las políticas de escritura y reemplazo. Cualquier algoritmo realmente bueno diseñado para probar el rendimiento de un caché debe tener todo esto en cuenta, ya que no existe un único algoritmo general que pueda probar de manera efectiva todas las configuraciones de caché, aunque puede diseñar un generador de rutinas de prueba parametrizado efectivo, que podría generar una rutina de prueba adecuada con suficientes detalles sobre la arquitectura de caché de un determinado destino. A pesar de esto, creo que mi sugerencia a continuación es una prueba general bastante buena, pero primero quería mencionar:

Usted menciona que tiene una prueba de caché de datos de trabajo que utiliza una "matriz de enteros grande a [100] .... [que accede] a los elementos de tal manera que la distancia entre los dos elementos es mayor que el tamaño de la línea de caché (32 bytes en mi caso) ". Tengo curiosidad por saber cómo ha determinado que funciona su algoritmo de prueba y cómo ha determinado cuántas faltas de caché de datos son el resultado de su algoritmo, en lugar de fallas causadas por otros estímulos. De hecho, con una matriz de prueba de 100 * sizeof (int), su área de datos de prueba solo tiene 400 bytes en la mayoría de las plataformas de propósito general de la actualidad (quizás 800 bytes si está en una plataforma de 64 bits o 200 bytes si estamos usando una plataforma de 16 bits). Para la gran mayoría de las arquitecturas de caché, toda la matriz de prueba se integrará en la caché muchas veces, lo que significa que los accesos aleatorios a la matriz llevarán la matriz completa a la caché en algún lugar (400 / cache_line_size) * 2 accesos, y todos el acceso después de eso será un acierto de caché, independientemente de cómo ordene sus accesos, a menos que salga un momento de interrupción del temporizador de tics del hardware o del sistema operativo y vacíe algunos o todos sus datos almacenados en caché.

Con respecto a la memoria caché de instrucciones: otros han sugerido el uso de un conmutador grande (): una declaración de caso o llamadas a funciones a funciones en ubicaciones dispares, ninguna de las cuales sería predeciblemente efectiva sin un diseño cuidadoso (y me refiero CUIDADOSAMENTE) del tamaño del código en las respectivas ramas de caso o ubicaciones y tamaños de las funciones ubicadas de manera desigual. La razón de esto es que los bytes a lo largo de la memoria "se pliegan" (técnicamente, "alias uno al otro" en) el caché en un patrón totalmente predecible. Si controla con cuidado la cantidad de instrucciones en cada rama de un interruptor () - declaración de caso, es posible que pueda llegar a alguna parte con su prueba, pero si simplemente lanza una gran cantidad de instrucciones indiscriminadas en cada una, no tiene idea de cómo se plegarán en la memoria caché y en qué casos del conmutador () - alias de caso se aliarán entre sí para usarlas para expulsarse mutuamente de la memoria caché.

Supongo que no estás demasiado familiarizado con el código de ensamblaje, pero tienes que creerme aquí, este proyecto lo está gritando. Confíe en mí, no utilizo el código de ensamblaje donde no se solicita, y prefiero la programación en OO C ++, utilizando las jerarquías de ADT STL y polimórficas siempre que sea posible. Pero en su caso, realmente no hay otra manera infalible de hacerlo, y el ensamblaje le dará el control absoluto sobre los tamaños de bloque de código que realmente necesita para poder generar efectivamente los índices de aciertos de caché especificados. No tendría que convertirse en un experto en ensamblajes, y probablemente ni siquiera tendría que aprender las instrucciones y la estructura necesarias para implementar un prólogo y epílogo en lenguaje C (Google para la "función de ensamblaje de C-callable"). Usted escribe algunos prototipos de funciones externas en “C” para sus funciones de ensamblaje, y listo. Si le interesa aprender algo de ensamblaje, cuanta más lógica de prueba coloque en las funciones de ensamblaje, menor será el "efecto Heisenberg" que impone a su prueba, ya que puede controlar con cuidado dónde van las instrucciones de control de prueba (y por lo tanto Su efecto en el caché de instrucciones). Pero para la mayor parte de su código de prueba, puede usar un montón de instrucciones "nop" (a la memoria caché de instrucciones realmente no le importa qué instrucciones contiene), y probablemente solo ponga la instrucción de "devolución" de su procesador al final de cada una Bloque de código.

Ahora digamos que su caché de instrucciones es de 32 K (bastante pequeño para los estándares actuales, pero tal vez aún sea común en muchos sistemas integrados). Si su caché es asociativa a 4 vías, puede crear ocho funciones de ensamblaje 8K separadas e idénticas al contenido (lo que se espera que tenga un valor de código de 64K, dos veces el tamaño del caché), cuya mayor parte es solo un conjunto de instrucciones NOP . Haces que todos caigan uno tras otro en la memoria (generalmente, simplemente definiendo uno tras otro en el archivo fuente). Luego, los llama desde una función de control de prueba que usa secuencias cuidadosamente calculadas para generar cualquier proporción de aciertos de caché que desee (con una granularidad de curso, ya que las funciones tienen una longitud total de 8K). Si llama a la primera, segunda, tercera y cuarta funciones una tras otra, sabrá que ha llenado toda la memoria caché con el código de esas funciones de prueba. Llamar a cualquiera de ellos nuevamente en este punto no dará lugar a una falta de caché de instrucciones (con la excepción de las líneas desalojadas por las propias instrucciones de la función de control de prueba), sino a cualquiera de las otras (5, 6, 7 u 8; elija el quinto) desalojará a uno de los otros (aunque el que se desaloje depende de la política de reemplazo de su caché). En este punto, el único al que puedes llamar y saber que NO desalojarás a otro es al que acabas de llamar (el quinto), y los únicos a los que puedes llamar y saber que DESECHARás a otro es al que aún no has llamado Llamado (el 6, 7, u 8). Para hacer esto más fácil, simplemente mantenga una matriz estática con el mismo tamaño que la cantidad de funciones de prueba que tiene. Para desencadenar un desalojo, llame a la función al final de la matriz y mueva su puntero a la parte superior de la matriz, desplazando las otras hacia abajo. Para NO desencadenar un desalojo, llame al que llamó más recientemente (el que está en la parte superior de la matriz; ¡asegúrese de NO desplazar a los demás en este caso!). Realice algunas variaciones sobre esto (quizás realice 16 funciones de ensamblaje 4K separadas) si necesita una granularidad más fina. Por supuesto, todo esto depende de que el tamaño de la lógica de control de prueba sea insignificante en comparación con el tamaño de cada "forma" asociativa de la caché; para un control más positivo, podría poner la lógica de control de prueba en las funciones de prueba, pero para un control perfecto tendría que diseñar la lógica de control completamente sin ramificación interna (solo ramificación al final de cada función de ensamblaje), pero creo que Me detendré aquí, ya que eso probablemente complique las cosas.

Fuera de lugar y no probado, la totalidad de una de las funciones de ensamblaje para x86 podría tener este aspecto:

myAsmFunc1:
   nop
   nop
   nop  # ...exactly enough NOPs to fill one "way" of the cache
   nop  # minus however many bytes a "ret" instruction is (1?)
   .
   .
   .
   nop
   ret  # return to the caller

Para PowerPC podría verse así (también sin probar):

myAsmFunc1:
   nop
   nop
   nop   # ...exactly enough NOPs to fill one "way" of the cache
   .     # minus 4 bytes for the "blr" instruction.  Note that
   .     # on PPC, all instructions (including NOP) are 4 bytes.
   .
   nop
   blr   # return to the caller

En ambos casos, los prototipos C ++ y C para llamar a estas funciones serían:

extern "C" void myAsmFunc1();    // Prototype for calling from C++ code
void myAsmFunc1(void);           /* Prototype for calling from C code */

Dependiendo de su compilador, es posible que necesite un guión bajo delante del nombre de la función en el propio código de ensamblaje (pero no en su prototipo de función C ++ / C).

Answer 5

Una cadena de if else en condiciones impredecibles (por ejemplo, datos de entrada o datos generados aleatoriamente) con cantidad de instrucciones tanto en el caso if como en el caso else, cuyo tamaño es mayor que una línea de caché.