Jerarquía de Memoria y Cachés en Procesadores Modernos: Optimización y Coherencia

Jerarquía de Memoria en Sistemas Actuales - Tendencias en los Procesadores Actuales

Integración de 2 y hasta 3 niveles de caché en el chip del procesador. Crecimiento del tamaño de las cachés (aumento del nivel de integración). Cachés y TLB's separadas para datos e instrucciones.

Puntos en común: búsqueda fuera de orden, cachés no bloqueantes (acierto bajo fallo y fallo bajo fallo), prebúsqueda de instrucciones y datos por hardware, instrucciones software para prebúsqueda de datos y las cachés del primer nivel pueden soportar varios accesos en el mismo ciclo.

(T.4) Memoria Virtual

Definición

Gestión de memoria automática que da al programador la ilusión de que su espacio de direccionamiento no está limitado por el espacio de memoria principal reservado a su programa (espacio físico), sino por el rango de direcciones que permite el sistema (espacio virtual).

Ventajas

• El espacio virtual puede ser mucho mayor que el físico (raro que sea menor).
• Facilita la multiprogramación.
• Mejor aprovechamiento de la memoria principal.
• Facilita la protección de los programas.
• Transparente al programador.

Inconvenientes

• Gasto temporal relativamente elevado de la gestión de memoria (traducción de direcciones, reemplazos de bloques reservados, etc.).
• Gasto de procesamiento en la resolución de excepciones.
• Gasto hardware para conseguir una gestión de memoria rápida y eficiente (MMU, Memory Management Unit).

Traducción hardware-software: desde el procesador → dirección virtual → mapeador de direcciones (fallo de página si la página no está presente) → dirección física → jerarquía de memoria.

Estrategias de Implementación de la Memoria Virtual

1) MMU Interna

MMU en el mismo circuito integrado que el procesador. Se da en casi todos los procesadores actuales.

Ventajas: tiempos de acceso reducidos, alta portabilidad de programas y compartición de hardware entre el procesador y la MMU.

2) MMU Externa

MMU en un circuito integrado independiente.

Ventajas: se ahorra espacio del circuito integrado del procesador para otros recursos (caché, etc.).

Definiciones

• ESPACIO VIRTUAL = espacio nominal = espacio de direcciones: conjunto de direcciones que pueden direccionar un proceso.
• ESPACIO FÍSICO = espacio de memoria = reserva de memoria primaria (FMA): espacio de memoria reservado para el proceso.
• TRADUCTOR DE DIRECCIONES: V → espacio virtual, M: espacio físico. Al recibir un x ∈ v devuelve y si x está en M en la posición y, o bien ? en otro caso, provocando una excepción o fallo de direccionamiento (la referencia x debe transferirse de la memoria secundaria a la primaria).

Reglas para Resolver Fallos de Direccionamiento

1. Regla de carga: CUÁNDO se transfiere x.
2. Regla de ubicación: DÓNDE se sitúa x en la memoria principal.
3. Regla de reemplazo: QUÉ referencia virtual situada en la memoria principal debe eliminarse para hacer sitio a x (solo si la memoria principal está totalmente ocupada).

Clasificación de los Sistemas de Memoria Virtual

Los sistemas de memoria virtual agrupan las referencias virtuales en bloques. Una referencia virtual, por tanto, está compuesta por dos campos: número de bloque y desplazamiento dentro del bloque (estos bloques se consideran como las unidades de transferencia de información entre la memoria secundaria y la principal).

El traductor de direcciones, por tanto, solo debe traducir el campo de bloque, dejando invariante el desplazamiento. El tamaño del traductor, pues, es proporcional al número de bloques del espacio virtual (o físico).

Tipos de Sistemas de Memoria Virtual según Tamaño de Bloques:

1. Paginados: los bloques son todos del mismo tamaño. Los bloques se llaman páginas y una excepción se llama 'fallo de página'.
2. Segmentados: los bloques son de tamaño diferente. Los bloques se llaman segmentos y una excepción es un 'fallo de segmento'.
3. Sistemas Segmentados con Paginación: los bloques (segmentos) son de tamaño desigual pero múltiplo de un tamaño unidad (página).

(4.1) Sistemas Paginados

