• Author / Uploaded
• Brayan Zegarra Arana

• Categories
• Caché (Computación)
• Poco
• Unidad Central de procesamiento
• Almacenamiento de datos de la computadora
• Puntero (Programación de computadora)

Citation preview

Capítulo 4: Conexión procesador-memoria 1 (Ejercicios de clase) En un computador el bus de memoria principal es de 100 Mhz y 64 bits de datos. Si el ciclo de lectura del bus necesita dos ciclos de reloj, (a) ¿cuál es el tiempo de acceso que debe tener la memoria para que no se necesiten introducir estados de espera? (b) Suponga que quiere cargar desde la memoria una línea de cache consituida por 64 bytes ¿Cuál es la ganancia en ancho de banda que se obtiene si se utiliza acceso en modo 'burst' con relación a acceso palabra a palabra si el tiempo de acceso de la memoria es de 45 ns.? Solución. Puesto que la frecuencia del bus es de 100 MHz, el tiempo de ciclo es de 1/100*106 sg = 10 / 109 sg = 10 nsg (a) Dado que el tiempo de ciclo de lectura del bus necesita dos ciclos de reloj, el tiempo de acceso de la memoria, para no tener que introducir estados de espera en una lectura, es igual a 2 * Tciclo_de_bus = 2 * 10 nsg = 20 nsg (b) Puesto que el bus tiene 64 bits de datos, es decir 8 bytes, para acceder a 64 bytes se necesitarían 8 accesos a memoria. Si el tiempo de acceso a la memoria es de 45 nsg, se necesitarían 5 ciclos de reloj (45/10 = 4.5, siendo 5 el menor número entero mayor o igual a 4.5). Por lo tanto, habría que introducir 3 ciclos de espera (de 10 nsg cada uno) puesto que los 20 nsg que constituyen el tiempo de ciclo de bus mínimo no son suficientes para que la memoria proporcione el dato. Si se puede utilizar un modo burst que permita leer una línea completa para introducirla en la cache se tendría que el número de ciclos necesario es 5-1-1-1-1-1-1-1 (cinco ciclos para acceder a la primera palabra, y luego un ciclo para acceder a cada una de las restantes), se necesitarían por tanto 12 ciclos = 12 * 10 nsg = 120 nsg → Ancho de Banda (Burst) = (64*8) bits / 120 nsg Si no se utiliza el modo burst se necesitan 5 ciclos por cada uno de los 8 accesos, es decir 5*8 ciclos = 40 * 10 nsg = 400 nsg → Ancho de Banda (No Burst) = (64*8) bits / 400 nsg Por lo tanto, la ganancia en ancho de banda es S (Ancho de Banda)= Ancho de Banda(Burst) / Ancho de Banda (No Burst) = 400/120 = 3.33

2 (Ejercicios de clase) Un computador dispone de un procesador de 64 bits y utiliza una memoria cache de correspondencia directa de 64 Kbytes y una memoria principal de 32 Mbytes. (a) Indique la posición de cache que ocupa la instrucción que se encuentra en la dirección 110AB48h teniendo en cuenta que cada línea es de 128 bytes.(b) ¿Y si, con los mismos datos, la memoria cache fuese asociativa por conjuntos de 4 vías?

Solución. Como la memoria principal es de 32 Mbytes, una dirección de memoria es de 25 bytes (32 Mbytes = 225 bytes), y como la memoria cache es de 64 Kbytes, las direcciones de cache tienen 16 bytes (64 Kbytes = 216 bytes). Teniendo en cuenta que las líneas son de 128 bytes, los 7 bytes menos significativos son los que permiten direccionar los bytes dentro de una línea (128 bytes = 27 bytes). Según esto, el número de líneas de la cache es 6 4 ( K b y te s / c a c h e ) 2 16 (b y te s / c a c h e )  7  2 9 ( lin e a s / c a c h e ) 1 2 8 (b y te s / lin e a ) 2 (b y te s / lin e a ) por lo que se necesitan 9 bits para designar una línea. (a) Si la memoria cache es de correspondencia directa, los 7 bits menos significativos de la dirección indican la posición del byte dentro de la línea (esto es así en cualquier organización de cache, puesto que, al transferirse líneas completas entre cache y memoria, la correspondencia se establece entre líneas), los siguientes 9 bits indican la línea de cache en donde se almacena la línea de memoria principal, y los restantes 9 bits van al campo de marca para poder identificar la línea concreta de memoria principal que se ha introducido en la línea de cache en cuestión. En la figura se esquematiza la situación de los bits:

