Ecm2

(2.4) MEMORIAS ENTRELAZADAS: Idea: dividir la mem. en MODULOS independientes con para tener acceso simultaneao a varias palabras en diferentes modulos (entrelazamiento) • CONDICION DE EFICIENCIA: las referencias a mem. se distribuyen equitativamente entre modulos,siendo clave dicha distribucion • SITUACION IDEAL: el ancho d banda d acceso a mem. se multiplica por el nº d modulos • Memoria Total = N = 2ⁿ palabras // Nº de Modulos = M = 2^m.  ESQUEMAS - son 2 y con cualquiera de ambos se puede obtener M palabras en paralelo pa cada acceso a memoria. Existe conflicto d memoria --> varias dir. requieren ala vez un acceso al mismo modulo reduciendo la velocidad de acceso. Los conflictos de memoria son mayores en orden superior debido ala secuencialidad d los programas. En sistemas multiprocesador es a veces mejor el entrelazamiento superior cuando las tareas son disjuntas o interaccionan poco entre si (lo cual no es siempre cierto). Se suele usar el entrelazamiento d orden inferior. 1)ENTRELAZAM. DE ORDEN SUPERIOR (consecutivo): dir. fisica: n bits • Al i-esimo modulo le corresponden las dir. consecutivas i·2^{n - m} hasta (i+1)·2^{n - m}-1 • Los m bits + significativos identifican el modulo y el resto un desplazamiento dentro del modulo • Ventajas: expandibilidad y fiabilidad (un fallo se restringe a un area localizada del espacio d dir.) 2)ENTRELAZAM. DE ORDEN INFERIOR (ciclico): en el i-esimo modulo se almacenaran las dir. d la forma K·M+i con k=0,1,...,2^{n - m}-1 (espaciamiento M entre ellas) • Los m bits - significativos de la dir. fisica seleccionan el modulo y el resto la posicion dentro del modulo (2a) Con Laches en la Salida: en cada acceso son leidas M palabras consecutivas --> K·M+i con i=0,1,...,M-1. Se almacenan en latches y son transferidas en serie por un MUX. Las palabras son leidas en el siguiente ciclo --> mecanismos d anticipacion. En el mejor caso el tiempo d acceso se reduce a M. Es ideal para accesos a mem. secuenciales. Baja su eficiencia en programas no secuenciasles (saltos) y pa solucionarlo se pueden diseñar sistemas con latches ala entrada (2b) Con Latches a la Entrada: cada modulo puede usar una dir. relativa particular. Necesita controlador de mem. pa procesar las peticiones 1a1 secuencialmente. Si una peticion encuentra el latch ocupado por otra previa, es retardada (T.3)  MEMORIA CACHE - Objetivo: lograr una memoria rapida e ilimitada • Principio de localidad: los programas acceden a una parte relativamente pequeña d su espacio de direcciones en cualquier instante d tiempo --> a) loc. temporal: si un elemento es referenciado volvera a ser referenciado pronto (bucles) b) loc. espacial: si un elemento es referenciado, los elementos cuyas dir. esten proximas tenderan a ser refeenciados pronto • Aprovechando el principio de localidad se implementa la mem. d un computador como una jerarquia d mem. presentado al usuario tanta mem. disponible como sea posible en la tecnologia + barata mientras se proporciona el acceso a la velocidad ofrecida por la mem. + rapida • En nuestra jerarquia de mem. el nivel + alto para nosotros sera la mem. cache dejando los registros d lado aparte. Un nivel mas cercano al procesador es un subconjunto de cualquier nivel mas apartado y todos los datos stan almacenados en el nivel mas bajo, ubicandose la info. en cada nivel de acuerdo a su probabilidad de uso (3.1) INTRO. A LAS CACHES: el termino --> Conti, Gibson y Pitkowsky (1968). 1º computador comercial con cache: IBM 360/85 (1968) • La cache es una memoria pequeña y rapida q se situa entre el procesador y la mem. principal • Almacena la info. actualmente en uso d la mem. principal • La gestion d la cache es similar ala gestion d mem. virtual • El principio d localidad justifica el exito d la cache • BLOQUE (linea cache): unidad minima d transferencia d info. entre un niver superior y otro inferior • ACIERTO: la info. requerida aparece en el nivel superior • FALLO: la info. no se encuentra en el nivel superior y es necesario acceder al inferior • TASA DE ACIERTOS: fraccion d accesos a mem. encontrados en el nivel superior • TASA DE FALLOS: fraccion d accesos a mem. no encontrados en el nivel superior (1-tasa de aciertos) • PENALIZACION DE FALLO: tiempo necesario pa sustituir un bloque del nivel superior por el del nivel inferior, mas tiempo para entregar ste bloque al procesador. Se divide en: a)tiempo de acceso --> tiempo pa acceder a la 1ª palabra dun bloque en un fallo b) tiempo de transferencia --> tiempo adicional pa transferir las restantes palabras del bloque • Tiempo d acierto < Penalizacion d fallos (3.2) OPERACION DE UN SISTEMA CACHE: al bloque d una cache se le llama linea • ESTRUCTURA DE UNA CACHE: Directorio --> contiene info. sobre las lineas d la zona d almacenamiento. Zonas de almacenamiento --> contiene copia de algunas lineas d la mem. principal • El directorio contiene un conjunto d etiquetas pa identificar si una palabra d la cache se correspond con la palabra buscada --> ad+ necesitamos alguna forma d reconocer si un bloque d cache no tiene info. valida (bit de validez: a 0 indica info. no valida) UBICACION DE LINEAS - 3 categorias de organizacion cache (n lineas): 1)CORRESPONDENCIA DIRECTA: cada linea tiene un unico lugar donde puede aparecer en la cache (campos--> etiqueta, linea d la cache (log₂n --> tamaño indice), palabra dentro d la linea, byte d palabra.• 1 via n conjuntos 2)TOTALMENTE ASOCIATIVA: cada linea puede star en cualquier parte d la cache (campos--> etiqueta, palabra dentro d la linea, byte d palabra) • n vias, 1 conjunto 3)ASOCIATIVA POR CONJUNTOS DE m VIAS: a cada linea le corresponde un conjunto de m lineas d la cache ( nº d conjuntos=n/m=c ) • campos--> etiq,indice conjunto (log₂c), palabra dentro d la salida, byte d palabra

 BUSQUEDA DE LINEAS - Indice: selecciona un conjunto d la cache • Etiqueta: se compara simultaneamente con todas las etiquetas del conjunto seleccionado • El bit de validez nos indica si la entrada contiene una dir. valida • Aumentar la asociatividad incrementa el tamaño d la etiqueta REEMPLAZO DE LINEAS -  Tenemos q establecer criterio pa reemplazar lineas en un fallo cache d la cache • En correspondencia directa: una unica posibilidad • En asociativa por conjuntos o totalmente asociativa: hay q escoger una linea entre las de un conjunto o entre todas las d la cache, respectivamente • Principales estrategias: 1)Aleatoria: se hace una eleccion aleatoria (facil de implementar) 2)Menos recientemente usado (LRU): el bloque sustituido es el q hace + tiempo q no es usado OPERACION DE ESCRITURA-  2 opciones basicas pa escribir en cache: 1)Escritura directa: la info. se escribe en la cache y en la memoria d nivel inferior. Ventajas: facil de implementar (detencion de la UCP en la escritura --> buffer d escritura), fallos de lectura menos costosos y la mem. del nivel inferior esta siempre actualizada 2)Postescritura: solo se escribe en la cache y cuando se reemplaza la linea se escribe en memoria. Ventajas: escritura a la velocidad d la cache, multiples escrituras en una linea implican una sola escritura d la linea completa en la memoria, - ancho d banda d memoria y se puede hacer uso efectivo del ancho d nivel + bajo • Bit de modificacion: bit de estado q se usa en postescritura pa indicar si una linea se ha modificado o no. Reduce la frecuencia de escritura ante reemplazos d linea, ya q si la linea no se ha modificado no hace falta escribirla en mem. • Opciones en un fallo de escritura: 1)Ubicar en escritura o busqueda en escritura: la linea se carga y siguen las acciones de acierto de escritura (en postescritura). Se busca q las escrituras subsiguientes en la linea no provoquen fallos. 2)No ubicar en escritura o evitar escritura: la linea se modifica en el nivel inferior y no se carga en la cache (escritura directa). Las escrituras subsiguientes en la linea provocaran escrituras a memoria. (3.3) RENDIMIENTO DE LA CACHE: TiempoMedio_{AccesoMemoria}=Tiempo_acierto + (Tasa_Fallos x Penalizacion_Fallo) • Tiempo_CPU=(Ciclos_EjecucionCPU + Ciclos_{DetencionMemoria}) X Tiempo_CicloReloj • Para simplificar asumiremos q todas las detenciones son debidas a la cache e incluiremos los ciclos de reloj de los aciertos como ciclos de reloj de ejecucion CPU --> Ciclos_{DetencionMemoria}=[(Lecturas/Programa) x Tasa_{FallosLectura} x Penalizacion_{FallosLectura}] + [(Escrituras/Programa) x Tasa_{FallosEscritura} x Penalizacion_{FallosEscritura}  • Combinando las lecturas y escrituras simplificamos --> Ciclos_{DetencionMemoria}=(AccesosMemoria/Programa) x Tasa_Fallos x Penalizacion_Fallos • Factorizando el recuento de instrucciones (IC) --> Tiempo_CPU=IC x [CPI_Ejecucion + (AccesosMemoria/Instruccion) x Tasa_Fallos x Penalizacion_Fallos] x Tiempo_CicloReloj • Si consideramos la tasa de fallos como fallos por instruccion --> T_CPU= IC x [CPI_ejecucion + (Fallos/Instruccion) x Penalizacion_Fallos] x Tiempo_CicloReloj • El comportamiento de la cache tiene gran influencia en el rendimiento. En una CPU con CPI bajo y un reloj rapido tiene un doble impacto: 1)A + bajo CPI, el impacto relativo de los ciclos es + pronunciado 2)Para identicas jerarquias de memoria de dos computadores, la CPU con mayor frec. de reloj usa mayor nº d ciclos en un fallo • En las ecuaciones anteriores hemos supuesto q el tiempo d acierto no es un factor determinante en el rendimiento. En las tecnicas d mejora del rendimiento cache nos fijaremos como objetivo razonable minimizar el TiempoMedio_{AccesoMemoria}, sin embargo debemos tener en cuenta q el objetivo final es reducir el Tiempo_CPU. (3.4) FUENTES DE FALLOS: A)FORZOSOS: el primer acceso a una linea no esta en la cache(llamados tb 'fallos de arranque frio' o 'fallos d primera referencia') B)DE CAPACIDAD: la cache no tiene capacidad suficiente pa contener todas las lineas necesarias durante la ejecucion d un programa C)DE CONFLICTO: ocurren en ubicacion asociativa por conjuntos o de correspondencia directa, cuando una linea es descartada y posteriormente recuperada, si a un conjuntos le corresponden demasiadas lineas (llamados tb 'fallos de colision') /// Caracteristicas del modelo: da una vision del comportamiento medio, no explica fallos individuales y no tiene en cuenta la politica de reemplazo • Muchas tecnicas de reduccion d la tasa d fallos pueden incrementar el Tiempo_Acierto o la Penalizacion_Fallo (3.5) CACHES DE DATOS E INSTRUCCIONES: las caches unificadas o mixtas que contienen instrucciones y datos pueden ser un cuello de botella • La CPU sabe si esta emitiendo la dir. de una instrucc. o dato, pudiendo separar puertos VENTAJAS CACHES SEPARADAS - 1-casi dobla el ancho de banda entre la CPU y la jerarquia de memoria. 2-optimizacion por separado de cada cache. 3-elimina fallos de conflicto entre instrucc. y datos INCONVENIENTES CACHES SEPARADAS - 1-espacios fijos pa instrucc. y datos --> peor Tasa_Aciertos 2-Inconsistencia: instrucc. y datos en la misma linea, intrucc. modificables (3.6) REDUCCION DE LA TASA_FALLOS: INCREMENTAR EL TAMAÑO DE LA LINEA - reduce los fallos forzoso, puede incrementar los fallos d conflicto y d capacidad, incrementa la Penalizacion_Fallo y la seleccion del tamaño d linea depende d la latencia y del ancho d banda del nivel inferior d la jerarquia d memoria INCREMENTAR LA ASOCIATIVIDAD - reduce los fallos d conflicto. En la practica una cache asociativa por conjuntos de 8 vias es tan efectiva como una totalmente asociativa. Un cache de correspondencia directa tiene aprox. la misma Tasa_Fallos q una cache asociativa por conjuntos de 2 vias d la mitad d tamaño. Puede anumentar 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_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 correspondencia directa)- los subbloques tienen bit de validez. Reduce la Penalizacion_Fallo , reduce el tamaño de la etiqueta y ayuda en los aciertos de escritura escribiendo siempre la palabra