LRU vs FIFO vs Aléatoire

L'expression "Il n'y a pas de questions stupides" s'adapte si bien. C'était une bonne question, j'ai dû créer un compte et poster sur il et partager mon point de vue comme de quelqu'un qui a modelé les caches sur un couple de Processeurs.

Vous spécifiez l'architecture d'un 68000, qui est un PROCESSEUR plutôt que d'un GPU ou un contrôleur USB, ou d'un autre morceau de matériel qui peut accéder à un cache cependant...

Donc le code que vous exécutez sur le 68000, fera une énorme différence pour la partie de la question "le moins possible à l'avenir de cache miss "/défauts de page".

Dans ce de vous différencier entre le cache et les défauts de page, je ne suis pas sûr exactement ce qui coldfire architecture l'on se réfère à mais je suppose que ce n'est pas un matériel TLB de remplacement, il utilise un logiciel mecanisme (de sorte que le cache sera partagé avec les données des applications).

Dans la politique de remplacement le facteur le plus important est le nombre d'associations (ou les moyens).

Direct de cache de la carte (1), est directement corrélée (tous plus toujours) avec les bits de poids faibles de l'adresse (le nombre de bits de définir la taille du cache) et 32 ko de cache serait la moindre 15bits. Dans ce cas, le remplacement algorthims LRU, FIFO ou Aléatoire serait inutile puisqu'il n'existe qu'un seul choix possible.

Cependant écriture Différée ou "Writethrough" sélection de la mémoire cache aurait plus d'effet. Pour les écritures de la mémoire "Writethrough" signifie que la ligne de cache n'est pas réparti comme revêtue de l'écriture différée cache où la ligne actuellement dans le cache qui partage la même inférieur à 15 bits est éjecté hors du cache et de la lecture en puis modifié, à utiliser SI le code en cours d'exécution sur le PROCESSEUR utilise ces données).

Pour les opérations d'écriture et de ne pas effectuer de multiples opérations sur les données, puis "writethrough" est généralement beaucoup mieux, aussi sur les processeurs modernes (et je ne sais pas si cette architecture prend en charge), mais "Writethrough" ou d'écriture Différée peut être sélectionné sur une TLB/Page. Cela peut avoir beaucoup greator effet sur le cache de la politique, vous pouvez programmer le système pour l'adapter au type de données de chaque page, surtout dans un direct de cache de la carte 😉

Donc directement de cache de la carte est assez facile à comprendre, il est également facile de comprendre la base de la cache dans le pire des cas, dans le meilleur des cas et de la moyenne des cas.

Banque imagin un memcpy routine qui copie les données qui correspond à la taille du cache. Par exemple, un 32k direct mapped cache, avec deux 32k tampons alignés sur une 32k boundry....

0x0000 -> read
0x8000 -> write
0x8004 -> read
0x8004 -> write
...
0x8ffc -> read
0x8ffc -> write

Ici, vous voyez les lire et à écrire comme ils copie de chaque mot de données, de l'avis de la baisse de 15 bits sont les mêmes pour chaque opération en lecture et écriture.