25 9

Marca

9

Memoria Principal

7

Línea 9

Byte 7

Memoria Cache

16 Así pues, la dirección es 110AB48h = 1 0001 0000 1010 1011 0100 1000 donde los 16 bits recuadrados constituyen la dirección de cache: los 7 menos significativos (señalados en gris) corresponden a la dirección de byte dentro de la línea los 9 siguientes indican la línea de cache donde está la información. Los 9 bytes más significativos (no recuadrados) son los que se introducen en el campo de marca. Por tanto: Posición en la cache: AB48h Campo de marca: 110h (con 9 bits) (b) Si la memoria cache fuese asociativa de 4 vias, las líneas estarían agrupadas en conjuntos de cuatro, por lo que el número de conjuntos sería 29 / 22 = 27 conjuntos.

Así, al establecerse la correspondencia entre líneas de memoria y conjuntos de cache, se necesitarían 7 bits de memoria principal para indicar el conjunto, y se introducirían 11 bits (los 11 bits más significativos) en el campo de marca. Para completar la dirección de cache faltarían 2 bits (4 vías = 22) que se determinan según la política de asignación que se implemente en la memoria

25 11

Marca

7

Memoria Principal

7

Byte

Conjunto 7

2

7

Memoria Cache

16 asociativa donde se introducen los campos de marca. Así pues, la dirección se obtendría a partir de la dirección de memoria principal 110AB48h = 1 0001 0000 1010 1011 0 100 1000 donde se han señalado en gris los 7 bits que indican el conjunto. Los 7 bits memos significativos (recuadrados en blanco) indican la posición dentro de la línea, y los 11 bits más significativos se introducen en el campo de marca. Según esto, la dirección en cache sería: 1010 110X X100 1000 donde los bits marcados con XX tienen el valor que se les asigne al copiar la línea en caché según la política de asignación y la ocupación de líneas en el conjunto (puede asignársele la línea 0, 1, 2, o 3 del conjunto). Si, por ejemplo se le asigna la línea 1 del conjunto, el valor de esos bits sería 01 y tendríamos que Posición en la cache: 1010 1100 1100 1000 = ACC8h Conjunto: 101 0110 = 56h (con 7 bits) Campo de marca: 100 0100 0010 = 442h (con 11 bits)

3 (Ejercicios de clase) En un computador basado en el Pentium II (caches internas asociativas por conjuntos de 2 vías, de 16 Kbytes para datos, y de 16 Kbytes para instrucciones) que dispone de una memoria cache de segundo nivel de 256 Kbytes asociativa por conjuntos de 4 vias, y una memoria principal de 64 Mbytes. Indique las posiciones que ocupa en las memorias caches una instrucción de programa que se encuentra en la posición de memoria 12AAC4h. (Nota: cada línea tiene 32 bytes) Solución. Los bits que constituyen las direcciones en cada una de las memorias son: Memoria principal: 64 Mbytes = 226 bytes (26 bits de los 32 que genera el procesador)

Memoria Cache L1(2 vías): 16 Kbytes = 214 bytes (14 bytes de dirección) Memoria Cache L2 (4 vías): 256 Kbytes = 218 bytes (18 bytes de dirección) Como cada línea tiene 32 bytes, para direccionar un byte se necesitan 5 bits (32 = 25) Cache L1) De los 14 bits de dirección, los 5 menos significativos corresponden a la posición dentro de la línea de cache, y quedan 9 bits que indican la dirección de línea (hay 2 9 = 512 líneas). Como es una cache asociativa de 2 vías, existirán 29 /2 = 28 conjuntos (256 conjuntos). De esta forma, en la dirección de memoria principal, los bits más significativos se introducen en el campo de marca, los 8 bits siguientes indican el conjunto en el que se introduce la línea, y los 5 bits menos significativos corresponden a la posición de byte dentro de la línea. 8

Marca

Memoria Principal

5

Byte

Conjunto 8

1

5

Memoria Cache

