cpu resolución de los ejercicios de la hoja 4 - fdi.ucm.es hoja 4 (sol probl... · curso 2010-2011...

1/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro

Arquitectura e Ingeniería de ComputadoresCurso 2010-2011

Resolución de los Ejercicios de la Hoja 4

Dpto. de Arquitectura de Computadores y AutomáticaFacultad de Informática.

Universidad Complutense de Madrid.

José Miguel Montañana Aliaga.Fernando Castro Rodríguez.Francisco Tirado Fernández.

2/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.4CPI (ciclos por instr.) es de 1.5 con un sistema perfecto de memoriaSuponiendo:

• La latencia de memoria son 40 ciclos.• Las transferencias de bloques se realizan a 4 bytes/ciclo.• El 50% de los bloques son modificados.• El tamaño de bloque es de 32 bytes.• El 20% de las instrucciones son transferencias de datos.• No hay buffer de escritura

a) ¿Cuál sería el CPI para una cache directa unificada con post-escritura de 16KB y tasa de fallos de 0.029?

Si ahora suponemos además la existencia de un TLB tal que:• El fallo de TLB produce una penalización de 20 ciclos.• El acceso al TLB no afecta al tiempo de acierto de cache.• El 0.2% de las referencias no se encuentran en el TLB.

b) Suponiendo acceso a la cache con direcciones virtuales, calcular de nuevo el CPI efectivo teniendo en cuenta el TLB.

c) Suponiendo ahora acceso a la cache con direcciones físicas, volver a calcular el CPI efectivo teniendo en cuenta el TLB.

3/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


CPI= CPI memoria.perfecto + Penalización_media_memoria


Penalización_media_memoria==Media de acceso a memoria por instrucción x tasa fallos x penal_fallo

??? Lo calcularemos ahora

??? Lo calcularemos ahora

0.029

Todas las instrucciones acceden a la cache:• 1 acceso/instrucción• El 20% de las instrucciones acceden a la cache 0,2 accesos por instrucción

1+0.2=1.2

CPI (ciclos por instr.) es de 1.5 con un sistema perfecto de memoria• El tamaño de bloque es de 32 bytes.• El 20% de las inst. son transf. de datos.• No hay buffer de escritura

• La latencia de memoria son 40 ciclos.• Las transf. de bloques son de 4 bytes/ciclo.• El 50% de los bloques son modificados

4/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro





1.2 ??? Lo calcularemos ahora

0.029

Todas las instrucciones acceden a la cache:• 1 acceso/instrucción• El 20% de las instrucciones acceden a la cache 0,2 accesos por instrucción

1+0.2=1.2



5/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro







Penal fallos (ciclos):T. lect/escrit de bloque= latencia+(tamaño bloque/rel transfer)= 40+32/4 = 48 ciclosEl 50% de los bloques están limpios:

Fallo implica lecturamover 1 bloque : 48 ciclosEl 50% de los bloques están escritos:

Fallo implica escritura+lecturamover 2 bloques: 96 ciclosPromedio ciclos por fallo 0,5x48+ 0,5x96=72 ciclos

1.2 ??? Lo calcularemos ahora

0.029

6/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro







Penal fallos (ciclos):T. lect/escrit de bloque= latencia+(tamaño bloque/rel transfer)= 40+32/4 = 48 ciclosEl 50% de los bloques están limpios:

Fallo implica lecturamover 1 bloque : 48 ciclosEl 50% de los bloques están escritos:

Fallo implica escritura+lecturamover 2 bloques: 96 ciclosPromedio ciclos por fallo 0,5x48+ 0,5x96=72 ciclos

1.2 72 ciclos0.029

7/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro







1.2 72 ciclos0.029

Penalización_media_memoria=1.2x0.029x72=2.51

CPI=1.5+2.51=4.01

8/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro



b) Suponiendo acceso a la cache con direcciones virtuales, calcular de nuevo el CPI efectivo teniendo en cuenta el TLB.



El acceso al TLB no afecta al tiempo de acierto en la cacheSólo se accede al TLB en caso de fallo de la cache. Penalización añadida por los fallos del TLB:

(media de acceso a mem. por instr)x(tasa de fallo cache)x(tasa fallo TLB) x20== 1,2 x 0,029 x 0,002 x 20 = 0.0013 inst/ciclo ~ despreciable

9/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro



c) Suponiendo ahora acceso a la cache con direcciones físicas, volver a calcular el CPI efectivo teniendo en cuenta el TLB.



Suponemos acceso con dirección física se accede siempre al TLBPenaliza añadida por fallos TLB:

(media de acceso a mem. por instr)x(tasa de fallo cache)x(tasa fallo TLB) x20== 1,2 x 0,002 x 20 = 0.048 inst/ciclo

CPI=1.5+2.51+0,048=4.058

