Técnicas de aumento de prestaciones para memoria y E/S

Técnicas de optimización para la memoria caché.
El objetivo es reducir el tiempo medio de acceso a memoria:

Tiempo de acceso medio a memoria = Tiempo de acierto + Frecuencia de fallos * Penalización por fallo.

Existen tres formas de reducir el tiempo medio de acceso a memoria:
– Reducir los fallos de la cache (miss rate)
– Reducir las penalizaciones por fallo (miss penalty)
– Reducir el tiempo de acceso en caso de acierto (hit time)

Existen tres tipos de fallos en una memoria cache:
– Forzosos (Compulsory): En el primer acceso a un bloque éste no se encuentra en la cache (fallos de arranque en frío o de primera referencia)
– Capacidad (Capacity): La cache no puede contener todos los bloques necesarios durante la ejecución de un programa
– Conflicto (Conflict): Diferentes bloques deben ir necesariamente al mismo conjunto o línea cuando la estrategia es asociativa por conjuntos o de correspondencia directa (fallos de colisión)

CapturaCapturaTécnica: Incremento del tamaño de bloque (I)
Incrementar el tamaño de bloque – Ventajas: Se reducen los fallos forzosos como sugiere el principio de localidad espacial
– Inconvenientes: Aumentan los fallos por conflicto al reducirse el número de bloques de la cache y los fallos de capacidad si la cache es pequeña. La penalización por fallo aumenta al incrementarse el tiempo de transferencia del bloque.
CapturaCapturaCaptura
Técnica: Incremento de la asociatividad
• Aumentar la asociatividad
– Ventajas: Se reducen los fallos por conflicto
– Inconveniente: Aumenta el tiempo de acceso medio al incrementarse el tiempo de acierto (multiplexión). También aumenta el coste debidos a los comparadores.
CapturaTécnica: Cache victima (I)
Caches víctimas: Consiste en añadir una pequeña cache totalmente asociativa (1-5 bloques) para almacenar bloques descartados por fallos de capacidad o conflicto. En caso de fallo, antes de acceder a la memoria principal se accede a esta cache. Si el bloque buscado se encuentra en ella se intercambian los bloques de ambas caches
– Cache víctima de 4 bloques reduce del 20% al 95% los fallos de conflicto en una cache de correspondencia directa de 4Kb (Jouppi 1990)

CapturaTécnica: Cache pseudo-asociativa
Consiste en utilizar toda la capacidad de la cache para reubicar algunos bloques extra en bloques que en principio no les pertenece
– Implementación: Cuando en una cache de correspondencia directa se falla, antes de ir a buscar en la memoria principal puede intentarse en otro bloque (el correspondiente al índice pero con el bit más significativo invertido) del “pseudo conjunto”
Captura
Técnica: Pre-búsqueda hardware de instrucciones y datos
Consiste en que cuando se accede a memoria en caso de fallo no sólo se trae el bloque solicitado sino también los consecutivos, almacenándolos en un buffer. Si en el próximo acceso el bloque se encuentra en el buffer, se cancela el acceso en curso a la cache, se lee el bloque del buffer y comienza una nueva solicitud de pre-búsqueda.
– En un sistema con caches de datos e instrucciones separadas de 64Kb asociativas de 4 vías, un buffer de 8 bloques eliminan del 50% al 70% de los fallos (Palacharna and Kessler 1994).

Técnica: Pre-búsqueda controlada por el compilador (I)
Otra alternativa consiste en que es el propio compilador el que inserta instrucciones de pre-búsqueda, solicitando datos cuando aún no son necesarios
– Pre-búsqueda en registro: El valor se almacena en un registro
– Pre-búsqueda en cache: El valor se almacena en la cache

Técnica: Optimización del compilador
El compilador reordena el código de manera que por la forma en como se hacen los accesos se reducen los fallos de cache
– Detectando conflictos y reordenando las instrucciones se han reducido los fallos un 50% en una cache de correspondencia directa de 2Kb con bloques de 4 bytes y 75% en una de 8Kb (McFarling 1989)
– Técnicas:
• Mejora de la localidad espacial: Mezcla de arrays e Intercambio de bucles
• Mejora de la localidad temporal: Fusión de bucles y Bloqueado