14 Así, en la posición de memoria: 12AAC4h = 1 0010 1010 1010 1100 0100 los 8 bits remarcados en gris indican el conjunto en el que se introduce la línea, y los 5 menos significativos indican la posición de byte dentro de la línea. Eso significa que la dirección en cache será 01010110X00100 donde el valor de X se fijará en el momento en que se introduce la línea en cache, según el estado de ocupación de las dos líneas del conjunto y de la política de asignación. Si suponemos que se le asigna el conjunto 0 se tiene que: Dirección en cache: 01 0101 1000 0100 = 1584h (con 14 bits) Conjunto: 0101 0110 = 56h (con 8 bits) Marca: 10010101 Cache L2) De los 18 bits de dirección, los 5 menos significativos corresponden a la posición dentro de la línea de cache, y quedan 13 bits que indican la dirección de línea (hay 2 13 = 8K líneas). Como es una cache asociativa de 4 vías, existirán 213 /22 = 211 conjuntos (2K conjuntos). De esta forma, en la dirección de memoria principal, los bits más significativos se introducen en el campo de marca, los 11 bits siguientes indican el conjunto en el que se introduce la línea, y los 5 bits menos significativos corresponden a la posición de byte dentro de la línea.

11

Marca

Byte

Conjunto 11

Memoria Principal

5

2

5

Memoria Cache

18 Así, en la posición de memoria: 12AAC4h = 1 0010 1010 1010 1100 0100 los 11 bits remarcados en gris indican el conjunto en el que se introduce la línea, y los 5 menos significativos indican la posición de byte dentro de la línea. Eso significa que la dirección en cache será 10101010110XX00100 donde el valor de XX se fijará en el momento en que se introduce la línea en cache, según el estado de ocupación de las dos líneas del conjunto y de la política de asignación. Si suponemos que se le asigna el conjunto 00 se tiene que: Dirección en cache: 10 1010 1011 0000 0100 = 2AB04h (con 18 bits) Conjunto: 101 0101 0110 = 556h (con 11 bits) Marca: 10010

4 (Ejercicios de clase) En un computador, la cache interna del procesador tiene un tiempo de acceso de 2.5 ns. y una tasa de aciertos del 80%, y la memoria principal tiene un tiempo de acceso de 10 ns. Suponga que dispone de una memoria cache SRAM con un tiempo de acceso de 5 ns. ¿Qué tasa de fallos ha de tener para que el tiempo de acceso medio a memoria se reduzca con respecto a la situación anterior? ¿Es posible obtener un tiempo de acceso medio de 3.7 ns.?¿Cuál es el mínimo tiempo de acceso medio que se puede conseguir?. (Nota: Considere que las memorias cache son 'Look-though'). Solución. El tiempo medio de acceso al sistema de memoria constituido por la memoria cache interna (L1) y la memoria principal DRAM es igual a: T(L1-DRAM) = a1 * t1 + (1-a1)*(t1+tDRAM)= 0.8 * 2.5 + (1-0.8) (2.5 + 10) nsg = 4.5 nsg donde a1 es la tasa de aciertos de la memoria L1, t1 es el tiempo de acceso de la memoria cache L1, y tDRAM el de la memoria principal. Se ha supuesto que el dato buscado siempre está en la memoria principal y que la memoria cache es del tipo look-trough. En el caso de un sistema de memoria con dos niveles de memoria cache, en el que existe una memoria implementada con celdas SRAM que constituye el nivel de cache externa L2, se tiene que, si a2 es la tasa de aciertos de la memoria cache L2 (que se supone también de tipo look-through), el tiempo medio de acceso es igual a: T(L1-L2-DRAM) = a1 * t1 + (1-a1)* a2 * (t1+t2) + (1-a1)*(1-a2)*(t1+t2+tDRAM)=

= 0.8 * 2.5 + (1-0.8) * a2 * (2.5 + 5) + (1-0.8) *(1-a2)*(2.5 + 5 + 10) = = 3.5 + 2 * (1-a2) De esta forma, para que T(L1-L2-DRAM) < T(L1-DRAM) es preciso que 3.5 + 2 * (1-a2) < 4.5

→ (1-a2) < 0.5 → 0.5 < a2

