Función de correspondencia

En Arquitectura de computadoras, la función de correspondencia es un algoritmo que permite corresponder los bloques de memoria a las líneas de caché. Se requiere algún medio para determinar que bloque de memorial principal ocupa una línea dada de caché, el método surge debido a la minoría de líneas de caché en relación con los bloques de memoria principal. Está fundamentada en la correspondencia matemática que establece que dados dos conjuntos: X e Y, y un Grafo f, que determina alguna relación binaria entre algún elemento de X con algún elemento de Y, diremos que ese grafo: f, define una correspondencia entre X e Y, cuando al menos un elemento de X está relacionado con al menos un elemento de Y.

Técnicas de la función de correspondencia

La elección de la función de correspondencia determina cómo se organiza la caché. Pueden utilizarse tres técnicas: directa, asociativa y asociativa por conjuntos:

Directa

Es la técnica más simple, consiste en hacer corresponder cada bloque de memoria principal a solo una línea posible de caché, en donde la correspondencia se expresa como:

I = J módulo M

I = Número de línea cache
J = Número de bloque de memoria principal
M = Número de líneas en la cache

La función de correspondencia se implementa fácilmente utilizando la dirección. Desde el punto de vista de acceso a caché, cada dirección de memoria principal puede verse como dividida en tres campos, Los w bits menos significativos identifican cada palabra dentro de un bloque de memoria principal; en la mayoría de las máquinas actuales, el direccionamiento es a nivel de bytes. Los s bytes restantes especifican uno de los segundos bloques de la memoria principal. La lógica de la caché interpreta esos s bits como una etiqueta de s – r bits y un campo de línea de r bits. La técnica de correspondencia es directa es simple y poco costosa de implementar. Su principal desventaja es que hay una posición concreta de caché para cada bloque dado. Por ello si un programa referencia repetidas veces a palabras de dos bloques diferentes asignados en la misma línea, dichos bloques se estarían intercambiando continuamente en la caché, y la tasa de aciertos sería baja.

Asociativa

Este tipo de correspondencia supera la desventaja planteada en la directa, permitiendo que cada bloque de memoria principal pueda cargarse en cualquier línea de la caché. En este caso, la lógica de control de la cache interpreta una dirección de memoria simplemente como una etiqueta y un campo de palabra. El campo de etiqueta identifica unívocamente un bloque de memoria principal. Para determinar si un bloque está en la caché, su lógica de control debe examinarse simultáneamente todas las etiquetas de líneas para buscar una coincidencia. Con la correspondencia asociativa hay flexibilidad para que cualquier bloque sea reemplazado cuando se va a escribir uno nuevo en la caché. Los algoritmos de reemplazo o sustitución, discutidos más adelante en esta sección, se diseñan para maximizar la tasa de aciertos. La principal desventaja de la correspondencia asociativa es la compleja circuitería necesaria para examinar en paralelo las etiquetas de todas las líneas de caché.

Asociativa por conjuntos

Se reconoce como una solución de compromiso que recoge lo positivo de las correspondencias directa y asociativa, sin presentar sus desventajas. En este caso, la caché se divide en v conjuntos cada uno de k líneas. Las relaciones que se tienen son:

M = V×K
I = J módulo V

I = Número de conjuntos de cache
J = Número de bloque de memoria principal
M = Número de líneas de la cache

En este caso, se denomina correspondencia asociativa por conjunto de k vías. Con la asignación asociativa por conjuntos, el bloque Bj puede asignarse en cualquier de las k líneas del conjunto i. En este caso, la lógica de control de la caché interpreta una dirección de memoria como tres campos: etiqueta, conjunto y palabra. Los d bits de conjunto especifican uno de entre v = 2d conjuntos. Los s bits de los campos de etiqueta y de conjunto especifican uno de los segundos bloques de memoria principal. Con la correspondencia totalmente asociativa, la etiqueta en una dirección de memoria es bastante larga, y debe compararse con la etiqueta de cada línea en la caché. Con la correspondencia asociativa por conjuntos de k vías, la etiqueta de una dirección de memoria es mucho más corta, y se compara solo con las k etiquetas dentro de un mismo conjunto. En el caso extremo de v = m, k = 1, la técnica asociativa por conjuntos se reduce a la correspondencia directa, y para v = 1, k = m, se reduce totalmente a la asociativa. El uso de dos líneas por conjunto (v = m /2, k=2) es el caso más común, mejorando significativamente la tasa de aciertos respecto de la correspondencia directa. La asociativa por conjuntos de cuatro vías (v = m/4, k = 4) produce una modesta mejora adicional con un coste añadido relativamente pequeño. Un incremento adicional, en el número de líneas por conjunto tendría poco efecto.

Bibliografía

Stallings, W. (2000). Organización y Arquitectura de Computadores (Quinta Edición ed.). Madrid: Pearson Prentice Hall. ISBN 84-205-2993-1.Organización y Arquitectura de Computadores

Datos: Q8963061