Reducir las penalizaciones por fallo (miss penalty).
Técnica: Uso de Sub-bloques
– Cuando las etiquetas son demasiado grandes (ocupan mucho y su comparación es costosa) pueden reducirse haciendo bloques más grandes pero eso aumenta la penalización por fallo (tiempo de transferencia)
– Para evitarlo pueden dividirse los bloques en sub-bloques y utilizar en vez de un bit de válido tantos como sub-bloques tengamos. Las transferencias son a nivel de sub-bloques
CapturaTécnica: Dar prioridad a los fallos de lectura sobre la escritura (I)
En la caches WT el buffer de post-escritura mejora el rendimiento pero también complica los accesos a memoria cuando el bloque buscado se encuentra en el buffer (aún no ha sido escrito en memoria) y se produce un fallo en lectura de dicho bloque.

Ejemplo:
Una cache de correspondencia directa WT con buffer de post-escritura (conflicto entre las posiciones 512 y 1024) ¿El contenido de R2 y R3 es igual?
M[512] ← R3 — escritura en buffer
R1 ← M[1024] — fallo en lectura
R2 ←M[512] — fallo en lectura (aún no se ha copiado el bloque)
— El fallo en lectura debe esperar a que finalice la escritura

Solución: Para evitar que los fallos en lectura esperen siempre a que el buffer se vacíe (en un buffer de cuatro palabras supone un incremento de la penalización de un 50%) se puede comprobar el contenido del buffer y si no hay conflicto permitir que el fallo en lectura continúe

Esta técnica también permite reducir la penalización por fallo en caso de caches CB (escritura del bloque sucio)

Técnica: Re-arranque rápido y primera palabra crítica
Estas técnicas se basan en el hecho de que en un momento dado la CPU sólo necesita una palabra del bloque para continuar la ejecución
– Re-arranque rápido (Early restart): Consiste en no esperar a leer todo el bloque sino que en cuanto se haya transferido la palabra solicitada enviarla a la CPU y luego continuar trayendo el bloque
– Primera palabra crítica (Critical word first): Consiste en solicitar a la memoria sólo la palabra que falló y enviarla tan pronto como llegue a la CPU. Mientras ésta continua con la ejecución, se rellena el resto de palabras del bloque

Técnica: Caches no bloqueantes
Esta técnica se utiliza en máquinas con pipeline. Por ejemplo, es posible continuar la búsqueda de una instrucción en la cache de instrucciones mientras se espera que se traiga un bloque fallido en la cache de datos

Reducir el tiempo de acceso en caso de acierto (hit time).
Técnica: caches pequeñas y simples
Buena parte del tiempo de acierto se dedica a leer y comparar las etiquetas.
– Las caches pequeñas (on-chip) permiten tiempos de acierto reducidos pero poca capacidad. Una posible solución: etiquetas onchip y datos off-chip.
– En las caches de correspondencia directa (simples) la comprobación de la etiqueta y el acceso al dato se hace a la vez.
– En el primer nivel de cache se utilizan caches pequeñas y simples.

Técnica: Evitar la traducción de direcciones
Evitar la traducción de direcciones durante la indexación de la cache: Consiste en almacenar direcciones virtuales en la cache, evitando así la traducción de direcciones virtuales a físicas en caso de acierto (Caches virtuales vs. Caches físicas).

Técnica: Escrituras en pipeline para aciertos en escritura rápidos
Consiste en crear un pipeline para las operaciones de escritura, de manera que la escritura actual se hace solapada en el tiempo con la comparación de etiquetas de la escritura siguiente. Las operaciones de lectura no son parte de este pipeline pues la comparación de etiquetas y la lectura del bloque se hacen siempre en paralelo.

Técnicas de optimización para la memoria principal.
La memoria principal es el siguiente nivel de la jerarquía de memorias, a continuación de las caches, y por tanto satisface las demandas de ese nivel. Además, sirve de interfaces para la E/S de la computadora. Al ser el siguiente nivel de la jerarquía, y por el hecho de ser un nivel más lento que la cache, su organización influye en la penalización de fallo y por tanto influye en el rendimiento.

Los parámetros para evaluar el rendimiento de la memoria principal son:
– Latencia : tiempo en obtener el primer acceso
– Ancho de banda : número de bytes leídos o escritos por unidad de tiempo.

Para lograr un buen rendimiento, hay que conseguir el mejor ancho de banda posible entre la cache y la memoria principal, ya que así se disminuye el tiempo de transferencia. El tiempo de acceso o latencia es difícil de reducir.

Las posibles organizaciones para mejorar el rendimiento de la memoria principal son:

– Aumentar el ancho de la memoria
• Se aumenta el ancho de banda haciendo la memoria y el bus de varias palabras de ancho.
• Aumentar el ancho de la memoria y del bus disminuye el tiempo de acceso y el tiempo de transferencia → disminuye la penalización de fallo • Se necesita un multiplexor que seleccione la palabra del bloque de cache que se va a suministrar a la CPU
• Todas estas medidas aumentan el coste, y aumentan también el tiempo de acceso a la cache.
CapturaSi ancho de memoria es de 2 palabras
Penalización de fallo = 1 + 2×15 + 2×1 = 33 ciclos
Nº bytes transferidos/ciclo = 16/33 = 0,48

Si ancho de memoria = 4 palabras
Penalización de fallo = 1 + 1×15 + 1×1 = 17 ciclos
Nº bytes transferidos/ciclo = 16/17 = 0,94

Utilizar memoria entrelazada:
Se incrementa el ancho de banda ensanchando la memoria pero no el bus de conexión.

Memoria organizada en bancos de 1 palabra de ancho. Se leen/escriben simultáneamente varias palabras (tantas como bancos) con un solo tiempo de acceso.
– Hay una parte común en la dirección que se envía a todos los bancos
– Todos los bancos acceden simultáneamente al dato ubicado en esa dirección
– Se lee el dato disponible en cada banco → se obtiene un bloque de datos.
Captura Los bits menos significativos de la dirección seleccionan el banco de memoria. Direcciones consecutivas de memoria (Dn) se ubican en bancos consecutivos.
– Ejemplo con 4 bancos:
D0 -> Banco0; D1 -> Banco1;
D2 -> Banco2; D3 -> Banco3;
Dn -> Banco(Dn MODULO Nº Bancos)

Se sigue pagando el coste de transmitir cada palabra secuencialmente, pero se evita pagar más de una vez la latencia de acceso.

Técnicas de optimización conjunta para todos los niveles de la jerarquía (visión global de la jerarquía de memoria).
Memoria
Técnicas de optimización para los buses E/S.
Cuando el número de dispositivos conectados a un bus aumenta disminuye su rendimiento. Esto es debido a dos motivos fundamentales:

– El aumento del retardo de propagación de las señales debido al aumento de longitud de los conductores que dan soporte al bus. Esto afecta especialmente a la propagación encadenada de la señal de concesión del bus.
– El incremento de demanda de acceso que se produce al aumentar el número de dispositivos conectados. Este exceso de dispositivos puede crear un cuello de botella que haga que el rendimiento del sistema se degrade por la espera inútil que se origina cuando tienen que realizar transferencias.

Las diferencias en la velocidad de operación de los dispositivos conectados al bus, también repercuten negativamente en su rendimiento. Para evitar la caída de rendimiento, el sistema de buses se jerarquiza, apareciendo dos buses más: el bus local, y el bus de E/S. El bus local es de longitud pequeña, de alta velocidad, y adaptado a la arquitectura particular del sistema para maximizar el ancho de banda entre el procesador y la caché, por eso suele ser un bus propietario. Este bus aísla el tráfico procesador-caché del resto de transferencias del sistema.
CapturaEl bus de E/S o de expansión reduce el tráfico en el bus del sistema, de manera que el procesador puede acceder a memoria en un fallo de caché mientras realiza una operación de entrada/salida. Los buses de expansión son buses estándar o abiertos (ISA, EISA, PCI, etc.) es decir, independientes de la computadora y con unas características bien definidas en el correspondiente documento de normalización. La existencia de estos buses permite diseñar una amplia gama de controladores de periféricos compatibles. Para conectar los buses del sistema y de expansión se requiere un Adaptador de Bus, dispositivo que permite adaptar las distintas propiedades de ambos buses: velocidad, carácter síncrono o asíncrono, multiplexación, etc.

El proceso de jerarquización se puede complicar más con otras topologías que den cabida a dispositivos de distinta velocidad. De esta forma se equilibra mejor el tráfico de información en sistemas que operan con muchos dispositivos conectados. En la figura siguiente se muestra una topología jerárquica en la que se contempla un bus de alta
velocidad del que cuelgan dos buses, uno de expansión para  dispositivos rápidos y otro de E/S para dispositivos lentos.
Antologia Arquitectura de Computadoras
Técnicas de optimización para los dispositivos de E/S.
Las diferencias existentes entre los dispositivos periféricos han hecho que la unidad de E/S de una computadora se organice en torno a dos tipos de elementos, unos que soportan las características comunes a todos los dispositivos (módulos de E/S) y otros específicos para cada periférico que son los controladores de dispositivo:

Un módulo de E/S permite que el procesador gestione una amplia gama de dispositivos periféricos de una forma similar, ocultando los detalles concretos de temporización, formatos de datos y principios físicos de funcionamiento. El módulo de E/S se conecta con el procesador a través de un conjunto de líneas de datos, dirección y control (un bus). Los
datos que se transfieren se almacenan temporalmente en un registro de datos.