Es decir, que la memoria cache L2 tiene que tener una tasa de aciertos mayor del 50%. Teniendo en cuenta que T(L1-L2_DRAM) = 3.5 + 2 * (1-a 2), si se quiere que T(L1-L2_DRAM) se igual a 3.7 se debe cumplir que 3.7 = 3.5 + 2 * (1-a2) → (1-a2) = 0.2/2 → a2 = 0.9 El tiempo de acceso mínimo correspondería a la situación en la que a2 = 1 (siempre que se busca un dato en L2 se encuentra allí): T(L1-L2-DRAM) = 3.5 nsg. Es el mismo valor que se obtendría si en la expresión del tiempo, T(L1-DRAM), para el sistema de memoria de dos niveles se hiciera el tiempo de acceso a la DRAM igual al tiempo de acceso a la memoria cache L2.

5 (Ejercicios de clase) Un microprocesador incluye una CPU de 32 bits y caches separadas para datos e instrucciones, de 4 Kbytes cada una, con líneas de 32 bytes, y organizadas como caches asociativas por conjuntos de dos vías. El tiempo de acceso a la memoria cache es de 5 ns, la política de reemplazo es LRU (se reemplaza la línea que lleve más tiempo sin utilizarse), y la de actualización es de post-escritura (write-back). El microprocesador está conectado a las memorias externas separadas para datos e instrucciones mediante dos buses independientes de 100 MHz y 64 líneas de datos cada uno, con un tiempo de acceso de 50 ns y ciclos burst 5-1-1-1. Se está ejecutando un programa en el que la secuencia de instrucciones que se encuentran en los bytes 0 a 1FFFh constituyen un bucle que se repite 30 veces, y tras ellas existe una secuencia de instrucciones que ocupa desde el byte 2000h hasta el 2FF8h, y que se ejecuta una vez. En el 60% de las instrucciones del programa, se hace referencia a un dato, ocasionándose un total de 500 fallos en el acceso a estos datos. (a) Suponiendo que las caches están inicialmente vacías ¿Cuál es la tasa de aciertos para el acceso a los datos y a las instrucciones en el programa?. (b) ¿Cuál es el tiempo medio de acceso a la memoria de instrucciones? (c) ¿Cuál es el tiempo medio de acceso a la memoria de datos si el 20% de los fallos por acceso a datos dan lugar a reemplazo de la línea con actualización de la línea reemplazada en memoria? Solución. (a)Empezaremos situando las líneas del programa en las líneas de la cache interna para instrucciones para determinar los fallos de cache que se producen al acceder a las instrucciones. Como la cache de instrucciones tiene 4 Kbytes (212 bytes), con líneas de 32 bytes (25 bytes), habrá 212/25=128 líneas, y como las líneas se agrupan en conjuntos de dos líneas, 128/2=64 (2 6=64)

conjuntos. Por lo tanto, los bits 0-4 indican el byte dentro de la línea, y los bits 5-10 el conjunto al que van las líneas de memoria principal. Para determinar el número de fallos en la cache de instrucciones hay que tener en cuenta que el bucle tiene 8Kbytes, y que al empezar en la posición 0h , las líneas se empiezan a cargar en cache desde el conjunto 0 (los bits 5 a 10 son 0). Así, los primeros 4 Kbytes (128 líneas) se pueden situar en los 64 conjuntos de dos vías de la cache ocasionando 128 faltas. Las líneas de los restantes 4 Kbytes del bucle tendrán que ir reemplazando las líneas ya cargadas, ocasionando otros 128 fallos. En total, la iteración del bucle ocasionará 256 fallos. Estos 256 fallos se generarán en cada una de las 30 iteraciones puesto que los primeros 4 Kbytes de cada iteración tienen que situarse en las líneas de cache ocupadas por los últimos 4 Kbytes de la iteración anterior, etc. Por lo tanto, el número de fallos en el bucle es 256*30= 7680. Las secuencia de instrucciones que vienen a continuación ocupen menos de 4 Kbytes, y se podrán introducir en la caché. Como los bits 5 a 10 de la posición 2000h son cero, las líneas de la secuencia se empiezan a cargar desde el conjunto 0. Se producirán tantos fallos como líneas haya en la secuencia. El número de líneas de la secuencia se obtiene desplazando las direcciones de comienzo y final cinco bits a la derecha (las líneas son de 32 bytes) y restando los datos resultantes. El resultado que queda es 1111111=7Fh, por lo tanto desde la línea 0 a la 7Fh hay 128 líneas. Es decir, se producen 128 fallos en la secuencia final del programa. El número de fallos totales ocasionados por el programa es 7680+128= 7808 Como el número de instrucciones del programa es (30*(8*210)+4088)/4 = 62462 (una instrucción de 32 bits son 4 bytes). Por lo tanto, la tasa de fallos es de 7808/62462 = 0.125, y la tasa de aciertos a la cache de instrucciones es 0.875. En cuanto a la tasa de fallos de la memoria cache de datos, se tiene que como el número de instrucciones es 62462, y como se generan accesos a datos en un 60%, el número de accesos a la memoria cache de datos es 0.6*62462= 37477. Como se producen 500 fallos, la tasa de fallos es 500/37477= 0.013, y la tasa de aciertos es de 0.987 (b) El tiempo medio de acceso a la memoria cache de instrucciones es Tacceso  a cachet cache  (1  a cache )(t cache  t memoria )

