Ex 7.1

Quel est le nombre maximal de mots de 32 bits qui peuvent être stockés dans les mémoires physique des processeurs montrés au tableau 7.1 (p. 308) ?

(solution)

Intel 8088, 8086: -> adresses de 20 bits
nombre des mots = 220 octets = 218 mots = 28·210 = 256 K mots

Power PC 601: -> adresse de 32 bits
nombre des mots = 232 octets = 230 mots = 210·210·210 = 1 G mots ~ 109 mots

Ex 7.2

(a) Comment est placé la valeur ABCDh sur 16 bits dans la mémoire d'une machine "big-endian" et d'une machine "little-endian"?

(b) Même question si on met la valeur sur 32 bits?

(solution)

(a) 16-bit big-endian, commençant à l'adresse 0: AB CD. little endian: CD AB
(b) 32-bit big-endian, commençant à l'adresse 0: 00 00 AB CD. little indian: CD AB 00 00.

Ex 7.10

Une mémoire dynamique de taille 1M x 1 qui est organisée comme un tableau de 1024x1024 cellules doit être rafraîchie chaque 8 ms. Si on utilise la méthode de rafraîchissement "RAS-only" et que le temps du cycle d'accès est tc=80 ns, quel est le pourcentage minimum de temps consacré au rafraîchissement?

(solution)

Le temps minimum de rafraîchissement d'une rangée = 80 ns
Ce temps pour 1024 rangés = 1024x80 ns
Et ceci se répète chaque 8 ms (8x106ns ), alors le pourcentage du temps est de (1024x80)/(8x106) = 1.024%

Ex 7.19

Une mémoire cache associative par ensembles de 2 éléments a un temps d'accès de 40 ns, dans les cas d'un succès (hit), et un temps d'accès de 90 ns lors d'un défaut (miss). Le temps d'accès à la mémoire principale était de 70 ns, quand il n'y avait pas de mémoire cache. L'accélération des accès mémoire (speedup) en utilisant la cache est de 1.4 pour un ensemble de programmes tests. Trouver le taux de succès (d'accès mémoire) pour ces programmes?

(solution)

Succès: th=40 ns, défaut: tm=90 ns, sans-cache: tsc=70 ns,
taux de succès = h

le temps d'accès avec cache, ta=h·th + (1-h)·tm = tm-h·(tm-th) = 90 - 50 h

le speedup = (le temps d'accès sans cache/ le temps d'accès avec cache)
1.4 = (70)/(90-50h) alors, h = 80%

Ex 7.20

Une mémoire principale de 16 MO utilise une cache de 32 KO à correspondance directe ayant 8 octets par ligne (i.e, par bloc).

(a) combien y-a-il de lignes dans la cache?
(b) montrez comment l'adresse mémoire est partitionnée.

(solution)

(a) nb de lignes = 32 KO / 8 O/ligne = 215 O / 23 O/ligne = 212 lignes
(b) Voir la page 353, pour le format d'adresse
La mémoire est de taille 16 MO, alors l'adresse a 24 bits au total (car 224 O = 16 MO).
La cache contient 212 lignes, alors 12 bits sont nécessaires afin d'identifier une ligne dans la cache.
Chaque ligne représente un groupe (Figure 7.33)
3 bits sont nécessaires pour identifier l'octet dans chaque ligne, car chaque ligne contient 8 octets.
Le restant, c-à-dire, 24 - 12 -3 = 9 identifie l'étiquette ("tag") de mémoire.

23      15 14         3 2   0
+---------+------------+----+ 
|   TAG   |    GROUP   |Byte| 
+---------+------------+----+ 
     9          12       3    bits

Ex 7. 21

Un système de mémoire contient une mémoire principale de 32 MO et une cache de 64 KO.
Chaque bloc a 16 octets. Illustrez les champs d'adresse mémoire si la cache est de type

(a) associative
(b) correspondance directe
(c) associative par ensembles de 8 éléments

(solution)

Mémoire de 32 MO -> 25 bits d'adressage, au total.
La taille de la cache en ligne = 64 KO / 16 = 4 K lignes = 212 lignes
Blocs de 16 octets -> 4 bit pour identifier l'octet

(a) associative (voir page 351)
La taille de tag en bits = 25 - 4 = 21

24                   4 3   0 
+---------------------+----+ 
|         TAG         |Byte| 
+---------------------+----+
           21            4   bits 

(b) correspondance directe (voir page 353)
Le nombre de groupe = le nombre de lignes dans cache = 212, alors on a 12 bits d'identification.
La taille du tag en bits = 25 - 12 - 4 = 9

24      16 15         4 3   0 
+---------+------------+----+
|   TAG   |    GROUP   |Byte|
+---------+------------+----+
     9          12        4   bits 
(c) associative par ensembles de 8 éléments (page 355) 

Il faut d'abord déterminer le nombre d'ensembles possible dans la cache.
Le nombre d'ensembles dans la cache = la taille de la cache en ligne / la taille de chaque ensemble.
Alors, le nb d'ensembles = 212/ 23 = 29 -> 9 bits d'identification.
La taille du tag en bits = 25 - 9 - 4 = 12

24         13 12      4 3   0
+------------+---------+----+
|     TAG    | ENSEMBLE|Byte|
+------------+---------+----+
      12           9      4   bits

#7 Final 1225 A98

(a) Dans un système de mémoire virtuelle paginée, il y a 4 trames dans la mémoire physique et l'algorithme de remplacement est LRU. Pour la trace des références de pages suivante, déterminez le nombre de défauts de page ("page faults"), en supposant que la mémoire physique ne contient aucune page au début: 1, 2, 3, 2, 4, 2, 5, 6, 1, 2

(b) Si l'algorithme était OPT (optimal) plutôt que LRU, quel serait le nombre de défauts de page dans ce cas?

Même question pour FIFO (n'était pas dans l'examen)

(solution)

(a)
Ce qui se trouve dans chaque trame avant l'accès mentioné.
LRU

trames  | accès
- - - - | 1 miss
1 - - - | 2 miss
1 2 - - | 3 miss
1 2 3 - | 2
1 2 3 - | 4 miss
1 2 3 4 | 2
1 2 3 4 | 5 miss (remplace 1)
5 2 3 4 | 6 miss (remplace 3)
5 2 6 4 | 1 miss (remplace 4)
5 2 6 1 | 2
5 2 6 1 |

On a donc 7 défauts de page.

(b)
OPT

trames  | accès
- - - - | 1 miss
1 - - - | 2 miss
1 2 - - | 3 miss
1 2 3 - | 2
1 2 3 - | 4 miss
1 2 3 4 | 2
1 2 3 4 | 5 miss (remplace 3)
1 2 5 4 | 6 miss (remplace 4)
1 2 5 6 | 1
1 2 5 6 | 2
1 2 5 6 |

On a donc 6 défauts de page.

FIFO

trames  | accès
- - - - | 1 miss
1 - - - | 2 miss
1 2 - - | 3 miss
1 2 3 - | 2
1 2 3 - | 4 miss
1 2 3 4 | 2
1 2 3 4 | 5 miss (remplace 1)
5 2 3 4 | 6 miss (remplace 2)
5 6 3 4 | 1 miss (remplace 3)
5 6 1 4 | 2 miss (remplace 4)
5 6 1 2 |

On a donc 8 défauts de page.