Caché virtualmente indexado físicamente etiquetado (VIPT)

requisitos previos:

1. Memoria caché
2. Acceso a la memoria
3. Paginación
4. Amortiguador de transición de mirar a un lado

Revisión del acceso a la memoria caché
Cuando una CPU genera una dirección física, el acceso a la memoria principal precede al acceso a la memoria caché. Los datos se verifican en la memoria caché mediante el uso de la etiqueta y los bits de índice/establecimiento, como se muestra aquí . Tal caché donde la etiqueta y los bits de índice se generan a partir de la dirección física se denomina caché indexada físicamente y etiquetada físicamente (PIPT). Cuando hay un golpe de caché, el tiempo de acceso a la memoria se reduce significativamente.

Average Memory Access Time =
Hit Time + Miss Rate* Miss Penalty

Aquí, Hit Time = Cache Hit Time = Tiempo que se tarda en acceder a una ubicación de memoria en la caché
Miss Penalty = tiempo que se tarda en cargar una línea de caché desde la memoria principal a la caché
Miss Rate =  durante un largo período de tiempo

En los sistemas actuales, la CPU genera una dirección lógica (también llamada dirección virtual) para un proceso. Cuando se usa una caché PIPT, la dirección lógica debe convertirse a su dirección física correspondiente antes de que se puedan buscar datos en la caché PIPT. Esta conversión de dirección lógica a dirección física incluye los siguientes pasos:

1. Verifique la dirección lógica en el búfer de vista lateral de transición (TLB) y, si está presente en TLB, obtenga la dirección física de la página de TLB.
2. Si no está presente, acceda a la tabla de páginas desde la memoria física y luego use la tabla de páginas para obtener la dirección física.

Todo este tiempo se suma al tiempo de acierto. Por lo tanto, tiempo de acierto = latencia TLB + latencia de caché

Limitaciones de la memoria caché PIPT

1. Este proceso es bastante secuencial, por lo tanto, tiene un alto tiempo de éxito.
2. No es ideal para cachés de nivel interno.
3. Cualquier sistema accede con frecuencia a la memoria caché de datos y el acceso de TLB para los datos cada vez ralentizará significativamente el sistema.

Caché etiquetada virtualmente indexada virtualmente
Una solución inmediata parece ser una caché etiquetada virtualmente indexada virtualmente (VIVT) . El caché VIVT verifica directamente los datos en el caché y los obtiene sin traducirlos a una dirección física, lo que reduce significativamente el tiempo de acierto. 
En tal caché, la etiqueta y el índice serán parte de la dirección lógica/virtual generada por la CPU. Ahora, la dirección generada directamente por la CPU se puede usar para obtener los datos, lo que reduce significativamente el tiempo de acierto.  
Solo si los datos no están presentes en la memoria caché, se verificará TLB y, finalmente, después de convertirlos a una dirección física, los datos se llevarán a la memoria caché VIVT. Por lo tanto, tiempo de acierto para VIVT = tiempo de acierto de caché.

Limitaciones de VIVT Cache:

1. El TLB contiene indicadores importantes como el bit sucio y el bit no válido, por lo que incluso con la memoria caché VIVT, TLB debe verificarse de todos modos.
2. Muchos errores de caché en el cambio de contexto: dado que el caché es específico de la dirección lógica y cada proceso tiene su propio espacio de direcciones lógicas, dos procesos pueden usar la misma dirección pero hacer referencia a datos diferentes.
   Recuerde que esta es la misma razón para tener una tabla de páginas para cada proceso. Esto significa que para cada cambio de contexto, el caché debe vaciarse y cada cambio de contexto sigue con una gran cantidad de errores de caché, lo que consume mucho tiempo y se suma al tiempo de acierto.

Una solución a estos problemas es la caché etiquetada físicamente indexada virtualmente (caché VIPT). Las siguientes secciones del artículo cubren VIPT Cache, el desafío en VIPT Cache y algunas soluciones.

Caché etiquetada físicamente indexada virtualmente (VIPT)
La caché VIPT utiliza bits de etiqueta de la dirección física y el índice como índice de la dirección lógica/virtual. La caché se busca utilizando la dirección virtual y se obtiene una parte de la etiqueta de la dirección física. Se busca la TLB con dirección virtual y se obtiene la dirección física. Finalmente, la parte de la etiqueta de la dirección física obtenida de la caché VIPT se compara con la etiqueta de la dirección física obtenida de TLB. Si ambos son iguales, entonces es un acierto de caché, de lo contrario, una falla de caché.

Dado que TLB tiene un tamaño más pequeño que el caché, el tiempo de acceso de TLB será menor que el tiempo de acceso de Cache. Por lo tanto, tiempo de acierto = tiempo de acierto de caché. 
La caché VIPT tarda el mismo tiempo que la caché VIVT durante un golpe y resuelve el problema de la caché VIVT:

1. Dado que también se accede a la TLB en paralelo, las banderas se pueden comprobar al mismo tiempo.
2. La caché VIPT usa parte de la dirección física como índice y dado que cada acceso a la memoria en el sistema corresponderá a una dirección física única, los datos para múltiples procesos pueden existir en la caché y, por lo tanto, no es necesario vaciar los datos para cada cambio de contexto.