10/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.5Un computador tiene memorias cache separadas de datos (8KB) e instrucciones (16KB) y las siguientes características:

• La tasa de aciertos de la cache de instrucciones es del 95 %.• La tasa de aciertos de la cache de datos es del 85 %.• El tamaño de bloque de la cache de instrucciones es de 8 bytes y el de la cache de datos es de 4 bytes. En ambos casos, cuando se falla se lee el bloque completo.

La CPU genera 108 referencias a instrucciones y 4x107 a datos por unidad de tiempo(ut).Cada una de estas referencias se suponen de un byte. El 20% de las referencias a datos son escrituras.El 25% de los bloques en la memoria cache de datos son modificados (escritos) durante su permanencia en ella.

Calcular la anchura de banda media necesaria entre memoria principal y memoria cache en los siguientes casos:

a) Con política de escritura directa (con asignación en escritura).b) Con política de post-escritura (con asignación en escritura).

11/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.5DATOS:4 x107 reg/ut 1 reg=1B Bloque:4BTF=0.15 Escritura: 20% Bloques: 25%

INSTRUCCIONES:108 reg/ut 1 reg=1B Bloque:8B TF=0.05

Tráfico Mp Mc (General)Instrucciones: Bytes por ut

(Nº reg/ut)x TF x (nº Bytes/bloque) = 108x0,05x8 = 4x107B/ut

fallos/ut fallos/utDatos: Bytes por ut

(nº reg/ut) x TF (nº Bytes/bloque) = 4 x103x 0,15x4= 2,4x107B/ut

fallos/ut fallos/utTráfico Mc Mp

1. con escritura directa: 1B por cada escritura, haya fallo o no(No reg/ut)x Fracción escritura x 1B = 4x107 x0,2 = 8x106B/uttotal : 4x107 + 2,4x107 + 0,8x107 = 7,2 x107B/ut

2. con post-escritura: 1 bloque por cada reemplazamiento de bloque sucio(Nº reg/ut) xTFx (frac bloques sucios) x (nº bytes/bloque) =

= 4x107x0,15x0,25x 4 = 6x106B/uttotal : 4x107 + 2,4x107 + 0,6 x107 = 7x107B/ut

12/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.7Una cache de instrucciones de tipo directo puede en algún caso proporcionar mejor rendimiento que una cache totalmente asociativa con reemplazamiento LRU. Explicar como es posible.

Una cache de instrucciones directa puede ser mejor que una totalmente asociativa si se está ejecutando un bucle que no entra completo en la cache.Un bucle que accede a tres direcciones ABC y se repite ABCABCABCSupongamos caches de dos bloques, de manera que:

• A y C van al primer bloque (marco)• B va al segundo

El resultado es:• En una cache directa tenemos fallo en el acceso a A y C, pero en B siempre acierta• En una cache totalmente asociativa con reemplazo LRU sefalla siempre (los dos últimos bloques referenciados son diferentes del que se referencia)

13/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.9Considérese un procesador con instrucciones de 32 bits y una cache de instrucciones de 32 bytes con líneas de 8 bytes.

Para los 2 fragmentos de código DLX siguientes, indicar la organización (y sus parámetros) que da lugar a una ejecución con el mínimo número de fallos (si hay varias que produzcan el mismo rendimiento, deberá escogerse la de menor coste hardware).

0 lw r1,100(r2) 0 lw r1,100(r2)1 add r1,r1,r3 1 add r1,r1,r32 sub r4,r5,r1 2 sub r4,r5,r13 j 8 3 j 8……… ……..6 mul r2,r2,r8 6 mul r2,r2,r87 sub r2,r2,r9 7 sub r2,r2,r38 div r8,r1,r4 8 add r8,r1,r09 j 0 9 j 6

Tc x Tb=32 bytes. Tb=8 bytes. Tc=4, la cache tiene 4 bloques, en cada uno de los cuales caben 2 instrucciones. Con 4 bloques sólo hay tres configuraciones distintas de cache:c=0(asoc.); c=1 (2 bloques por conjunto) y c=2 (directa)

0,1,2,3,8,9,0,… 0,1,2,3, 8,9,6,7,8,9,6,…Prog 2Prog 1

14/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Prog 1: 0,1,2,3,8,9,0,… Prog 2: 0,1,2,3, 8,9,6,7,8,9,6,…Tc x Tb=32 bytes. Tb=8 bytes. Tc=4, la cache tiene 4 bloques, en cada uno de los cuales caben 2 instrucciones. Con 4 bloques sólo hay tres configuraciones distintas de cache:c=0(asoc.); c=1 (2 bloques por conjunto) y c=2 (directa)

Prog 1: 0,1,2,3,8,9,0,…Estos números indican las direcciones de palabra,Con 2 palabras por bloque, sus números de bloque son:

0,1,4, 0,1,4 ….Asignación Directa Asociativa por conjuntos Totalmente

asociativa4 3

0: 0 0 0

0TAG

1: 0 0 14: 1 0 00: 0 0 0

CONFLICTO

2 1 03

0: 0 0 0

TAG

1: 0 0 14: 1 0 00: 0 0 0

2 12 VIAS

NO CONFLICTO

Conjunto 0Conjunto 1

MEJORALTERNATIVA

15/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Prog 1: 0,1,2,3,8,9,0,… Prog 2: 0,1,2,3, 8,9,6,7,8,9,6,…Tc x Tb=32 bytes. Tb=8 bytes. Tc=4, la cache tiene 4 bloques, en cada uno de los cuales caben 2 instrucciones. Con 4 bloques sólo hay tres configuraciones distintas de cache:c=0(asoc.); c=1 (2 bloques por conjunto) y c=2 (directa)

Prog 2: 0,1,2,3, 8,9,6,7,8,9,6,…Estos números indican las direcciones de palabra,Con 2 palabras por bloque, sus números de bloque son:

0,1,4,3, 4,3,4,….Asignación Directa Asociativa por conjuntos Totalmente

asociativa4 3

0: 0 0 0

0TAG

1: 0 0 14: 1 0 03: 0 1 1

Fallo InicialNo hay conflictos

2 12 VIAS

MEJORALTERNATIVA

4: 1 0 03: 0 1 1

16/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Escritura directa:

lectura

escritura

Post-Escritura:

Lectura:fallo:

éxito: no transferenciafallo: leer bloque memoriaéxito: escribir palabra en memoriafallo: leer bloque de memoria (Asignación en escritura) + escribir palabra en memoria

éxito: no transferencia

Bloque limpio: leer bloqueBloque sucio: escribir bloque + leer bloque

Escritura: Ídem a a la lectura

17/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.8Un computador con memoria cache separada de datos e instrucciones tiene las siguientes características:

• El 90% de todas las referencias a instr. generadas por la CPU son encontradas en la cache. • El 80% de todas las referencias a datos generadas por la CPU son encontradas en la cache.• El bloque de la cache de instr. es de cuatro palabras y en cada fallo se lee el bloque completo.

El bloque de la cache de datos es de 2 palabras y en cada fallo se lee el bloque completo.La CPU genera 107 referencias a instrucciones y 2x106 referencias a datos. El 20% de estas referencias son escrituras.El 25% de los bloques en la memoria cache de datos son modificados (escritos) durante su permanencia en ella.

Calcular la anchura de banda media necesaria entre memoria principal y memoria cache en los siguientes casos:

a) Con política escritura directa (write-through) con asignación en escriturab) Con política post-escritura (copy-back) con asignación en escritura

18/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.8DATOS:

2 x106 reg/ut Bloque:2palabrasTF=20% Escritura: 20% Bloque sucios: 25%

INSTRUCCIONES:107 reg/ut Bloque:4 palabras TF=10%

Tráfico Mp Mc (General)Instrucciones: palabras por ut

(nº reg/ut)x TF x (nº pal/bloque)= 107x0,1x4 = 4x106palabras/ut

fallos/ut fallos/utDatos: palabras por ut

(nº reg/ut) x TFx (nº pal/bloque)= 2 x106x 0,2x2= 8x105 palabras/ut

fallos/ut fallos/utTráfico Mc Mp

1. con escritura directa: 1pal por cada escritura en la datos, haya fallo o no(nº reg/ut)x Fracción escritura x 1pal = 2x106 x0,2x1 = 4x105pal/uttotal : 4x106 + 8x105 + 4x105 = 5,2 x106 palabras/ut

2. con post-escritura: 1 bloque por cada reemplazamiento de bloque sucio(nº reg/ut) xTFx (frac bloques sucios) x (nº bytes/bloque) =

= 2x106x0,2x0,25x 2 = 2x105 palabras/uttotal : 4x106 + 8x105 + 2 x105 = 5x106 palabras/ut

19/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.10 (examen curso 1999-2000)En un procesador a 300MHz solicita un acceso a memoria cache para recoger una palabra cada ciclo de reloj. Para un determinado programa la tasa de fallos de memoria cache es 0.1, en caso de fallo se procede a reemplazar el bloque de 4 palabras.

La cache utiliza la política de “copy-back” y cada bloque dispone de un bit que indica si se ha modificado desde que llego a la cache. El porcentaje de bloques que se modifican es del 35 %.

Se construye un computador paralelo de memoria compartida con procesadores como este (con caches locales) se conectan a la memoria principal por medio de un bus con un ancho de banda de 5,2 G-palabras/ seg

¿cual es el número máximo de procesadores que soportará esta configuración sin agotar el ancho de banda del bus?

A 300MHz, 300x106 por segundo. Tasa de fallos 0,1 30x106