donde: -

acache es la tasa de aciertos de la cache (acache= 0.875) tacceso_cache es el tiempo de acceso a una palabra de la cache interna (tcache=5 ns). tacceso_memoria es el tiempo de acceso a una palabra en memoria: t memoria=50 ns. Cada ciclo de bus es de 10 ns (el bus es de100 MHz), y para acceder a una palabra se necesitan 5 ciclos.

Sustituyendo, se tiene que Tacceso = 0.875*5 + 0.125*(5+50) = 11.25 ns (c) Para calcular el tiempo medio de acceso a la memoria de datos hay que tener en cuenta el tiempo de acceso a cache, y a la memoria principal en el caso de fallo de cache. La expresión es:

Tacceso  a cache t cache  (1  a cache )(t cache  t memoria  p reemplazo .t linea )

donde: acache es la tasa de aciertos de la cache (acache= 0.987) tcache es el tiempo de acceso a una palabra de la cache interna (tcache=5 ns). tmemoria es el tiempo de acceso a una palabra en memoria (tmemoria=50 ns) tlinea es el tiempo de actualización de una línea en memoria principal cuando debe reemplazarse dicha línea en memoria cache. Este tiempo de actualización corresponde al de un acceso burst a la memoria principal, es decir 5 + 1 + 1 + 1 = 8 ciclos de bus (t linea=8*10 ns =80 ns). preemplazo es la frecuencia con la que se producen reemplazos de línea. Como en el 20% de los fallos hay necesidad de reemplazo, se tiene que preemplazo=0.2. Sustituyendo los correspondientes valores, se tiene que Tacceso = 0.987*5.0 ns + (1-0.987) * (5.0 ns + 50.0 ns +0.2 * 80.0 ns) = 5.793 ns

6 (Ejercicios de clase) En un computador el bus tiene una frecuencia de 200 MHz, y la memoria principal un tiempo de acceso de 30 ns, que, tras el primer acceso, puede proporcionar (o recibir) una palabra por ciclo en los ciclos burst. El procesador superescalar de 1GHz dispone de una cache interna con líneas de 4 palabras. En los programas, por término medio, un 30% de las instrucciones necesitan leer o escribir un dato (una palabra) en memoria., la tasa de aciertos de la cache interna es del 90%, y, en un 20% de los accesos a datos se necesita reemplazar el bloque, en caso de que se haya producido un fallo. (a) ¿Cuál es el tiempo medio de acceso a la memoria? (b) ¿Cuántas instrucciones por ciclo se pueden ejecutar, por término medio, en el procesador?¿y si la tasa de fallos pasa a ser de un 95%? Solución. (a) Para calcular el tiempo medio de acceso a memoria hay que tener en cuenta el tiempo de acceso a cache, y a la memoria principal en el caso de fallo de cache. La expresión es: Tacceso  acachetacceso _ cache  (1  acache )(t acceso _ cache  tacceso _ memoria  preemplazo .t acceso _ linea )

