funciones de correspondencia
TRANSCRIPT
![Page 1: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/1.jpg)
Arquitectura de Computadores
Memoria Caché: Funciones de Correspondencia
![Page 2: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/2.jpg)
Objetivos
Entender el modo de operación de las distintas
funciones de correspondencia utilizadas en las
memorias caché
Entender como cada función mapea las direcciones de
la memoria principal en la memoria caché
Entender las ventajas y desventajas de cada función de
correspondencia
Objetivos
2 Arquitectura de Computadores
![Page 3: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/3.jpg)
Indica la forma como mapeo los bloques de memoria principal en las líneas de la memoria caché
Arquitectura de Computadores3
Determina donde guardar un bloque Determina donde buscar un dato Permite determinar qué bloque hay en cada línea
Memoria Caché
Función de Correspondencia
![Page 4: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/4.jpg)
Arquitectura de Computadores4
Correspondencia Directa (directly mapped)
Correspondencia Asociativa (fully associative)
Correspondencia Asociativa por conjuntos (N-way associative)
Funciones de Correspondencia
Tipos de Correspondencia
![Page 5: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/5.jpg)
Arquitectura de Computadores5
Correspondencia Directa
(directly mapped)
Funciones de Correspondencia
![Page 6: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/6.jpg)
Arquitectura de Computadores6
Correspondencia Directa (directly mapped) Mapea a priori Cada bloque tiene asociada una línea de la caché
Correspondencia Directa
![Page 7: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/7.jpg)
Arquitectura de Computadores7
Ej. 1000 alumnos: 0-999 Cada uno se estaciona en el
estacionamiento determinado por sus últimos 2 dígitos del número de alumno.
Correspondencia Directa
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
![Page 8: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/8.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Arquitectura de Computadores8
Ej. 1000 alumnos: 0-999 Cada uno se estaciona en el
estacionamiento determinado por sus últimos 2 dígitos del número de alumno.
Correspondencia Directa
Llega alumno 814 Se estaciona en 14
![Page 9: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/9.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Arquitectura de Computadores9
Ej. 1000 alumnos: 0-999 Cada uno se estaciona en el
estacionamiento determinado por sus últimos 2 dígitos del número de alumno.
Correspondencia Directa
Llega alumno 764 Se estaciona en 64
![Page 10: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/10.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Llega alumno 102 Se estaciona en 02
Arquitectura de Computadores10
Ej. 1000 alumnos: 0-999 Cada uno se estaciona en el
estacionamiento determinado por sus últimos 2 dígitos del número de alumno.
Correspondencia Directa
![Page 11: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/11.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Arquitectura de Computadores11
Correspondencia Directa
Queremos ir a buscar el auto del alumno 683
¿Cómo sabemos si el auto del estacionamiento 83 es el de él?
Necesitamos almacenar información extra que indique que auto es el que está en cada estacionamiento.
![Page 12: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/12.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Arquitectura de Computadores12
Correspondencia Directa
TAG
Queremos ir a buscar el auto del alumno 683
¿Cómo sabemos si el auto del estacionamiento 83 es el de él?
Necesitamos almacenar información extra que indique que auto es el que está en cada estacionamiento.
![Page 13: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/13.jpg)
82
83
84
85
6
00
01
02
13
14
15
62
63
64
96
97
98
99
Arquitectura de Computadores13
¿Qué guardo? El dígito de las centenas El resto determinado por número de
n° estacionamiento
Correspondencia Directa
TAG
8
7
1
9
5
Entonces el auto guardado en 83 no corresponde al 683 sino al 583.
Hay que ir a buscar el auto 683 fuera del campus y actualizar el tag.
![Page 14: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/14.jpg)
82
83
84
85
6
00
01
02
13
14
15
62
63
64
96
97
98
99
Arquitectura de Computadores14
¿Si quiero el auto del alumno 963?
Voy a 63 y leo el tag. El auto es el que busco.
Correspondencia Directa
TAG
8
7
1
9
![Page 15: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/15.jpg)
Arquitectura de Computadores15
Correspondencia Directa
Memoria Cache
00
01
10
11
Cada línea de caché corresponde a un “estacionamiento” . Cada bloque de la memoria principal se asocia a una línea
particular. Ej.Memoria principal de 256 bytes, caché de 8 bytes, bloques de 2
bytes.
Memoria Principal = 128 bloques Caché = 4 líneas
![Page 16: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/16.jpg)
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
Arquitectura de Computadores16
Correspondencia Directa
Cada línea de caché corresponde a un “estacionamiento” . Cada bloque de la memoria principal es asociada a una línea
particular. Ej.Memoria principal de 256 bytes, caché de 8 bytes, bloques de 2
bytes, Determina el byte dentro del bloque o de la línea
01010101
![Page 17: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/17.jpg)
Arquitectura de Computadores17
Correspondencia Directa
Cada línea de caché corresponde a un “estacionamiento” . Cada bloque de la memoria principal es asociada a una línea
particular. Ej.Memoria principal de 256 bytes, caché de 8 bytes, bloques de 2
bytes,
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
Determina la línea de la caché
0000010110101111
![Page 18: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/18.jpg)
Arquitectura de Computadores18
Correspondencia Directa
Cada línea de caché corresponde a un “estacionamiento” . Cada bloque de la memoria principal es asociada a una línea
particular. Ej.Memoria principal de 256 bytes, caché de 8 bytes, bloques de 2
bytes,
Tag asociado a la dirección
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
0000 00000 00000 00000 00000 00000 00000 00000 0
![Page 19: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/19.jpg)
Arquitectura de Computadores19
Correspondencia Directa
¿Qué pasa si duplicamos la memoria principal? El tag aumenta en un bit
Tag asociado a la dirección
00000000
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
0000 00000 00000 00000 00000 00000 00000 00000 0
![Page 20: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/20.jpg)
Arquitectura de Computadores20
Correspondencia Directa
¿Qué pasa si duplicamos la cantidad de líneas de la caché? Los bits que determinan las líneas aumentan en 1 El tag se reduce en un bit
Determina la línea de la caché0000 0000
0000 00010000 00100000 00110000 01000000 01010000 01100000 0111
0000010110101111
00000000
![Page 21: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/21.jpg)
Arquitectura de Computadores21
Correspondencia Directa
¿Qué pasa si duplicamos el tamaño de las líneas? Índice del byte en el bloque o línea aumenta en un bit Bit de la línea se mantiene, pero se desplaza. Tag se reduce en 1
Determina el byte dentro del bloque o de la línea
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
0000010110101111
01010101
00110011
00000000
00001111
![Page 22: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/22.jpg)
Arquitectura de Computadores22
Correspondencia Directa
Ventajas Tag pequeño (menos memoria extra) Muy rápidas No requieren políticas de reemplazo Lógica simple
Desventajas Poca eficiencia en el uso del espacio
Puedo sobrescribir datos aún cuando hay lugares libres Muchas colisiones
![Page 23: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/23.jpg)
Arquitectura de Computadores23
Correspondencia Directa
Ej. Memoria principal de 2 Mb
2 * 220 21 bits. Caché de 64 Kb Línea de 4 bytes
64Kb / 4b = 16K_líneas 24 * 210 14 bits
Para una dirección cualquiera
A20 A19 A18 A17 A16 A15 A14 A13 A12 A11 A10 A9 A8 A7 A6 A5 A4 A3 A2 A1 A0
Índice del byte
LíneaTag
![Page 24: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/24.jpg)
Arquitectura de Computadores24
Correspondencia Asociativa
(fully associative)
Funciones de Correspondencia
![Page 25: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/25.jpg)
Arquitectura de Computadores25
Correspondencia Asociativa (fully associative) Mapea en forma dinámica Cada bloque puede estar en cualquier línea
Correspondencia Asociativa
![Page 26: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/26.jpg)
Arquitectura de Computadores26
Ej. 1000 alumnos: 0-999 Cada uno se estaciona en el
primer estacionamiento libre.
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Correspondencia Asociativa
![Page 27: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/27.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Arquitectura de Computadores27
Llega alumno 814
Correspondencia Asociativa
Ej. 1000 alumnos: 0-999 Cada uno se estaciona en el
primer estacionamiento libre.
![Page 28: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/28.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Arquitectura de Computadores28
Ej. 1000 alumnos: 0-999 Cada uno se estaciona en el
primer estacionamiento libre.
Llega alumno 764
Correspondencia Asociativa
![Page 29: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/29.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Llega alumno 102
Arquitectura de Computadores29
Correspondencia Asociativa
Ej. 1000 alumnos: 0-999 Cada uno se estaciona en el
primer estacionamiento libre.
![Page 30: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/30.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Arquitectura de Computadores30
Queremos ir a buscar el auto del alumno 683
¿Cómo sabemos donde está?
Correspondencia Asociativa
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
TAG814
764102
¿Qué almacenamos en el tag?
Todo el n° de alumno
![Page 31: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/31.jpg)
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Arquitectura de Computadores31
TAG
¿Qué pasa si se llena el estacionamiento?
Al llegar un nuevo auto, sacamos alguno conforme a alguna política
Correspondencia Asociativa
814
764102
![Page 32: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/32.jpg)
Arquitectura de Computadores32
Memoria Cache
00
01
10
11
Cualquier bloque de memoria principal puede estar en cualquier línea de la caché
Ej. Memoria principal de 256 bytes, caché de 8 bytes, bloques de 2 bytes.
Memoria Principal = 128 bloques Caché = 4 líneas
Correspondencia Asociativa
![Page 33: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/33.jpg)
Arquitectura de Computadores33
Cualquier bloque de memoria principal puede estar en cualquier línea de la caché
Ej. Memoria principal de 256 bytes, caché de 8 bytes, bloques de 2 bytes.
Memoria Principal = 128 bloques Caché = 4 líneas
Correspondencia Asociativa
Determina el byte dentro del bloque o de la línea
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
01010101
![Page 34: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/34.jpg)
Arquitectura de Computadores34
Cualquier bloque de memoria principal puede estar en cualquier línea de la caché
Ej. Memoria principal de 256 bytes, caché de 8 bytes, bloques de 2 bytes.
Memoria Principal = 128 bloques Caché = 4 líneas
Correspondencia Asociativa
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
Tag asociado a la dirección
01010101
![Page 35: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/35.jpg)
Arquitectura de Computadores35
Correspondencia Asociativa
Ventajas Uso eficiente de la memoria (100%)
Desventajas Tag muy grande. Requiere politicas de reemplazo Requiere almacenar información adicional para las políticas
de reemplazo. Es muy caro determinar qué bloque está en cada línea
Búsqueda puede ser muy lenta si la caché aumenta de tamaño O(n).
Ó muy cara electrónicamente si se usa búsqueda en paralelo.
![Page 36: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/36.jpg)
Arquitectura de Computadores36
Correspondencia Asociativa por conjuntos
(N-way associative)
Funciones de Correspondencia
![Page 37: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/37.jpg)
Arquitectura de Computadores37
Correspondencia Asociativa por conjuntos (N-way associative)
Mezcla de la correspondencia directa y asociativa
Correspondencia Asociativa por Conjuntos
![Page 38: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/38.jpg)
Arquitectura de Computadores38
Ej. 1000 alumnos: 0-999
00
01
02
13
14
15
62
63
64
82
83
84
85
96
97
98
99
Correspondencia Asociativa por Conjuntos
Las 100 entradas se dividen en 10 grupos de 10.
El grupo donde se estaciona alguien depende del último dígito de su n° de alumno (~directly mapped)
Dentro del grupo se estaciona donde mejor le parezca (~fully-associative)
![Page 39: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/39.jpg)
Arquitectura de Computadores39
Memoria Cache
00
01
10
11
Ej. 2 vías.
Memoria Principal = 128 bloques Caché = 4 líneas
Correspondencia Asociativa por Conjuntos
Las vías indican la cantidad de líneaspor conjunto… NO LA CANTIDAD DE CONJUNTOS
![Page 40: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/40.jpg)
Arquitectura de Computadores40
Ej. 2 vías.
Memoria Principal = 128 bloques Caché = 4 líneas
Correspondencia Asociativa por Conjuntos
Determina el byte dentro del bloque o de la línea
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
01010101
![Page 41: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/41.jpg)
Arquitectura de Computadores41
Ej. 2 vías.
Memoria Principal = 128 bloques Caché = 4 líneas
Correspondencia Asociativa por Conjuntos
Determina el conjunto de la memoria cache
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
00110011
![Page 42: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/42.jpg)
Arquitectura de Computadores42
Ej. 2 vías.
Memoria Principal = 128 bloques Caché = 4 líneas
Correspondencia Asociativa por Conjuntos
Tag asociado a la dirección
0000 00000000 00010000 00100000 00110000 01000000 01010000 01100000 0111
00110011
01010101
![Page 43: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/43.jpg)
Arquitectura de Computadores43
Ventajas
Tag más pequeño que en fully – associative, pero más grande que Directly – Mapped
Permite mayor eficiencia en el uso de la memoria por la flexibilidad.
Búsqueda dentro del conjunto es más rápida.
Correspondencia Asociativa por Conjuntos
![Page 44: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/44.jpg)
Arquitectura de Computadores44
Ej, 4 vías. Memoria Principal de 1Kb 210
10 bits
Líneas de 2 bytes 1 bit para especificar línea
Caché de 64 bytes 64 / 2 bytes por línea = 32 líneas.
32 líneas / 4 vías = 8 conjuntos. 3 bits para especificar conjunto.
¿ En que direcciones de la caché podría estar el dato almacenado en la dirección 1101100111 ?
Correspondencia Asociativa por Conjuntos
![Page 45: Funciones de correspondencia](https://reader035.vdocumento.com/reader035/viewer/2022062216/5592ebca1a28ab7e408b4693/html5/thumbnails/45.jpg)
Arquitectura de Computadores45
Correspondencia Asociativa por Conjuntos
Memoria Caché
00h
01h
02h
03h
04h
05h
06h
07h
08h
1Bh
1Ch
1Dh
1Eh
1Fh
Conjunto 0 : líneas 0 – 3 Conjunto 1 : líneas 4 – 7 Conjunto 2 : líneas 8 – 11 … Conjunto n :
líneas N*n N*n + N-1
Ej, 4 vías.¿ En que dirección de la caché podría estar el dato almacenado en la dirección 1101100111 ?
1101100111conjunto 3
byte 1
Línea 0 : direcciones 0 – 1 Línea 1 : direcciones 2 – 3 … Línea n : direcciones 2*n
+ 2*n+1
Conjunto 3 : líneas 12 -15
Línea 12 : direcciones 24 - 25
13 : 26 - 27
14 : 28 - 29
15 : 30 - 31