: es el esquema de mem. virtual + difundido REPRESENTACION - Programa P: P = {p₁,p₂,...,p_n}, con p_i pagina virtual • Normalmente, tamaño(p_i)=p=2^k • Dir. virtual incluida en p_i: a_ij = p_id_j con p_i € P, 0jj, 1 pagina fisica) ESQUEMAS BASICOS DE IMPLEMENTACION DE TRADUCCION - A)Traduccion directa: el traductor se implementa mediante una tabla d acceso directo de tamaño |V|/p, llamada tabla de paginas (tabla indexada por el nº de PV, bit de residencia, bit d validez, bit d modificacion (siempre postescritura), reemplazo, proteccion) • Almacenamiento de la tabla de paginas: en registros rapidos (traduccion rapida y costosa) o en la mem. principal (traduccion + lenta pero - costosa q la anterior) B)Traduccion asociativa: la traduccion se implementa mediante una tabal d paginas, pero esta se almacena en una mem. asociativa. Su tamaño es |M|/p entradas. C)Traduccion directa en varios niveles: el alto coste de los registros rapidos y d las mem. asociativas asi como el gran tamaño d la tabla d paginas d acceso directo, restringen el uso d los esquemas d traduccion directo y asociativo a sistemas pequeños • La mayoria de los sistemas realizan la traduccion mediante un esquema directo en 2 niveles, es dcir, almacenan la tabla d paginas en el espacio virtual (paginan la tabla d paginas) • Algunos sistemas amplian la traduccion a 3 niveles • Inconvenientes: la traduccion es + lenta, pues hay q hacer 3 (o 4, 3 niveles + dato) accesos a la mem. principal). La gestion d fallos d pagina es compleja D)Traduccion directa y asociativa combinada: pretende combinar la ventaja del bajo coste hardware d la traduccion directa con la ventaja d la alta velocidad d la traduccion asociativa • La memoria asociativa o TLB, almacena los pares [pagina virtual, pagina fisica] mas recientemente referenciados juntos con los bits de gestion q se requieran. Su exito esta justificado por el principio de localidad y el tamaño tipico de la TLB es de 32 a 256 entradas. 