Donde: acache es la tasa de aciertos de la cache (acache= 0.9) tacceso_cache es el tiempo de acceso a una palabra de la cache interna (tacceso_cache=tciclo=1/109=1ns). tacceso_memoria es el tiempo de acceso a una palabra en memoria (tacceso_memoria=30 ns) tacceso_linea es el tiempo de actualización de una línea en memoria principal cuando debe reemplazarse dicha línea en memoria cache. Como una línea está constituida por cuatro palabras, el tiempo de actualización corresponde al del tiempo de un acceso burst a la memoria principal, es decir 6 + 1 + 1 + 1 = 9 ciclos de bus (tacceso_linea=9*5 ns =45 ns). preemplazo. Dado que habrá un reemplazo de línea en un 20% de los accesos a datos y que el 30% de las instrucciones acceden a datos, para un programa de N instrucciones tenemos: preemplazo  0.2 

0.3 * N 0.3  0.2   0.046 N  0.3 * N 1.3

Sustituyendo los correspondientes valores, se tiene que Tacceso = 0.9*1.0 ns + (1-0.9) * (1.0 ns + 30.0 ns +0.046 * 45.0 ns) = 4.207 ns (b) Se puede estimar el ancho de banda del procesador teniendo en cuenta que, si se ejecutan N instrucciones en el procesador, se realizarán (además de los N accesos para las instrucciones) 0.3N accesos para (leer/escribir) palabras de datos. Por lo tanto, Número de Palabras que se captan = N + 0.3N = 1.3N El tiempo para ejecutar esas instrucciones en el procesador superescalar es, por término medio, Tiempo de Ejecución en el Superescalar = (tciclo_procesador N)/b = 1.0N/b ns donde b es el número de instrucciones por ciclo que ejecuta el procesador. El ancho de banda que requiere el procesador es B procesador 

1.3N b  1.3b( palabras / ns) 1.0 N

Para determinar el valor de b se iguala el ancho de banda del procesador y el ancho de banda que proporciona la memoria, Bmemoria, que se obtiene a partir del tiempo de acceso medio a la memoria, calculado en el anterior apartado Bmemoria = 1/4.207 (palabras/ns): b = 1/(4.207*1.3) = 1/5.469 = 0.18 Como puede verse, b es menor que 1. Por lo tanto, el ancho de banda que proporciona la memoria no sería suficiente ni siquiera para que el procesador pueda funcionar como procesador segmentado (ejecutando una instrucción por ciclo). En el caso de que la tasa de fallos de cache fuese del 95%, el tiempo de acceso medio a la memoria sería (utilizando la misma expresión que en el apartado anterior): Tacceso = 0.95*1.0+0.05*33.07 = 2.603 En este caso, el ancho de banda de la memoria es Bmemoria =1/2.603 = 0.38 (palabras/ns). Como se puede observar, se ha producido una mejora de un factor de 1.61: un aumento de un 5% en la tasa de fallos ha ocasionado una mejora de aproximadamente un 60% en el ancho de banda. El valor de b aumenta, pero, en cualquier caso sigue siendo menor que la unidad: b = 1/(2.603*1.3) = 0.295 Si queremos aprovechar las capacidades superescalares del procesador no habría más remedio que incrementar el ancho de banda de la memoria. Una estrategia para conseguir ese incremento en el ancho de banda de la memoria es incrementar el número de palabras que se traen desde la memoria cache interna en cada acceso a la misma (de hecho, esta es la alternativa usual en los procesadores superescalares). Al estar la memoria cache integrada en el mismo chip que el procesador, no hay problema por las posibles limitaciones en el número de terminales. Si el procesador es capaz de ejecutar tres instrucciones por ciclo (b=3), el ancho de banda del

procesador es Bprocesador=1.3*3 palabras/ns = 3.9 palabras/ns. Para que el ancho de banda de la memoria sea igual, se leerán/escribirán W palabras en cada acceso, donde: 3.9 (palabras/ns) = W/2.603 (palabras/ns)  W = 3.9 * 2.603 = 10.1 palabras  11 palabras Si este número es demasiado elevado para la tecnología disponible, no habría más remedio que mejorar el tiempo medio de acceso a la memoria (mayor tasa de aciertos, memorias más rápidas, etc.), o el rendimiento del procesador se verá limitado por la memoria.

