Arquitectura de caché.
Dependiendo de la forma en que la línea de caché y el área de memoria principal coincidan, se distinguen tres arquitecturas de caché: una caché de mapeo directo, una caché totalmente asociativa y una caché parcial o asociativa por conjuntos.
Caché mapeado directo.
En una caché de mapeo directo, la dirección de la memoria a la que se accede determina de manera única la línea de caché en la que se puede ubicar el bloque requerido. Explicaremos el principio de funcionamiento de dicho caché usando el ejemplo de un caché no sectorizado de 256 KB con un tamaño de línea de 32 bytes y una memoria principal en caché de 64 MB, un caché de placa base típico para Pentium. La estructura de la memoria caché en dicho sistema se ilustra en la Fig. 1. La memoria principal almacenada en caché está paginada condicionalmente (en este caso, 256 KB), cuyo tamaño es el mismo que el tamaño del caché (256 KB). La memoria caché (y condicionalmente, las páginas de la memoria principal) se divide en líneas (256 KB / 32 bytes - 8 K líneas). La arquitectura de mapeo directo implica que cada línea de caché puede mapear desde cualquier página de memoria en caché solo la línea correspondiente. Dado que la memoria principal es mucho más grande que la caché, cada línea de caché puede ser reclamada por muchos bloques de memoria con la misma parte baja de la dirección, que se denomina desplazamiento dentro de la página (0 - juego, 1 juego, 2 juegos ... N-conjunto de bloques de 32 bytes). Una línea en un momento determinado puede contener una copia de solo uno de estos bloques. El número de línea es la dirección de la línea en la memoria caché, y la etiqueta contiene información sobre qué bloque ocupa esta línea (la etiqueta es la parte superior de la dirección establecida por el procesador al acceder a la memoria, o en otras palabras, la número de página). La memoria de etiquetas debe tener un número de celdas igual al número de líneas de caché, y su ancho debe ser suficiente para acomodar los bits de orden superior de la dirección de memoria caché que no están en el bus de direcciones de caché. Además de la parte de dirección de la etiqueta, cada línea de caché está asociada con bits de signos de validez y modificación de datos. Al comienzo de cada acceso a la RAM, el controlador de memoria caché, en primer lugar, lee la celda de memoria de etiqueta con la dirección de línea determinada por los bits A17-A5, compara el contenido de esta línea de memoria de etiqueta con los bits A25-A18 de la dirección de memoria establecida por el procesador, y analiza el signo de la realidad.
Arroz. 1. Caché con mapeo directo.
Este análisis se realiza en un bucle de seguimiento especial, a veces llamado bucle de consulta. Si, como resultado del análisis, resulta que el bloque requerido no está en el caché, se genera (o continúa) un ciclo de acceso a la memoria principal (falta de caché). Si acierta, la caché atiende la solicitud. En caso de error después de leer de la memoria principal por parte del receptor de información, los nuevos datos se colocan en la línea de caché (si está limpio) , y los bits superiores de la dirección se colocan en su etiqueta y se establece el signo de validez de los datos. Independientemente de la cantidad de datos solicitados, toda la línea se reescribe en el caché desde la memoria principal (ya que el signo de validez se aplica a todos sus bytes). Si el controlador de caché implementa la lectura anticipada, en los ciclos de bus libres subsiguientes, la siguiente línea también se actualiza (si estaba limpia). ). La lectura "en reserva" permite, si es necesario, realizar un ciclo de lectura por lotes desde la memoria caché a través del límite de la línea. Tal caché tiene la implementación de hardware más simple y se usa en el caché secundario de la mayoría de las placas base. Sin embargo, tiene un grave defecto. Si, durante la ejecución del programa, el procesador accede alternativamente a la misma dirección de línea, pero con números de etiqueta diferentes o que cambian cíclicamente, los errores de caché se registrarán constantemente y la memoria caché, en lugar de acelerar, ralentizará el intercambio con memoria. El cambio de página en los sistemas operativos (SO) multitarea también reduce la cantidad de visitas a la memoria caché, lo que afecta el rendimiento del sistema. Aumentar el tamaño de la memoria caché mientras se mantiene la arquitectura de mapeo directo no tendrá un efecto muy significativo, ya que diferentes tareas reclamarán las mismas líneas de memoria caché. Sin aumentar el tamaño de la memoria caché, es posible aumentar la eficiencia del almacenamiento en memoria caché cambiando su estructura, que se analizará a continuación.
A veces, una memoria caché asignada hacia adelante utiliza el concepto de conjunto en lugar de una fila en una memoria caché asignada hacia adelante sectorizada, y el sector se denomina fila. Un conjunto (así como una línea de caché que no sea de sector) tiene información de etiqueta asociada con todos los elementos del conjunto (líneas o sectores). Además, cada elemento del conjunto (fila o sector) tiene su propio bit de validez (Fig. 2).
Arroz. 2. Caché mapeado hacia adelante sectorizado
Caché de tipo asociativo (parcialmente asociativo).
La arquitectura asociativa de conjuntos de la caché (Fig. 3) permite que cada bloque de memoria almacenada en caché reclame una de varias líneas de caché combinadas en un conjunto. En esta arquitectura, hay, por así decirlo, varios canales de mapeo directo paralelos y coordinados, donde el controlador de caché tiene que decidir en cuál de las filas del conjunto colocar el siguiente bloque de datos. Por ejemplo, en el caso más simple, cada bloque de memoria puede caber en una de las cuatro líneas establecidas (caché asociativo de conjuntos de cuatro canales). El número de conjunto en el que se puede mapear el bloque de datos solicitado se identifica de manera única por la parte central de la dirección (como el número de línea en el caché de mapeo directo). La línea de conjunto que se asigna al bloque requerido está determinada por una comparación de etiquetas (como en un caché asociativo) realizada en paralelo para todas las líneas de memoria de etiquetas del conjunto dado (canales de caché). Además, cada conjunto debe tener un indicador asociado que defina la cadena del conjunto que se reemplazará con un nuevo bloque de datos en caso de que se pierda la memoria caché (la flecha apunta en su dirección en la figura).
Arroz. 3. Caché asociativo de conjuntos de cuatro canales
La fecha candidata para el reemplazo suele ser la cadena a la que no se ha accedido durante más tiempo (algoritmo LRU - Usado menos recientemente). Con una cantidad relativamente grande de canales (líneas en el conjunto), se recurre a cierta simplificación: el algoritmo Pseudo-LRU para cuatro líneas permite tomar decisiones utilizando solo 3 bits.
También es posible utilizar un algoritmo de reemplazo FIFO (primero en entrar, primero en salir) o incluso un reemplazo aleatorio, que es más simple pero menos eficiente. La arquitectura asociativa por conjuntos se usa ampliamente para la memoria caché principal de los procesadores modernos.
Caché asociativo.
A diferencia de las anteriores, para una caché totalmente asociativa, cualquiera de sus líneas puede mapear cualquier bloque de memoria, lo que aumenta significativamente la eficiencia de usar una cantidad limitada de caché. Sin embargo, todos los bits
Arroz. 4. Memoria caché totalmente asociativa.
Las direcciones del bloque almacenado en caché, menos los bits que determinan la posición (desplazamiento) de los datos en la línea, se almacenan en la memoria de etiquetas. En tal arquitectura (Fig. 4), para determinar la presencia de los datos solicitados en la memoria caché, una comparación con la parte superior de la dirección de la etiqueta de todas las líneas de memoria de la etiqueta, y no solo una o varias, como en el mapeo directo o arquitectura asociativa de conjuntos, es necesaria. Se elimina la enumeración secuencial de celdas de memoria de etiquetas. (esto lleva demasiado tiempo), por lo que queda una comparación paralela de las etiquetas de todas las celdas, y esta es una tarea de hardware compleja que es aceptable solo para pequeñas cantidades de caché principal (procesador M2 Cyrix).
Los desarrolladores de la memoria caché se han encontrado con el problema de que cualquier celda de la enorme memoria principal puede estar potencialmente en la memoria caché. Si el conjunto de datos de trabajo utilizado en el programa es lo suficientemente grande, esto significa que muchos fragmentos de la memoria principal competirán por cada lugar en la memoria caché. Como se informó anteriormente, no es raro que la relación entre la memoria caché y la memoria principal sea de 1 a 1000.
3.3.1 Asociatividad
Sería posible implementar una memoria caché en la que cada línea de caché pueda almacenar una copia de cualquier ubicación de memoria. Se llama caché totalmente asociativa (caché totalmente asociativa). Para acceder a una línea de caché, el núcleo del procesador tendría que comparar las etiquetas de cada línea de caché con la etiqueta de la dirección solicitada. La etiqueta deberá almacenar la dirección completa, que no estará especificada por el desplazamiento en la línea de caché (lo que significa que el valor de S que se muestra en la figura de la sección 3.2 será cero).
Hay cachés que se implementan de esta manera, pero considerando el tamaño del caché L2 actualmente en uso, no es práctico. Tenga en cuenta que una caché de 4 MB con 64B de líneas de caché debería tener 65.536 entradas. Para obtener un rendimiento adecuado, la lógica de la memoria caché debe poder, en unos pocos ciclos, seleccionar de todas estas entradas la que coincida con la etiqueta dada. El costo de implementar tal esquema sería enorme.
Figura 3.5: Representación esquemática de una memoria caché totalmente asociativa
Cada línea de caché requiere que el comparador realice una comparación de etiquetas grande (tenga en cuenta que S es cero). La letra junto a cada conexión indica el ancho de la conexión en bits. Si no se especifica nada, entonces el ancho de la conexión es de un bit. Cada comparador debe comparar dos valores, cada uno de los cuales tiene T bits de ancho. Luego, según el resultado, el contenido de la línea de caché correspondiente debe seleccionarse y estar disponible. Para hacer esto, debe combinar tantos conjuntos de líneas de datos O como segmentos de caché (contenedores de caché) haya. El número de transistores necesarios para implementar un comparador será grande, en parte porque el comparador debe ser muy rápido. No se puede utilizar un comparador iterativo. La única forma de ahorrar en el número de comparadores es reducir su número mediante la comparación iterativa de etiquetas. Esto no funciona por la misma razón que los comparadores iterativos: llevaría demasiado tiempo.
Un caché totalmente asociativo es práctico para un caché pequeño (por ejemplo, el caché TLB en algunos procesadores Intel es totalmente asociativo), pero el caché debe ser pequeño, realmente pequeño. Hablamos de un máximo de varias decenas de registros.
Las cachés L1i, L1d y de nivel superior requieren un enfoque diferente. Todo lo que puedes hacer es limitar tu búsqueda. En el caso más extremo, cada etiqueta se asigna exactamente a una entrada de caché. El cálculo es sencillo: para una caché de 4MB/64B con 65.536 entradas, podemos acceder directamente a cada entrada y utilizar los bits 6 a 21 de la dirección (16 bits) para ello. Los 6 bits inferiores son el índice de línea de caché.
Figura 3.6: Representación esquemática de un caché de mapeo directo
Como se puede ver en la Figura 3.6, la implementación de tal caché mapeado directo (caché de asignación directa) puede ser rápido y fácil. Requiere solo un comparador, un multiplexor (dos se muestran en este diagrama porque la etiqueta y los datos están separados, pero esto no es un requisito de diseño estricto) y alguna lógica para seleccionar contenido que contenga líneas de caché válidas. El comparador es complejo por los requisitos en cuanto a velocidad, pero ahora solo hay uno; como resultado, se puede gastar más esfuerzo para hacerlo más rápido. La verdadera complejidad de este enfoque radica en los multiplexores. El número de transistores en un multiplexor simple crece en O(log N), donde N es el número de líneas de caché. Esto es aceptable, pero puede resultar en un multiplexor lento, en cuyo caso la velocidad se puede aumentar gastando dinero en transistores en los multiplexores y paralelizando parte del trabajo para aumentar la velocidad. El número total de transistores crecerá lentamente en comparación con el tamaño de la memoria caché, lo que hace que esta sea una solución muy atractiva. Pero este enfoque tiene un inconveniente: solo funciona si las direcciones utilizadas en el programa están distribuidas uniformemente en relación con los bits utilizados para el mapeo directo. Si este no es el caso, y generalmente lo es, algunas entradas de caché se usan activamente y, por lo tanto, se desasignan repetidamente, mientras que otras apenas se usan o permanecen vacías.
Figura 3.7: Representación esquemática de una caché con asociatividad múltiple
Este problema se puede resolver utilizando la memoria caché con asociatividad múltiple (conjunto asociado). Las cachés de asociatividad múltiple combinan características de cachés totalmente asociativas y cachés de mapeo directo, evitando en gran medida las desventajas de estas soluciones. La Figura 3.7 muestra un diseño de caché con asociatividad múltiple. La memoria para etiquetas y para datos se divide en conjuntos, cuya selección se realiza de acuerdo con la dirección. Esto es similar a una memoria caché asignada directamente. Pero en lugar de usar un elemento separado para cada valor en un conjunto, el mismo conjunto se usa para almacenar en caché una pequeña cantidad de valores. Las etiquetas de todos los elementos del conjunto se comparan en paralelo, lo que es similar al funcionamiento de una memoria caché totalmente asociativa.
El resultado es una memoria caché que es razonablemente robusta contra errores debido a una selección incorrecta o intencional de direcciones con los mismos números establecidos al mismo tiempo, y el tamaño de la memoria caché no está limitado por la cantidad de comparadores que pueden operar en paralelo. Si aumenta el caché (ver figura), solo aumenta el número de columnas, no el número de filas. El número de líneas aumenta solo si aumenta la asociatividad del caché. En la actualidad, los procesadores de caché L2 utilizan niveles de asociatividad de hasta 16 y superiores. La memoria caché L1 normalmente se establece en el nivel 8.
Tabla 3.1: Efectos del tamaño de caché, asociatividad y tamaño de línea de caché
| Tamaño memoria caché L2 |
Asociatividad | |||||||
|---|---|---|---|---|---|---|---|---|
| visualización directa | 2 | 4 | 8 | |||||
| CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | CL=32 | CL=64 | |
| 512k | 27 794 595 | 20 422 527 | 25 222 611 | 18 303 581 | 24 096 510 | 17 356 121 | 23 666 929 | 17 029 334 |
| 1M | 19 007 315 | 13 903 854 | 16 566 738 | 12 127 174 | 15 537 500 | 11 436 705 | 15 162 895 | 11 233 896 |
| 2M | 12 230 962 | 8 801 403 | 9 081 881 | 6 491 011 | 7 878 601 | 5 675 181 | 7 391 389 | 5 382 064 |
| 4M | 7 749 986 | 5 427 836 | 4 736 187 | 3 159 507 | 3 788 122 | 2 418 898 | 3 430 713 | 2 125 103 |
| 8M | 4 731 904 | 3 209 693 | 2 690 498 | 1 602 957 | 2 207 655 | 1 228 190 | 2 111 075 | 1 155 847 |
| 16M | 2 620 587 | 1 528 592 | 1 958 293 | 1 089 580 | 1 704 878 | 883 530 | 1 671 541 | 862 324 |
Si tenemos un caché de 4MB/64B y una asociatividad de 8 canales, entonces tendremos 8192 conjuntos en el caché y solo se requerirán 13 bits de etiqueta para abordar los conjuntos de caché. Para determinar cuál de las entradas (si las hay) en el conjunto de caché contiene la línea de caché direccionada, se deben comparar 8 etiquetas. Esto se puede hacer en muy poco tiempo. Como puede ver en la práctica, esto tiene sentido.
La Tabla 3.1 muestra el número de errores de caché L2 para algún programa (en este caso, el compilador gcc, que los desarrolladores del kernel de Linux consideran el punto de referencia más importante) al cambiar el tamaño del caché, el tamaño de la línea del caché y la asociatividad múltiple del valor. En la Sección 7.2, presentaremos la herramienta de simulación de caché necesaria para esta prueba.
Simplemente, si aún no es obvio, la relación de todos estos valores es que el tamaño del caché es
tamaño de línea de caché x asociatividad x número de conjuntos
La asignación de dirección a caché se calcula como
O = tamaño de línea de caché log2
S = log2 del número de conjuntos
según la figura del apartado 3.2.
Fig.3.8: Tamaño de caché y nivel de asociatividad (CL=32)
Arroz. 3.8 hace que los datos de la tabla sean más comprensibles. La figura muestra datos para una línea de caché de un tamaño fijo de 32 bytes. Al observar los números para un tamaño de caché dado, puede ver que la asociatividad realmente puede ayudar a reducir las pérdidas de caché de manera significativa. Para una caché de 8 MB, pasar de la asociatividad de asignación directa a la de 2 vías ahorra casi un 44 % de caché. Si se utiliza una memoria caché de asociatividad múltiple, el procesador puede almacenar un conjunto de trabajo más grande en la memoria caché que en el caso de una memoria caché asignada directamente.
A veces puede leer en la literatura que la introducción de la asociatividad tiene el mismo efecto que duplicar el tamaño de la memoria caché. Esto, como se ve en el caso de pasar de un caché de 4 MB a un caché de 8 MB, es cierto en algunos casos extremos. Pero esto, por supuesto, no es cierto con un aumento posterior de la asociatividad. Como puede verse a partir de los datos, un aumento posterior en la asociatividad da una ganancia significativamente menor. Sin embargo, no debemos ignorar por completo este hecho. En nuestro programa de ejemplo, el uso máximo de memoria es de 5,6 MB. Entonces, con un tamaño de caché de 8 MB, los mismos conjuntos de caché se usarán varias veces (más de dos veces). A medida que aumenta el conjunto de trabajo, el ahorro puede aumentar, ya que, como vemos, con tamaños de caché más pequeños, la ventaja de usar la asociatividad será mayor.
En general, aumentar la asociatividad de la memoria caché por encima de 8 parece tener poco efecto en un solo subproceso de carga de trabajo. Con la llegada de los procesadores multinúcleo que utilizan una caché L2 compartida, la situación está cambiando. Ahora básicamente tiene dos programas accediendo al mismo caché, lo que en la práctica debería duplicar el efecto del uso de la asociatividad (o cuadruplicar para procesadores de cuatro núcleos). Por lo tanto, se puede esperar que a medida que aumenta el número de núcleos, la asociatividad de la caché compartida debería aumentar. A medida que esto se vuelve imposible (la asociatividad de 16 canales ya es difícil de implementar), los diseñadores de procesadores comenzarán a usar un caché L3 común y más allá, mientras que el caché L2 será potencialmente compartido por algún subconjunto de núcleos.
Otro efecto que podemos ver en la Figura 3.8 es cómo aumentar el tamaño de la memoria caché mejora el rendimiento. Estos datos no se pueden interpretar sin conocer el tamaño del conjunto de trabajo. Obviamente, una memoria caché tan grande como la memoria principal debería generar mejores resultados que una memoria caché más pequeña, por lo que, en general, no hay límite para aumentar el tamaño de la memoria caché y obtener beneficios medibles.
Como se mencionó anteriormente, el tamaño máximo del conjunto de trabajo es de 5,6 MB. Este valor no nos permite calcular la cantidad de memoria que traería el máximo beneficio, pero nos permite estimar este tamaño. El problema es que toda la memoria no se usa continuamente y, por lo tanto, tenemos conflictos incluso con 16 MB de caché y 5,6 MB de trabajo (recuerde la ventaja del caché asociativo bidireccional de 16 MB sobre la versión de visualización directa). Pero es seguro decir que bajo tal carga, la ventaja de un caché de 32 MB no será significativa. Sin embargo, ¿quién dijo que el conjunto de trabajo debe permanecer sin cambios? A medida que las cargas de trabajo crecen con el tiempo, también debería hacerlo el tamaño de la memoria caché. Al comprar máquinas y decidir cuánto caché pagar, vale la pena medir el tamaño del conjunto de trabajo. Por qué esto es importante se puede ver en la Fig. 3.10.
Figura 3.9: Diseño de memoria utilizado en las pruebas
Se ejecutan dos tipos de pruebas. En la primera prueba, los elementos se procesan secuencialmente. El programa de prueba usa el puntero n , pero los elementos de la matriz están vinculados entre sí de modo que se recorren en el orden en que están en la memoria. Esta opción se muestra en la parte inferior de la Figura 3.9. Hay una referencia posterior que proviene del último elemento. En la segunda prueba (parte superior de la figura), los elementos del arreglo se recorren en orden aleatorio. En ambos casos, los elementos de la matriz forman una lista cíclica con enlaces simples.
Las opciones conocidas para asignar la memoria principal a la memoria caché se pueden reducir a tres tipos: directo, totalmente asociativo Y parcialmente asociativo.
En pantalla directa dirección de línea i caché a la que se puede asignar el bloque j del OP, está determinado únicamente por la expresión: i = j modificación metro, Dónde metro es el número total de líneas en el caché, es decir, por línea de caché con el número i mostrado cada metro-ésimo bloque del OP, si la cuenta regresiva comienza desde el bloque, cuyo número es igual a i.
El mapeo directo es un método de mapeo simple y económico de implementar. Su principal inconveniente es la asignación rígida de una línea en el caché a ciertos bloques OP. Por lo tanto, si el programa accede alternativamente a palabras de dos bloques diferentes asignados a la misma línea de caché, esta línea se actualizará constantemente y la probabilidad de acierto será baja.
Visualización totalmente asociativa supera la desventaja del directo al permitir que cualquier bloque de RAM se cargue en cualquier línea de caché. El mapeo asociativo brinda flexibilidad para elegir una fila para un bloque recién grabado. La desventaja fundamental de este método es la necesidad de realizar una verificación de todas las líneas de caché.
El mapeo parcialmente asociativo es uno de los posibles compromisos, combinando las ventajas de los métodos de mapeo directo y asociativo y, hasta cierto punto, libre de sus deficiencias. La memoria caché se divide en v subconjuntos (conjuntos), cada uno de los cuales contiene k filas (es costumbre decir que un conjunto tiene k entradas). La dependencia entre el conjunto y los bloques OP es la misma que en el mapeo directo: a las líneas incluidas en el conjunto i, solo se pueden mostrar bloques de memoria principal bien definidos, de acuerdo con la relación i = j modificación v, Dónde j– dirección del bloque OP. Al mismo tiempo, la ubicación de los bloques a lo largo de las líneas del módulo es arbitraria y se utiliza el principio asociativo para buscar la línea deseada dentro del módulo.
En casos extremos, cuando v = metro, k= 1, el mapeo asociativo múltiple se reduce a uno directo, y cuando v = 1,k = metro- al asociativo.
Dependiendo del método para determinar la correspondencia mutua de la línea de caché y el bloque de memoria principal, se distinguen tres arquitecturas de caché:
Caché totalmente asociativo
Caché de mapeo directo (caché de mapeo directo);
conjunto- (parcial o múltiple-) caché asociativo (conjunto-caché asociativo).
EN caché totalmente asociativa cualquier bloque de memoria principal puede residir en cualquier línea de caché, o cualquier línea de caché puede asignarse a cualquier bloque de memoria principal. En este caso, los bits superiores de la dirección de datos en caché, menos los bits que determinan la posición (desplazamiento) de los datos en la línea (bloque), se ingresan en el catálogo y se usan como etiqueta. En tal arquitectura, para determinar si hay datos en el caché en una dirección particular, es necesario comparar los bits superiores de esta dirección con las etiquetas de todas las líneas en el directorio del caché. Si dicha comparación se realiza secuencialmente, llevará demasiado tiempo y la memoria caché perderá sentido debido al bajo rendimiento. Por lo tanto, dicha comparación debe realizarse en paralelo para todas las etiquetas. Este requisito se cumple mejor con la memoria asociativa, es decir, la etiqueta debe almacenarse en la memoria asociativa de etiquetas de la memoria caché.
Tal organización de la memoria caché es un problema de hardware complejo que puede resolverse solo para pequeños volúmenes, es decir, una caché totalmente asociativa, debido a su complejidad, no puede tener un gran volumen y se usa, por regla general, con fines auxiliares. Por ejemplo, en los procesadores Intel, se utiliza una memoria caché totalmente asociativa en el bloque de paginación para crear búfer de traducción de asociación TLB (Búfer de búsqueda de traducción), diseñado para acelerar el acceso a páginas muy utilizadas.
La arquitectura opuesta es caché de mapeo directo. En un caché de mapeo directo, un bloque particular de memoria principal solo puede residir en una línea de caché bien definida. La memoria principal se divide condicionalmente en páginas, cuyo tamaño coincide con el tamaño de la memoria caché. La arquitectura de mapeo directo significa que cada línea de caché solo puede mapear el bloque correspondiente de cualquier página en la memoria principal. Los bloques con el mismo número de todas las páginas caen en la misma línea de caché. Por lo tanto, cada línea de caché es reclamada por muchos bloques de memoria principal con el mismo número dentro de una página. Una línea a la vez solo puede contener una copia de uno de estos bloques. La etiqueta es el número de la página cuyo bloque ocupa la línea de caché correspondiente. En tal arquitectura, para determinar si hay datos en el caché con una dirección específica, es necesario comparar el número de la página a la que pertenece esta dirección con la etiqueta de la línea en el directorio de la memoria caché que corresponde al bloque. en la página que contiene la dirección dada, es decir, solo necesita realizar una comparación.
La memoria caché asignada directamente tiene la implementación de hardware más simple, ya que la memoria caché tiene la estructura de una memoria directamente direccionable convencional y solo se necesita un comparador. Por lo tanto, dicho caché puede ser grande.
El intermedio entre una memoria caché totalmente asociativa y una memoria caché de asignación directa es caché asociativa de conjunto, que se utiliza principalmente en microprocesadores modernos. En una caché asociativa de conjuntos, a diferencia de una caché de mapeo directo, cada bloque de memoria principal puede reclamar una de varias líneas de caché combinadas en un conjunto. Esto aumenta la probabilidad de una conversión exitosa. De manera simplista, podemos suponer que una memoria caché asociativa de conjuntos son varios canales de mapeo directo paralelos y coordinados en los que las filas con los mismos números forman un conjunto correspondiente. La cadena de marcación que representa el bloque requerido de la memoria principal está determinada por una comparación de etiquetas (como en un caché asociativo) realizada en paralelo para todos los canales de caché. Cada conjunto tiene un indicador asociado que especifica la fila del conjunto que se reemplazará por un nuevo bloque en caso de que se pierda la memoria caché. El candidato para el reemplazo suele ser la cadena a la que no se ha accedido durante más tiempo (algoritmo LRU - Usado menos recientemente). También es posible usar un FIFO o incluso un algoritmo de reemplazo aleatorio, que es más simple pero menos eficiente.
¿Por qué observamos un aumento constante en el rendimiento de los programas de un solo subproceso? Por el momento, nos encontramos en esa etapa de desarrollo de las tecnologías de microprocesadores, cuando el aumento de la velocidad de las aplicaciones de un solo hilo depende solo de la memoria. La cantidad de núcleos está creciendo, pero la frecuencia se fija dentro de los 4 GHz y no aumenta el rendimiento.
La velocidad y la frecuencia de la operación de la memoria es la razón principal por la que obtenemos "nuestro pedazo de pastel gratis" (enlace). Por eso es importante utilizar la memoria de la forma más eficiente posible, y más aún tan rápido como la memoria caché. Para optimizar el programa para una computadora específica, es útil conocer las características de la memoria caché del procesador: el número de niveles, tamaño, longitud de línea. Esto es especialmente importante en el código de alto rendimiento: núcleos del sistema, bibliotecas matemáticas.
¿Cómo determinar las características del caché automático? (por supuesto, cpuinfo no se considera analizado, aunque solo sea porque al final nos gustaría obtener un algoritmo que pueda implementarse fácilmente en otros sistemas operativos. Conveniente, ¿no?) Eso es lo que haremos ahora .
un poco de teoria
Actualmente existen tres tipos de cachés y son ampliamente utilizados: caché de asignación directa, caché asociativa y caché asociativa múltiple.Caché de mapeo directo
- una línea de RAM determinada se puede asignar a una sola línea de caché, pero se pueden asignar muchas líneas de RAM posibles a cada línea de caché.Caché asociativo (caché totalmente asociativo)
- cualquier línea de RAM se puede asignar a cualquier línea de caché.Caché asociativo múltiple
- la memoria caché se divide en varios "bancos", cada uno de los cuales funciona como una caché de asignación directa, por lo que una línea de RAM no se puede asignar a una sola entrada de caché posible (como sería en el caso de la asignación directa), sino a uno de varios bancos; La selección de banco se basa en la LRU u otro mecanismo para cada línea almacenada en caché.LRU: el desplazamiento de la línea "largamente sin usar", la memoria caché.
Idea
Para determinar la cantidad de niveles de caché, debe considerar el orden de los accesos a la memoria, en los que la transición será claramente visible. Los diferentes niveles de caché difieren principalmente en la velocidad de respuesta de la memoria. En el caso de una "pérdida de caché" para el caché L1, los datos se buscarán en los siguientes niveles de memoria, y si el tamaño de los datos es mayor que L1 y menor que L2, entonces la velocidad de respuesta de la memoria será la velocidad de respuesta L2. La afirmación anterior también es cierta en el caso general.Está claro que debemos elegir una prueba en la que veamos claramente errores de caché y probarla en varios tamaños de datos.
Conociendo la lógica de los cachés asociativos múltiples que funcionan de acuerdo con el algoritmo LRU, no es difícil encontrar un algoritmo en el que el caché "caiga", nada complicado: pasar por la línea. El criterio de eficiencia es el tiempo de un acceso a la memoria. Naturalmente, necesita acceder secuencialmente a todos los elementos de la cadena, repitiendo muchas veces para promediar el resultado. Por ejemplo, puede haber casos en los que la línea quepa en el caché, pero para el primer paso cargamos la línea desde la RAM y, por lo tanto, obtenemos un tiempo completamente inadecuado.
Me gustaría ver algo como pasos, pasando a lo largo de líneas de diferentes longitudes. Para determinar la naturaleza de los pasos, considere un ejemplo de un paso de línea para un caché directo y asociativo, el caso de un caché asociativo múltiple será un promedio entre un caché de mapeo directo y un caché asociativo.
Caché asociativo
Tan pronto como el tamaño de los datos supere el tamaño de la memoria caché,
un caché totalmente asociativo "falla" en cada acceso a la memoria.
Caché directo
Considere diferentes tamaños de fila. - muestra el número máximo de fallos que gastará el procesador para acceder a los elementos de la matriz durante el próximo paso por la línea.
Como puede ver, el tiempo de acceso a la memoria no aumenta drásticamente, pero sí aumenta la cantidad de datos. Tan pronto como el tamaño de los datos supere el tamaño de la memoria caché, habrá fallas en cada acceso a la memoria.
Por lo tanto, para una caché asociativa, el paso será vertical, mientras que para una caché directa, aumentará gradualmente hasta el doble del tamaño de la caché. Una memoria caché multiasociativa sería un caso promedio, un "golpe", aunque solo sea porque el tiempo de acceso no podría ser mejor que uno directo.
Si hablamos de memoria, entonces la más rápida es la caché, seguida de la operativa, la más lenta es la de intercambio, de eso no hablaremos en el futuro. A su vez, diferentes niveles de caché (por regla general, hoy en día los procesadores tienen 2 o 3 niveles de caché) tienen diferentes velocidades de respuesta de la memoria: cuanto mayor sea el nivel, más lenta será la velocidad de respuesta. Y por tanto, si la línea se sitúa en el primer nivel de la caché (que, por cierto, es completamente asociativa), el tiempo de respuesta será menor que el de una línea significativamente mayor que el tamaño de la caché del primer nivel. . Por lo tanto, habrá varias mesetas en el gráfico del tiempo de respuesta de la memoria frente a los tamaños de línea: una meseta * de la respuesta de la memoria y mesetas causadas por varios niveles de caché.
*Función meseta - (i:x, f(xi) - f(xi+1)< eps: eps → 0 }
Empecemos a implementar
Usaremos C (ANSI C99) para la implementación.El código fue escrito rápidamente, el paso habitual a través de líneas de diferente longitud, menos de 10mb, que se realiza repetidamente. (Daremos pequeños fragmentos del programa que llevan una carga semántica).
Para (i = 0; yo< 16; i++) { for (j = 0; j < L_STR; j++) A[j]++; }
Miramos el gráfico y vemos un gran paso. Pero en teoría, todo sale bien. Se hizo necesario entender: ¿por qué sucede esto? ¿Y como arreglarlo?
Obviamente, esto puede suceder por dos razones: o el procesador no tiene una memoria caché, o el procesador es tan bueno para adivinar los accesos a la memoria. Dado que la primera opción se acerca más a la ficción, el motivo de todo es una buena predicción de aciertos.
El hecho es que hoy en día lejos de los mejores procesadores, además del principio de localidad espacial, también predicen una progresión aritmética en el orden de acceso a la memoria. Por lo tanto, los accesos a la memoria deben ser aleatorios.
La longitud de la matriz aleatoria debe ser comparable a la longitud de la cadena principal para eliminar la gran granularidad de los accesos, así como la longitud de la matriz no debe ser una potencia de dos, debido a esto, "superposiciones ” ocurrió, lo que puede resultar en valores atípicos. Es mejor establecer la granularidad constante, incluso si la granularidad es un número primo, entonces se pueden evitar los efectos de superposición. Y la longitud de la matriz aleatoria es una función de la longitud de la cadena.
para (i = 0; yo< j; i++) {
for (m = 0; m < L; m++) {
for (x = 0; x < M; x++){
v = A[ random[x] + m ];
}
}
}
Después de eso, sorprendimos a la tan esperada "imagen", de la que hablamos al principio.
El programa se divide en 2 partes: prueba y procesamiento de datos. Escriba un script en 3 líneas para ejecutarlo o ejecútelo 2 veces a mano, decida usted mismo.
Tamaño de la lista de Linux.
#incluir
Tamaño de listado de Windows.c
#incluir
En general, creo que todo está claro, pero me gustaría precisar algunos puntos.
La matriz A se declara como volátil: esta directiva nos garantiza que siempre habrá llamadas a la matriz A, es decir, no serán "cortadas" ni por el optimizador ni por el compilador. También vale la pena mencionar que toda la carga computacional se realiza antes de la medición del tiempo, lo que nos permite reducir la influencia de fondo.
El archivo se traduce a ensamblador en Ubuntu 12.04 y compilador gcc 4.6: se conservan los ciclos.
Procesamiento de datos
Es lógico utilizar derivados para el procesamiento de datos. Y a pesar de que a medida que aumenta el orden de diferenciación aumenta el ruido, se utilizará la segunda derivada y sus propiedades. No importa cuán ruidosa sea la segunda derivada, solo nos interesa el signo de la segunda derivada.Encontramos todos los puntos en los que la segunda derivada es mayor que cero (con algún error porque la segunda derivada, además de ser considerada numéricamente, es muy ruidosa). Establecemos la función de la dependencia del signo de la segunda derivada de la función en el tamaño del caché. La función toma el valor 1 en los puntos donde el signo de la segunda derivada es mayor que cero, y cero si el signo de la segunda derivada es menor o igual a cero.
Los puntos de despegue son el comienzo de cada paso. Además, antes de procesar los datos, es necesario eliminar los valores atípicos individuales que no cambian la carga semántica de los datos, pero crean un ruido notable.
Listado del archivo data_pr.c
#incluir
Pruebas
CPU/OS/versión del kernel/compilador/claves de compilación: se especificarán para cada prueba.
Intel Pentium CPU P6100 a 2,00 GHz / Ubuntu 12.04 / 3.2.0-27-genérico / gcc -Wall -O3 size.c -lrtL1 = 0,05 MB
L2 = 0,2 MB
L3 = 2,7 MB- No daré todas las buenas pruebas, hablemos del "Rastrillo"
Hablemos del "rastrillo"
El rake se detectó mientras se procesaban los datos en el procesador del servidor Intel Xeon 2.4/L2 = 512 kb/Windows Server 2008El problema radica en el pequeño número de puntos que caen dentro del intervalo de alcanzar una meseta, por lo que el salto en la segunda derivada es imperceptible y se toma como ruido.
Puede resolver este problema utilizando el método de mínimos cuadrados o realizar pruebas en el curso de la determinación de las zonas de meseta.
Me gustaría escuchar sus sugerencias sobre cómo resolver este problema.
Bibliografía
- Makarov A. V. Arquitectura de computadores y programación de bajo nivel.
- Ulrich Drupper
Caché con mapeo directo (ubicación);
caché totalmente asociativa;
· caché asociativa múltiple o parcialmente asociativa.
Caché asignada directamente(alojamiento) es lo más
un tipo de búfer simple. Una dirección de memoria identifica de forma única una cadena
caché en el que se colocará el bloque de información. Al mismo tiempo, pre-
Se supone que la RAM está dividida en bloques y cada uno
qué bloque en el búfer recibe solo una línea. Este es un método de visualización simple y económico de implementar. Su principal inconveniente es la asignación rígida de una línea en el caché a ciertos bloques OP. Por lo tanto, si un programa accede alternativamente a palabras de dos bloques diferentes asignados a la misma línea de caché, esa línea se actualizará constantemente y la probabilidad de acierto será baja.
Caché totalmente asociativa supera la desventaja del directo al permitir que cualquier bloque de RAM se cargue en cualquier línea de caché. La lógica de control distingue dos campos en la dirección del UE: el campo de etiqueta y el campo de palabra. El campo de la etiqueta coincide con la dirección del bloque OP. Para comprobar si hay una copia del bloque en la memoria caché, la lógica de control de la memoria caché debe comprobar simultáneamente las etiquetas de todas las filas en busca de una coincidencia con el campo de la etiqueta de dirección. El mapeo asociativo brinda flexibilidad para elegir una fila para un bloque recién grabado. La desventaja fundamental de este método es la necesidad de utilizar una memoria asociativa costosa.
Tipo asociativo múltiple o tipo de visualización parcialmente asociativo − este es uno de los posibles compromisos, combinando las ventajas de los métodos directos y asociativos. La memoria caché (tanto etiquetas como datos) se divide en varios módulos. La dependencia entre el módulo y los bloques OP es tan rígida como en el mapeo directo. Pero la ubicación de los bloques a lo largo de las líneas del módulo es arbitraria y el principio asociativo se usa para buscar la línea deseada dentro del módulo. Este método de visualización es el más utilizado en los microprocesadores modernos.
Mapeo de sectores OP en el caché.
Este tipo de visualización se utiliza en todas las computadoras modernas y consiste en que todo el OP se divide en sectores que consisten en un número fijo de bloques consecutivos. La memoria caché también se divide en sectores que contienen el mismo número de líneas. La ubicación de los bloques en el sector OP y el sector caché es completamente la misma. La asignación de sector a caché se realiza de forma asociativa, por lo que cualquier sector de la RAM se puede colocar en cualquier sector de la memoria caché. Por lo tanto, en el proceso de operación, la ALU se dirige al OP en busca del siguiente comando, como resultado de lo cual, en el caché (en ausencia de un bloque que contenga este comando), todo un sector de información del OP se carga en el caché, además, de acuerdo con el principio de localidad, debido a esto, un aumento significativo en la velocidad del sistema.
Modelo de caché jerárquico
Por regla general, la memoria caché tiene una arquitectura de varios niveles. Por ejemplo, en una computadora con 32 KB de caché interna (en el núcleo de la CPU) y 1 MB externa (en la caja de la CPU o en la placa base), la primera se consideraría caché de nivel 1 (L1) y la segunda caché 2. -ésimo nivel (L2). En los sistemas de servidores modernos, el número de niveles de caché puede ser de hasta cuatro, aunque lo más habitual es utilizar dos o tres niveles.
En algunas arquitecturas de procesador, la caché L1 se divide en una caché de instrucciones (InstructionCache, I-cache) y una caché de datos (DataCache, D-cache), no necesariamente del mismo tamaño. Desde el punto de vista de los circuitos, es más fácil y económico diseñar I-cache y D-cache por separado: la I-box lleva a cabo la búsqueda de comandos y la E-box y la F-box obtienen los datos. , aunque en ambos casos intervienen el A-box y el C-box. Todos estos bloques son grandes y es problemático proporcionarles acceso simultáneo y rápido al mismo caché. Además, esto requeriría inevitablemente un aumento en el número de puertos de acceso, lo que también complica la tarea de diseño.
Dado que I-cache y D-cache deben proporcionar una latencia de acceso muy baja (esto es cierto para cualquier caché L1), tienen que sacrificar su tamaño; por lo general, es de 16 a 32 KB. Después de todo, cuanto menor sea el tamaño de la memoria caché, más fácil será lograr un acceso de baja latencia.
La memoria caché del segundo nivel, por regla general, está unificada, es decir, puede contener tanto comandos como datos. Si está integrado en el núcleo de la CPU, entonces hablan de S-cache (SecondaryCache, caché secundaria), de lo contrario, de B-cache (BackupCache, caché de copia de seguridad). En las CPU de servidor modernas, el volumen de S-cache es de uno a varios megabytes, aB-cache, hasta 64 MB. Si el diseño de la CPU prevé la presencia de un caché incorporado de tercer nivel, entonces se llama T-cache (TernaryCache, caché terciario). Como regla general, cada nivel de caché sucesivo es más lento, pero más grande que el anterior. Si B-cache está presente en el sistema (como el último nivel del modelo de memoria caché), entonces puede ser controlado tanto por la CPU como por el conjunto lógico del sistema.
Si en el momento de la ejecución de una determinada instrucción en los registros no hay datos para ella, se solicitarán desde el nivel de caché más cercano, es decir, desde D-cache. Si no están en D-Cache, la solicitud se envía a S-cache, etc. En el peor de los casos, los datos se entregarán directamente desde la memoria. Sin embargo, es posible una opción aún más triste, cuando el subsistema de administración de memoria virtual del sistema operativo (SO) logra forzarlos en el archivo de paginación en el disco duro. En el caso de la entrega desde la RAM, la pérdida de tiempo para recibir los datos necesarios puede ser de decenas a cientos de ciclos de CPU, y en el caso de los datos en el disco duro, ya podemos hablar de millones de ciclos.
Asociatividad de caché
Una de las características fundamentales de la memoria caché, el nivel de asociatividad, refleja su segmentación lógica. El hecho es que la enumeración secuencial de todas las líneas de caché en busca de los datos necesarios requeriría decenas de ciclos y anularía toda la ganancia del uso de la memoria integrada en la CPU. Por lo tanto, las celdas de RAM están conectadas a líneas de caché (cada línea puede contener datos de un conjunto fijo de direcciones), lo que reduce significativamente el tiempo de búsqueda. Se puede asociar más de una línea de caché con cada celda de RAM: por ejemplo, la asociación de n vías significa que la información en una determinada dirección de RAM se puede almacenar en n ubicaciones de caché.
La elección de un lugar se puede realizar de acuerdo con varios algoritmos, entre los cuales los principios de reemplazo LRU (LeastRecentlyUsed, se reemplaza la entrada solicitada más recientemente) y LFU (LeastFrequentlyUsed, la menos frecuentemente solicitada) son los más utilizados, aunque hay modificaciones. de estos principios. Por ejemplo, la memoria caché totalmente asociativa (fullyasociative), en la que la información ubicada en una dirección arbitraria en la RAM se puede colocar en una línea arbitraria. Otra opción es el mapeo directo, en el que la información ubicada en una dirección arbitraria en la RAM se puede colocar en un solo lugar en el caché. Naturalmente, esta opción proporciona el rendimiento más alto, ya que el controlador tendrá que "mirar" en una sola línea de caché al buscar información, pero también es la menos eficiente, ya que el controlador no seleccionará el lugar "óptimo" al escribir. Para la misma cantidad de caché, el esquema de asociatividad completo será el menos rápido, pero el más eficiente.
En la práctica, se encuentra una memoria caché completamente asociativa, pero, por regla general, tiene una cantidad muy pequeña. Por ejemplo, la CPU Cyrix 6x86 usó 256 bytes de esta caché de instrucciones frente a una caché L1 unificada de 16 o 64 KB. A menudo, se utiliza un esquema totalmente asociativo al diseñar TLB (que se analizará más adelante), cachés de direcciones de salto, búferes de lectura y escritura, etc. Como regla general, los niveles de asociatividad de I-cache y D-cache son bastante bajos (hasta a cuatro canales) - su aumento Es inapropiado, porque conduce a un aumento en los retrasos de acceso y, como resultado, afecta negativamente el rendimiento. Como compensación, se aumenta la asociatividad del S-cache (generalmente hasta 16 canales), ya que los retrasos en el acceso a este caché no son importantes. Por ejemplo, según un estudio de tareas de enteros de uso común, el Intel Pentium III tenía 16 000 bytes de caché D de cuatro carriles que cubrían aproximadamente el 93 % de las solicitudes, y 16 000 bytes de caché I de cuatro carriles cubrían el 99 % de las solicitudes.
Línea de caché y tamaño de etiqueta
Una característica importante de la memoria caché es el tamaño de línea. Como regla general, se usa un registro de dirección (la llamada etiqueta) por línea, que indica a qué dirección en RAM corresponde la línea dada. Es obvio que la numeración de bytes individuales es inapropiada, ya que en este caso la cantidad de información general en el caché excederá varias veces la cantidad de datos en sí. Por lo tanto, una etiqueta generalmente se basa en una línea, que generalmente tiene un tamaño de 32 o 64 bytes (el máximo real es 1024 bytes) y es equivalente a cuatro (a veces ocho) bits del bus de datos del sistema. Además, cada línea de caché va acompañada de cierta información para asegurar la tolerancia a fallos: uno o más bits de paridad (parity) u ocho o más bytes de detección y corrección de errores (ECC, ErrorCheckingandCorrecting), aunque en soluciones masivas muchas veces no utilizan ninguno de los dos. uno u otro
El tamaño de una etiqueta de caché depende de tres factores principales: el tamaño de la caché, la cantidad máxima de RAM que se puede almacenar en caché y la asociatividad de la caché. Matemáticamente, este tamaño se calcula mediante la fórmula:
Ciervo=log2(Smem*A/Scache),
donde Stag es el tamaño de una etiqueta de caché, en bits; Smem: cantidad máxima de RAM almacenable en caché, en bytes; Scache: cantidad de memoria caché, en bytes; A - asociatividad de caché, en canales.
De ello se deduce que un sistema con 1 GB de RAM y 1 MB de caché con asociatividad de doble canal requeriría 11 bits para cada etiqueta. Cabe señalar que el tamaño de la línea de caché en sí no afecta el tamaño de la etiqueta de ninguna manera, pero afecta inversamente la cantidad de etiquetas. Debe entenderse que el tamaño de la línea de caché no tiene sentido para que sea menor que el ancho de bits del bus de datos del sistema, pero un aumento múltiple en el tamaño conducirá a una obstrucción excesiva del caché con información innecesaria y carga excesiva en el bus del sistema y el bus de memoria. Además, la cantidad máxima de memoria caché que se puede almacenar no tiene que coincidir con la cantidad máxima de RAM que se puede instalar en el sistema. Si surge una situación en la que hay más RAM de la que se puede almacenar en caché, la caché contendrá información solo del segmento inferior de la RAM. Esta fue exactamente la situación con la plataforma Socket7/Super7. Los conjuntos de chips para esta plataforma permitían grandes cantidades de RAM (de 256 MB a 1 GB), mientras que la cantidad de caché a menudo se limitaba a los primeros 64 MB (estamos hablando del B-caché ubicado en la placa base) debido al uso de 8 bits baratos de chips SRAM de etiquetas (2 bits de los cuales estaban reservados para indicadores de validez y cambio de línea). Esto resultó en una caída notable en el rendimiento.