Un problema en el que se puede pensar es el caso cuando hay un acierto de caché pero una falla de TLB que requerirá un acceso a la memoria de la tabla de páginas en la memoria física. Esto sucede muy raramente ya que TLB almacena solo bits (dirección y banderas) como sus entradas, lo que requiere mucho menos espacio en comparación con un bloque completo (varios bytes) de memoria en el caso de la memoria caché. Por lo tanto, el número de entradas en TLB es mucho mayor que los bloques de caché en caché, es decir, entradas en   entradas TLB en el directorio de etiquetas de caché.

Ventajas de la caché etiquetada físicamente e indexada virtualmente

1. Evita el acceso secuencial reduciendo el tiempo de acierto
2. Útil en cachés de datos donde el acceso al caché es frecuente
3. Evita errores de caché en el cambio de contexto
4. Se puede acceder a las banderas TLB en paralelo con el acceso a la memoria caché

Desafío en la caché virtualmente indexada con etiquetas físicas La
indexación virtual en la caché VIPT genera un desafío. Un proceso puede tener dos direcciones virtuales asignadas a la misma ubicación física. Esto se puede hacer usando mmap en Linux:

mmap(virtual_addr_A,4096,file_descriptor,offset)
mmap(virtual_addr_B,4096,file_descriptor,offset)

Las dos líneas anteriores asignan el archivo señalado por file_descriptor a dos direcciones virtuales diferentes pero la misma dirección física. Dado que estas dos direcciones virtuales son diferentes y el caché está virtualmente indexado, ambas ubicaciones pueden indexarse ​​en diferentes ubicaciones en el caché. Esto conducirá a tener dos copias del bloque de datos y cuando estas ubicaciones se actualicen, los datos serán inconsistentes. Este problema se llama Aliasing. La creación de alias también puede ocurrir con un bloque compartido por dos procesos.

Las siguientes son las cuatro soluciones para resolver el problema:

1. La primera solución requiere invalidar cualquier otra copia de datos en caché al actualizar una ubicación de memoria.
2. La segunda solución sería actualizar cada otra copia de datos en el caché al actualizar una ubicación de memoria.
   Tenga en cuenta que la primera y la segunda solución requieren verificar si alguna otra ubicación se asigna a la misma ubicación de memoria física. Esto requiere traducir la dirección virtual a la dirección física; pero VIPT tenía como objetivo evitar la traducción, ya que se suma a la latencia de hit.
3. La tercera solución consiste en reducir el tamaño de la memoria caché . Recuerde que durante la traducción de la dirección virtual a la dirección física, el desplazamiento de página de una dirección virtual es el mismo que el de la dirección física. Esto significa que las dos direcciones virtuales también tendrán el mismo desplazamiento de página. Para asegurarse de que las dos direcciones virtuales estén asignadas al mismo índice en la memoria caché, el campo de índice debe estar completamente en la parte de desplazamiento de página.

Ejemplo que demuestra Aliasing:

Consider a system with:
32 bit virtual address,
block size 16 Bytes and page size 4 KB
(i) Direct Mapped Cache: 64 KB
(ii) Direct Mapped Cache: 4 KB
(iii) Direct Mapped Cache: 2 KB

(i) En la dirección virtual de 32 bits, para un caché de mapeo directo de 64 KB, los 
bits 15 a 4 son para el índice, los 
bits 11 a 0 son desplazamiento de página (lo que significa que para cualquier dos VA que apunte al mismo PA, 12 bits LSB serán ser el mismo).

Dos direcciones virtuales pueden ser 0x0045626E y FF21926E asignadas a la misma dirección física. La primera dirección se indexará en la línea de caché (626) _H y la segunda dirección se indexará en (926) _H . Esto muestra que la creación de alias ocurre con un caché de mapeo directo de 64 KB para el sistema. También tenga en cuenta que los últimos 12 bits son iguales en ambas direcciones, ya que se han asignado a la misma dirección física y los últimos 12 bits forman el desplazamiento de página, que será el mismo para ambas direcciones virtuales.

(ii) En la dirección virtual de 32 bits, para un caché de mapeo directo de 4 KB, los bits 11 a 4 son para el índice, los bits 11 a 0 son desplazamiento de página (lo que significa que para dos VA cualesquiera que apunten al mismo PA, 12 bits LSB serán ser el mismo).

Dos direcciones pueden ser 0x12345678 y 0xFEDCB678. Tenga en cuenta que los 12 bits LSB son iguales, es decir, (678) _H . Dado que para un caché de asignación directa de 2 KB, los bits de índice son completamente una parte del mismo desplazamiento de página, el índice de caché donde se asignarán ambas direcciones virtuales será el mismo. Por lo tanto, solo queda una copia a la vez y no se produce ningún alias. 

(iii) A continuación se muestra una representación de una memoria caché de asignación directa de 2 KB para el sistema que no muestra alias. Por lo tanto, cualquier caché asignada directamente de un tamaño menor o igual a 4 KB no generará alias.

         4. La tercera solución para crear alias requiere que la memoria caché sea más pequeña; una memoria caché más pequeña provocará más errores de memoria caché. Las soluciones 1, 
             2 y 3 están basadas en hardware. Otra solución llamada color de página/coloración de caché es una solución de software          
             implementada por el sistema operativo para resolver el aliasing sin limitar el tamaño de la caché. En el caso de una memoria caché de 64 KB 
             , se necesitan 16 colores para garantizar que no se produzcan alias. Además, lea: Página para colorear en ARMv6