7 (Ejercicios de clase) Tiene una aplicación de procesamiento de señal que debe repetir 3000 veces el cálculo a(i)= f(a(i),a(i+1), a(i+2),a(i+3)) para cada muestra de la señal a(i) (i=1,..,2 20-3) que ocupa 4 bytes, y f() es una función determinada. El código que permite implementar el cálculo está constituido por 12 instrucciones de 32 bits que se repiten para cada muestra. De las instrucciones, 4 son de acceso a memoria para leer/escribir datos, 4 son instrucciones de operaciones aritméticas, y 4 son de control del bucle, actualización de punteros, etc. Suponga un computador que dispone de un procesador superescalar que funciona a 1 GHz. y que puede terminar hasta 3 instrucciones por ciclo, con una memoria cache interna para datos y otra para instrucciones de 64 KBytes cada una, mapeo directo, líneas de 32 bytes, y tiempo de acceso de un ciclo de reloj. La memoria cache de datos utiliza política de actualización de post-escritura (write-back). La memoria principal de 256 MBytes tiene un tiempo de acceso de 50 ns. y se conecta a través de un bus de 64 bits a 100 MHz. que utiliza ciclos burst 5-1-1-1 para transferir las líneas de cache. Si la señal está almacenada en memoria a partir de la posición 0h, y el código está alineado con una línea de cache: (a) Realice una estimación del tiempo mínimo que tardaría en ejecutarse la aplicación. (b) Si se utiliza un compilador que es capaz de reducir el número de instrucciones de acceso a memoria, (pasando de 4 a 1 instrucciones de acceso a memoria por muestra) ¿Cuál sería ahora el tiempo mínimo estimado?. Solución: En primer lugar evaluaremos el tiempo que consumiría el procesador si funcionase a pleno rendimiento: Número de Instrucciones  3000*220*12 Considerando 3 instrucciones/ciclo y una frecuencia de reloj de 109 ciclos/sg, se tiene que: Tprocesador = (Número de Instrucciones)/((Instrucciones/ciclo)*(ciclos/sg))= (3000*220*12)/(3*109) = 12.58 sg. A continuación vamos a estimar el tiempo que requeriría el acceso a memoria, para ver si es menor que el del procesador o no, ya que el mayor de los tiempos es el que nos permitirá estimar el tiempo mínimo de procesamiento. Faltas de cache: -

En el acceso al código se produce una primera falta, que se puede despreciar en el cómputo final de tiempo (las debidas a los accesos a los datos son muchas más, como veremos).

-

En el caso del acceso a los datos tenemos que el volumen de datos es aproximadamente de 4 Mbytes (220-3 datos de 4 bytes cada uno), es decir 222/25 =217 líneas. La cache de datos tiene 64 Kbytes y las líneas son de 32 bytes, el númer tiene 216/25=211 líneas.

Por lo tanto, como no cabe la señal entera en la cache, y dado que se va leyendo ordenadamente, se producirán tantas faltas como líneas ocupa la señal, para cada acceso a la misma (cada una de las 3000 iteraciones). El número de accesos a datos a los que da lugar el programa, por cada una de las 3000 iteraciones es: Accesos a datos = 4*(220-3) 4*220 Por lo tanto la probabilidad de fallo es: (1-a) = 217 /4*220 = 0.0313 y por lo tanto a = 1-0.0313 = 0.96875 Dado que hay reemplazo en todas los casos de falta excepto para las primeras 2 11 líneas, la probabilidad de reemplazo es: preemplazo= 1- (211/3000*217) = 0.99 Esto significa que el tiempo de acceso a memoria es:

t a c c e s o  t c a c h e  a  ( t c a c h e  t m e m o r ia  p r e e m p la z o  t r e e m p la z o )  ( 1  a ) Por lo tanto: tacceso= 1*0.96875 + (1+50+0.99*8*10)*0.0313= 5.04 nsg. y el tiempo para acceder a todos los datos será: Tmemoria= 4*3000*(220-3)*5.04  60.48 sg b) Si el número de accesos pasa a ser 1, los tiempos pasarán a ser: Tmemoria= 3000*(220-3)*5.04  60.48/4= 15.12 sg Tprocesador = (9*220)/(109) = 9.4 sg. Como vemos, sigue siendo la memoria la que más tarda, y la que mejor aproximaría el tiempo mínimo. No obstante, como se puede comprobar, las diferencias entre los tiempos se han reducido bastante.

8 (Benchmark diciembre 2007) Suponga que siguiente programa for (i=0 ; i