Directement mappé cache à l'aide de l'écriture différée (souvenez-vous de l'écriture différée alloue les lignes de la suivante)

0x0000 -> read
 cache performs: (miss)
   0x0000:0x001f -> READ from main memory (ie. read 32 bytes of the source)

0x8000 -> write
  cache performs: (miss)
    invalidate 0x0000:0x001f (line 0)
    0x8000:0x801f -> READ from main memory (ie. read 32 bytes of the destination)
    0x8000           (modify this location in the cache with the read source data)

<loop>

0x0004 -> read
  cache performs: (miss)
    writeback 0x8000:0x801f -> WRITE to main memory (ie. write 32 bytes to the desitnation)
    0x0000:0x001f -> READ from main memory (ie. read 32 bytes of source (the same as we did just before)

0x8004 -> write
  cache performs: (miss)
    invalidate 0x0000:0x001f (line 0)
    0x8000:0x801f -> READ from main memory (ie. read 32 bytes of the destination)
    0x8004           (modify this location in the cache with the read source data)

</loop>  <--- (side note XML is not a language but we use it as such)

Comme vous le voyez, beaucoup d'opérations de mémoire de continuer, c'est en fait appelé "raclée" et est le meilleur exemple d'une pire des cas scenairo.

Maintenant, imaginez que nous utilisons un "writethrough" cache, ce sont les opérations:

<loop>
0x0000 -> read
 cache performs: (miss)
   0x0000:0x001f -> READ from main memory (ie. read 32 bytes of the source)

0x8000 -> write
  cache performs: (not a miss)
   (not a lot, the write is "posted" to main memory) (posted is like a letter you just place it in the mailbox and you don't care if it takes a week to get there).

  <loop>

  0x0004 -> read
    cache performs: (hit)
      (not a lot, it just pulls the data it fetched last time which it has in it's memory so it goes very quickly to the CPU)

  0x8004 -> write
    cache performs: (not a miss)
     (not a lot, the write is "posted" to main memory)

  </loop until next 32 bytes>
</loop until end of buffer>

Comme vous pouvez le voir une différence énorme que nous avons maintenant n'est pas du thrash, en fait, nous sommes dans le meilleur des cas dans cet exemple.

Ok, donc c'est le cas simple d'écrire par le biais de vs écrire de nouveau.

Direct carte caches sont cependant pas très commun de la plupart des gens utilisent, 2,4 ou 8 chemin du cache, c'est il y a 2, 4 ou 8 différentes possibilités d'affectations en ligne. Donc, on pourrait stocker 0x0000, 0x8000, 0x1000, 0x1800 tous dans le cache en même temps dans un 4 ou 8 voies, de cache (bien évidemment, une façon 8 peut également stocker 0x2000, 0x2800, 0x3000, 0x3800 ainsi).

Cela permettrait d'éviter cette surcharge question.

Juste pour préciser le numéro de la ligne dans un 32k direct mapped cache le bas de 15 bits de l'adresse.
Dans un 32k 2 voies c'est le fond 14 bits.
Dans un 32k 4 voies, c'est le fond 13 bits.
Dans un 32k 8 c'est le fond de 12 bits.

Et entièrement associatve cache c'est les lignes de la taille (ou le bas 5 bits avec 32 octets de la ligne). Vous ne pouvez pas avoir moins de un ligne. 32 octets est généralement la plupart des conditions de fonctionnement optimales dans un DDR système de mémoire (il y a d'autres raisons, someimes 16 ou parfois de 64 octets peut être mieux, et 1 octet serait optimale dans le algorthmic cas, permet de utilise 32 car c'est très fréquent)

Pour l'aider à comprendre la LRU, FIFO et Aléatoire envisager de la cache est plein associatif, dans un 32k de 32 octets de la ligne de cache c'est 1024 lignes.

Un remplacement aléatoire, d'une politique sur le hasard de provoquer un pire des cas, frapper chaque 1024 remplacements (ie. 99,9% de succès), soit dans la loi LRU ou FIFO je pourrais toujours écrire un programme qui permettrait de "thrash" ie. toujours causer une pire des cas behavouir (ie. 0% hit).

Clairement si vous aviez entièrement associatif cache vous ne choisissez LRU ou FIFO si le programme est connu, et qu'il était connu à l'exact behavouir du programme.

Pour TOUT ce qui n'était pas à 99,9% prévisible de choisir au HASARD, c'est tout simplement le meilleur pas être pire, et l'un des meilleurs pour se situer dans la moyenne, mais que diriez-dans le meilleur des cas (où j'ai d'obtenir les meilleures performances)...

Eh bien, il repose essentiellement sur le nombre de façons...

2 façons et je peux optimiser des choses comme memcpy et d'autres algorthims pour faire un bon travail. Aléatoire serait se tromper de la moitié du temps.
4 moyens et quand je switch entre autres tâches, je ne pourrais pas endommager le cache tellement que leurs données sont toujours locales. Aléatoire serait se tromper quater du temps.
8 façons maintenant les statistiques peuvent prendre effet à une 7/8% taux de succès sur un memcpy n'est pas aussi bon que d'un 1023/1024% (totalement associatif ou optimisé le code), mais pour les non optimisé le code qu'il fait une différence.

Alors pourquoi ne pas les gens de faire totalement associatif de la cache, avec remplacement aléatoire politiques!

Bien ce n'est pas parce qu'ils ne peuvent pas générer des nombres aléatoires, en fait un pseudo random number generator est tout aussi bon et oui je peux écrire un programme pour obtenir 100% de manquer de rythme, mais qui n'est pas le point, je ne pouvais pas écrire un programme utile qui aurait 100% de miss, que j'ai pu avec un LRU ou FIFO algo.

Un 32k de 32 octets de la ligne Entièrement associatve de la cache, vous obliger à comparer 1024 valeurs, dans le matériel, cela se fait via une CAM, mais c'est une pièce coûteuse de matériel, et aussi que c'est juste pas possible de comparer ce nombre de valeurs dans un "RAPIDE" temps de traitement, je me demande si un ordinateur quantique pourrait....

De toute façon, pour répondre à votre question qui est le meilleur:

1. Examiner si "writethrough" peut-être mieux que l'écriture différée.
2. Grande manière ALÉATOIRE est mieux
3. Code inconnu ALÉATOIRE est mieux pour les 4 ou au-dessus.
4. Si c'est la seule fonction ou vous voulez le plus de vitesse à partir de quelque chose de votre prêt à optimiser, et ou vous n'avez pas de soins sur le pire des cas, la LRU est probablement ce que vous voulez.
5. Si vous avez très peu de moyen de la LRU est probablement ce que vous voulez, sauf si vous avez un scénario très spécifique puis FIFO peut être OK.

Références:

• http://www.freescale.com/files/training/doc/APF_ENT_T0801_5225_COLDFIRE_MCU.pdf
• http://en.wikipedia.org/wiki/Cache_algorithms

OriginalL'auteur user3713380

Entre les trois, je vous recommande LRU. Tout d'abord, c'est une bonne approximation de planification optimale lorsque la localité est assumé (ce qui s'avère être une bonne hypothèse). Aléatoire de la planification ne peut pas bénéficier de la localité. Deuxièmement, il ne souffre pas de Belady l'anomalie (comme FIFO); c'est, plus gros caches signifie de meilleures performances, ce qui n'est pas forcément le cas avec FIFO.

Seulement si votre problème spécifique de domaine suggère fortement d'utiliser quelque chose d'autre, LRU va être dur à battre dans le cas général.

OriginalL'auteur Patrick87

Si vous voulez le meilleur des deux mondes, envisager une approche adaptative qui modifie la stratégie basée sur l'utilisation réelle des modèles. Regardez, par exemple, l'algorithme d'IBM Adaptative De Remplacement De Cache: http://code.activestate.com/recipes/576532-adaptive-replacement-cache-in-python/

OriginalL'auteur Raymond Hettinger