El estado del módulo se refleja en los bits de un registro de estado. El registro de control permite configurar y programar diferentes funciones en el módulo. Estos dos registros (estado y control) pueden unificarse en uno sólo en módulos simples. Un módulo de E/S dispone de la lógica específica para su conexión con uno o más dispositivos periféricos.
CapturaLa estructura del controlador de un dispositivo tendrá que adaptarse en cada caso a las peculiaridades específicas del periférico. Unos tendrán que actuar sobre elementos electromecánicos (impresoras de línea), otros sobre elementos ópticos (CD-ROM), o magnéticos (discos), etc.
CapturaLa conexión con el módulo de E/S se realiza a través de señales de control, estado y datos. Es la parte del controlador que homologa su comportamiento singular al esquema general de gestión de la E/S. Las señales de control determinan la función que debe realizar el dispositivo. La lógica de control asociada al dispositivo controla su operación en respuesta a las indicaciones del módulo de E/S. El transductor convierte las señales eléctricas asociadas a los datos a otra forma de energía. Además, suele existir un buffer asociado al transductor para almacenar temporalmente el dato que se transfiere entre el módulo de E/S y el dispositivo.

Técnicas de optimización para la gestión E/S
Existen dos mecanismos básicos para sincronizar las operaciones de E/S con las de la CPU: sincronización por programa y sincronización por interrupción:

E/S controlada por programa.
La CPU tiene el control absoluto de la operación de E/S: inicia y lleva a cabo la transferencia.  La sincronización por programa (E/S programada) es la más sencilla de implementar en
la computadora, sin embargo, presenta algunos inconvenientes:

• Pérdida de tiempo: el computador no realiza trabajo útil en el bucle de espera.
• Impide la realización de tareas periódicas, como la exigida por el refresco de una pantalla.
• Dificultades para atender varios periféricos.

E/S por interrupción: gestión de interrupciones.
La E/S le indica a la CPU cuando está preparada para transferir datos (genera una interrupción a la CPU), activando una línea especial conectada a la CPU (línea de interrupción).

– El periférico es capaz de interrumpir a la CPU para indicar que esta preparado.
– La CPU puede realizar otras tareas y solamente atiende al periférico cuando se produce una interrupción.
– La CPU es la encargada de controlar la operación de E/S mediante la ejecución de  la RTI.
CapturaCaptura
E/S con acceso directo a memoria (DMA)
El DMA (Direct Memory Access) es un procesador/controlador especializado en transferencias “muy grandes” desde periféricos a memoria y viceversa.

Cuando se tienen que transferir grandes cantidades de datos y a una elevada velocidad, es necesario disponer de una técnica que realice de forma más directa las transferencias entre la memoria y el dispositivo periférico, limitando al máximo la intervención de la CPU.

Básicamente se trata de un módulo con capacidad para leer/escribir directamente en la memoria los datos procedentes/enviados de/a los dispositivos periféricos. Para ello solicita la correspondiente petición a la CPU. Antes de que la CPU conceda acceso a memoria al DMA, pone en estado de alta impedancia su conexión a los buses del sistema (datos, direcciones y R/W), lo que es equivalente a desconectarse de la memoria durante el tiempo que es gestionada por el DMA. Cuando finaliza la operación de E/S el DMA genera una interrupción y la CPU vuelve a tomar control de la memoria. De esta forma la velocidad de transferencia sólo estarán limitadas por el ancho de banda de la memoria.

El DMA (Direct Memory Access) es programable. La CPU no realiza ninguna tarea (salvo programar el DMA) ya que la inicialización y transferencia son gobernadas por el periférico.

Para programar el DMA hay que enviarle al menos los siguientes datos:
– Dirección/puerto periférico E/S.
– Posición/dirección en memoria principal.
– Tamaño (número de bytes a transferir).
– Tipo transferencia: lectura o escritura.

Al finalizar el DMA avisa mediante una interrupción. Esta interrupción al igual que el resto de interrupciones son normalmente atendidas al final de cada instrucción. La rutina de servicio asociada comprobará el estado del DMA para ver si se han producido errores al ejecutar la transferencia que se le ha encomendado.
Captura
A diferencia del mecanismo por interrupción convencional, una orden DMA puede transferir muchísimos datos de una sola vez. Por lo tanto, el número de interrupciones por byte transferido es mucho menor que con las interrupciones convencionales: se gana en rapidez y el procesador no se encarga de la transferencia de datos.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s