Pourquoi caches L3 peuvent contenir que des blocs partagés?

Question

Dans un article récent de MCCA [1], les auteurs présentent un moyen d'améliorer l'évolutivité des caches partagées et cohérentes. L'ingrédient de noyau est en supposant que les caches sont inclusive , qui est caches de niveau supérieur (par exemple L3, une antémémoire globale) contiennent tous les blocs qui sont stockés dans leur descendant caches de niveau inférieur (par exemple L1, une antémémoire par noyau).

En règle générale, les caches de niveau supérieur sont plus grandes que leurs caches descendantes respectives ensemble. Par exemple, certains modèles de la série Intel Core i7 à quatre cœurs ont un 8MB partagé cache (L3) et 256KB caches privées (L2), qui est le cache partagé peut contenir huit fois autant de blocs que les caches privés au total.

Cela semble indiquer que chaque fois que le cache partagé doit expulser un bloc (pour charger un nouveau bloc), il peut trouver un bloc qui est partagé avec aucun des caches² privé (principe pigeon trous). Cependant, les auteurs écrivent:

  

[Nous] pouvons potentiellement éliminer tous les rappels, mais seulement si l'associativité, ou le nombre d'endroits où un bloc spécifique peuvent être mises en cache, du cache partagé dépasse le associativité total des caches privés. Associativité suffisante, [le cache partagé] est garantie pour trouver un bloc non partagé [...]. Sans cette associativité pire des cas, un groupe pathologique de misses pourrait conduire à une situation dans laquelle tous les blocs dans un ensemble de cache partagé sont vraiment partagés.

Comment est-ce possible, qui est de savoir comment, par exemple, la couverture 1Mo 8MB? Il est clair que je manque quelques détails de la façon dont ce travail des hiérarchies de cache. Que signifie « associativité » signifie ici? « Nombre de places dans lequel un bloc spécifique peut être mis en mémoire cache » est pas clair; Je ne peux arriver à l'interprétation qu'un bloc peut être stocké plusieurs fois dans chaque cache, mais cela n'a pas de sens du tout. Que serait un tel « groupe pathologique de manque » ressembler?

---

1. Pourquoi on-Chip Cache La cohérence est là pour rester par MMK Martin Hill MD, DJ Sorin (2012)
2. En supposant que les caches partagés sait quels blocs sont partagés où. Ceci peut être réalisé par des notifications d'expulsion explicites et peu suivi, dont il est question aussi dans [1].

Answer 1

Peut-être que je peux faire la lumière sur l'associativité. Ces caches ne sont pas des blocs de mémoire ouverts juste, il ne pense pas à eux comme une sorte de conteneur générique. Chaque bloc de mémoire a une adresse réelle (que ce soit n'a pas d'importance physique ou virtuel, supposons qu'il est tout simplement une adresse fixe). A chaque niveau de cache cette mémoire ne peut être mis en mémoire cache à des endroits très précis dans le cache.

Par exemple, l'adresse mémoire X peut être stocké dans le cache L1 à l'emplacement Y0. C'est une application directe. Mais supposons qu'il peut aussi être stocké à l'emplacement Y1, il est 2 voies associative (ce qui est assez courant). Être stockable dans N-lieux rend associative N à sens unique. Lorsque la puce choisit un emplacement du cache, il ne vérifie que ces endroits N -. Il ne scanne pas le cache (ce qui serait trop lent / compliqué)

Cela devrait préciser ce qu'ils veulent dire en disant que le cache partagé doit avoir une associativité plus globale que les caches inférieurs. Donc, si L1 est 2 voies, L2 est à 4 voies, et il y a 4 processeurs, ils cache partagé doit être> 24 voies associative (je n'ai pas l'article, mais cela ressemble à ce qu'ils veulent dire). Cela fait suite alors, qu'au moins un de ces emplacements partagés ne doivent pas être mises en cache dans l'une des caches privées.

Je ne peux pas dire avec certitude ce que leur cas « pathologique » est, mais je ne peux expliquer une commune, qui peut affecter des choses comme la recherche binaire. Supposons que le cache L1 est 1 voie associative et 4 Ko. Les endroits où peuvent être stockés mémoire est probablement un mod simple de l'adresse (X mod 4K). Dites alors vous avez un grand bloc de données qui est une puissance de 2 (qui est commun). Dans une recherche binaire vous hachez toujours la taille en deux, donc une recherche sur un bloc 256K aurait de vérifier l'adresse 128K, 64K, 32K, 16K, 8K, 4K, et la partie inférieure. Mais vous devriez voir un problème. Ces 6 premières adresses mappent toutes exactement le même emplacement du cache. Ainsi, chaque accès nécessite une expulsion et la charge, malgré vous accès à seulement une petite quantité de mémoire.