Uso total del bus 162x106 núm de proc soportados = = 32162 x1065,2x 109

120x106+42x106

Cada fallo lee un bloque (4 palabras) 120x106 palabras/segundo.

Bloque debe escribirse en mem en el reemplazamiento 120x106x0,3542x106pal/seg

20/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.11 (examen curso 2001-2002)Un computador de 32-bits (palabra de 32 bits) y con una memoria

direccionable en bytes, tiene una cache única de 512 bytes asociativa por conjuntos y con 2 bloques por conjunto.

Cada bloque es de 4 palabras (16 bytes) y con reemplazamiento LRU.

a) Para la siguiente secuencia de referencia indicar si el acceso es un acierto o un fallo. En caso de fallo indicar el tipo (inicial, capacidad, conflicto). Suponer la cache vacía al inicio.

b) Calcular la tasa de aciertos y la tasa de fallos.

Dirección

Acierto/fallo

Tipo

300 1BC 206 109 308 1A1 1B1 2AE 3B2 10C 205 301 3AE 1A8 3A1 1BA

F

I

F

I

F

I

F

I

F F

I

A F

I

F

I

A F F

Cf

F

I

F

Cf

A A

Tasa de aciertos = 4/16=0.25Tasa de fallos= 1-tasa de aciertos =12 /16 =0.75

Cf Cf

21/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


Problema 4.12Tenemos un procesador a 500 MHz con 2 niveles de cache, memoria principal y un disco para memoria virtual. El primer nivel de cache es separado para datos e instrucciones. Los parámetros del sistema de almacenamiento son los siguientes:

El TLB produce 0.1% de fallos para los datos con una penalización de 40 ciclos (las instrucciones no producen fallos en el TLB). Calcular el tiempo medio de acceso (TAMA) para instrucciones y para datos asumiendo que sólo se hacen lecturas

Tiempo de acceso Tasa de fallos

Tamaño del bloque

Cache nivel 1 1 ciclo 4% datos 1% instr.

64 bytes

Cache nivel 2 20 ciclos+ 1ciclo/64 bits 2% 128 bytesDRAM 100ns+25ns/8 bytes 1% 16K bytesDisco 50ms+20ns/byte 16k bytes

22/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


TAMAdisco = (5x107ns)+(16.384x20) = 50.327.680ns 25.163.840 ciclos

TAMADRAM = (100ns+25nsx(128bytes/8bytes))+0,01TAMAdisco = = (100ns+25nsx16)+0,01TAMAdisco =

=500ns+503.276,8ns 251888,4 ciclos

TAMAL2 =T.Acierto L2 + Tasa de fallos L2 + Penali L2 ==(20 + (64bytes/64bits)) + 0,02 TAMADRAM==(20 + 8) + 0,02 TAMADRAM= 5065,77ciclos

TAMAinst = 1 + 0,01 xTAMAL2 = 51,66 ciclos

TAMAdatos = 1 + 0,04xTAMAL2 + 0,001x40 = 203,67 ciclos

Problema 4.12

Tasa de fallos del TLB!!

23/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


EJERCICIO 4.13 (EXAMEN DEL CURSO 2008-2009):Tenemos una memoria principal de 64Kb direccionable en bytes.Consideremos una memoria caché de:

• 4Kb con organización directa• Líneas de 256 bytes• Con precarga en todos los casos (fallo/ acierto) del bloque siguiente

La siguiente secuencia de accesos a memoria principal es:04F5h, 11E0h, 1500h, 2000h, 241Fh,16FFh, 1233h

MOSTRAR EL CONTENIDO DE LA CACHÉ, indicando con los símbolos:“*” un fallo“+” un acierto“-” una precarga.

Como el tamaño de la memoria principal es de 64Kb,necesitamos 16 bits para direccionarla.

Como las líneas son de 256 bytes:• los últimos 8 bits identifican el byte, • los primeros 8 bits para identificar el bloque.

16 bits

Como la caché es de 4Kb, con líneas de 256bits tenemos • 16 Marcos de Bloque (M-B)

• para 16 M-B necesitamos 4 bits

(8) Selector de byte(4) IC(4) TAG

24/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


M-B0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

TAGs del contenido de la cache

25/34

CPU

Cache OnChip

Cache OnBoard

RAM

Disco Duro


M-B01234

56789

101112131415

04F5

0*0-

TAGs del contenido de la cache

11E0

1*1-

0*0-

1500

11

0*1*1-

20002*2-

011

241F22

2*2-1

16FF22

221+1-

1233221+1-2211

04F5

0*0-

11E0

1*1-

00

1500

11

01*1-

20002*2-

1

011

241F221

2*2-1

16FF221

221+1-

cpu resolución de los ejercicios de la hoja 4 - fdi.ucm.es hoja 4 (sol probl... · curso 2010-2011...

Documents