Tasa_Fallos q una cache asociativa por conjuntos de 2 vias d la mitad d tamaño. Puede aumentar el Tiempo_Acierto (incrementa el Tiempo_CicloReloj) CACHES VICTIMAS - cache pequeña totalmente asociativa. Guarda las lineas eliminadas d la cache en un fallo. Si la linea requerida se encuentra en ella, es intercambiada con una linea d la cache. Especialmente utiles pa caches d datos pequeñas d correspondencia directa CACHES PSEUDO-ASOACIATIVAS - en un fallo, antes d ir al nivel inferior d la jerarquia d memoria, se chequea otra linea d la memoria ('pseudo-conjunto'). Existen dos Tiempo_Acierto. Hay q colocar correctamente las lineas pa no degradar el rendimiento. Puede complicar el diseño de CPU segmentadas PREBUSQUEDAS DE INSTRUCC. Y DATOS - el objetivo es solapar la ejecucion con la prebusqueda. El rendimiento puede reducirse si interfiere en la demanda de los fallos. Puede realizarse de 2 formas: 1)Hardware: directamente en la cache o en un buffer externo 2)Controlada por el compilador: el dato prebuscado se puede grabar en un registro o en la cache  OPTIMIZACION EN TIEMPO DE COMPILACION - mediante la reordenacion del codigo o la reubicacion de los datos, se puede reducir la Tasa_Fallos. Algunos ejemplos de tecnicas son la fusion de arrays, intercambio de lazos, blocking o la fusion de lazos. (3.7)REDUCCION DE LA PENALIZACION DE FALLO: DAR PRIORIDAD A LOS FALLOS DE LECTURA SOBRE LAS ESCRITURAS - en una cache d escritura directa: añadimos buffer de escritura del tamaño adecuado, con el handicap de q puede tener el valor actualizado d una posicion necesaria en un fallo d lectura con lo que o esperamos a q se vacie el buffer o comprobamos el contenido del buffer • En una cache de postescritura: añadimos un buffer para almacenar el bloque modificado deteniendose la CPU si se presenta un nuevo fallo hasta q se vacie el buffer UBICAR SUBBLOQUES: (en caches de correspondencia directa): los subbloques tienen bit de validez. Reduce la Penalizacion de fallo, reduce el tamaño de la etiqueta y ayuda en los aciertos de escritura escribiendo siempre la palabra NO ESPERAR A ALMACENAR TODA LA LINEA - los beneficios dependen del tamaño d la linea y de la probabilidad d acceso a otra palabra d la misma linea. 2 tecnicas: 1)Rearranque anticipado: cuando llegue la palabra se envia a la CPU y continua la ejecucion 2) Busqueda fuera de orden: requerir la palabra q falla y enviarla a la CPU. Esta continua la ejecucion mientras se llena la linea CACHE LIBRE DE BLOQUEO - incrementa la complejidad del controlador d cache y no afecta al Tiempo de acierto. Varias opciones: acierto bajo fallo, acierto bajo multiples fallos y fallo bajo fallo (bancos d memoria independientes) CACHE DE DOS NIVELES - Cache de primer nivel de velocidad comparable a la d la CPU y cache de 2º nivel d gran tamaño pa capturar la mayoria d fallos q irian a la mem. principal • La veloc. de la de primer nivel afecta a la frec. reloj de la CPU y la de 2º nivel a la penalizacion de fallo de la del primer nivel • Propiedad de inclusion multinivel: todos los datos de la de primer nivel estan en la de 2º nivel. Deseable para mantener la consistencia. Se puede mantener con distintos tamaños de linea en las caches (invalidacion d lineas del primer nivel) • Resumiendo: en las caches de 2º nivel el enfasis se debe hacer en la reduccion d fallos, usando caches grandes, alta asociatividad y lineas grandes (3.8) REDUCCION DEL TIEMPO DE ACIERTO: CACHES PEQUEÑAS Y SIMPLES - el hardware pequeño es mas rapido. Una cache lo suficiente pequeña puede incluirse en el chip del procesador. En una cache de correspondencia directa se puede solapar el chequeo d la etiqueta con la transmision d los datos SEGMENTACION DE LAS ESCRITURAS - en una escritura la cache compara la etiqueta con la dir. actual. Para la escritura la cache usa los datos y etiqueta del acierto de escritura previo. Puede realizarse una escritura por ciclo. No hay ninguna modificacion para las lecturas (ya operan en paralelo) EVITAR LA TRADUCCION DE DIR. DURANTE EL INDEXADO DE LA CACHE - caches virtuales: usan la dir. virtual. Problemas --> cambio de proceso (añadir una etiqueta identificadora de proceso), sinonimos o alias (soluciones hardware como antialias o software como page coloring), entrada/salida: requiere una correspondencia con las dir. virtuales • Accesos a memoria + intensamente segmentados: + penalizacion en las predicciones erroneas d saltos y + ciclos d reloj entre el almacenamiento y el uso d datos • Utiliza la parte fisica d la dir. pa indexar la cache mientras se traduce la dir. virtual: caches d correspondencia directa limitadas en tamaño --> Alternativas: cache asociativa por conjuntos, page coloring o prediccion hardware ** de la 3.6 a la 3.8 son MEJORAS DEL RENDIMIENTO CACHE ** (3.9) COHERENCIA CACHE: ENTRADA/SALIDA - los dispositivos de E/S pueden hacer copias de la cache inconsistentemente y pueden usar copias obsoletas de la memoria. El acceso de las E/S a la cache resuelve el problema, pero interfiere con el funcionamiento de la CPU. Es preferible el acceso a mem. principal (buffer de E/S) • Cache de escritura directa: 1) salida: no hay datos obsoletos 2) entrada: soluciones software (paginas no cacheables, eliminacion d las dir. del buffer) y solucion hardware (comprobacion de las dir. de E/S) • Cache de postescritura: las mismas soluciones q las comentadas en la cache d escritura directa pa la entrada MULTIPROCESADORES - un programa ejecutandose en multiples procesadores querra tener copias del mismo dato en varias caches. Tipos de protocolos de coherencia cache: 1)Basados en directorio: una unica copia de la info. d las lineas. La info. es proporcional al nº d la linea d la mem. principal y no requiere un bus q vaya a todas las caches (+ escabilidad) 2)Espionaje (snooping): cada cache tiene su copia de la info. Requiere un bus comun a mem. y la info. de coherencia es proporcional al nº d lineas d la cache. Para no interferir con la CPU se duplica la parte d etiquetas d la cache • Dependiendo d lo q ocurra en una escritura tenemos: Invalidacion en escritura (multiples lectores y un solo escritor) o difusion en escritura (puede distinguir entre lineas compartidas o locales) • La mayoria d los multiprocesadores basadas en caches utilizan postescritura pq reduce el trafico d bus • El tamaño de linea es importante en la coherencia cache (comparticion falsa)