Anomalies de cache FIFO

C'est le défi de suivi de celui-ci , si vous êtes confus, veuillez d'abord le vérifier.

Premièrement, soit le nombre de ratés du cache qu'une séquence d'accès aux ressources aurait supposé que notre cache a la capacité et utilise un schéma d'éjection premier entré-premier sorti (FIFO) lorsqu'il est plein. $m(s, k)$ $s$ $k$

Puis, étant donné un rapport , renvoyer une séquence non vide d'accès aux ressources telle qu'il existe avec . $r > 1$ $s$ $k > j$ $m(s, k) \geq r \cdot m(s, j)$

En clair, construisez une séquence d'accès aux ressources afin qu'il y ait deux tailles de cache où le cache le plus grand a (au moins) fois plus de cache manquant lorsqu'il est utilisé pour résoudre . $s$ $r$ $s$

Un exemple pour , une sortie valide est la séquence , car elle provoque échecs de cache pour une taille de cache de , mais échecs pour une taille de cache de . $r = 1.1$ $(3, 2, 1, 0, 3, 2, 4, 3, 2, 1, 0, 4)$ $9$ $3$ $10$ $4$

Peu importe la séquence que vous retournez, tant qu'elle répond aux exigences.

Le code le plus court en octets gagne.

code-golf array-manipulation orlp
la source

Lecture de fond: l'anomalie de

Bélády

C'est peut-être juste l'épuisement, mais ce défi n'est pas tout à fait clair pour moi; pourriez-vous fournir un exemple concret et quelques autres cas de test?

Shaggy

@Shaggy Go consultez l'autre défi et la lecture de fond de l'autre commentaire. Le nœud du problème est qu'un cache FIFO peut s'aggraver à mesure qu'il s'agrandit pour certaines séries de demandes.

orlp

Réponses:

Wolfram Language (Mathematica) , 124 113 101 octets

Flatten@{s=⌈2#⌉;q=Range[r=2s+1];g=Mod[q s-s,r];{Sort@g[[#+1;;]],g[[;;#]]}&~Array~r,Table[q,s^3]}&

Essayez-le en ligne!

REMARQUE: la sortie TIO n'est pas la liste réelle car elle serait très longue. La fonction wrapper sur TIO vous indique le nombre de défauts de page pour deux capacités de cache.

Pour la liste actuelle: Essayez-le en ligne!

Connexes: arXiv: 1003.1336

Comment?

Supposons une situation où nous avons deux capacités de cache, 3et 4.

Supposons également que 3-cache ait {4, 2, 5}paginé et 4-cache ait {5, 4, 3, 2}paginé. Ensuite, essayons de paginer {1, 2, 3, 4, 5, 1, 2, 3, 4, 5}:

page  3-cache   4-cache
      {4,2,5}  {5,4,3,2}
  1   {1,4,2}  {1,5,4,3}
  2   {1,4,2}  {2,1,5,4}
  3   {3,1,4}  {3,2,1,5}
  4   {3,1,4}  {4,3,2,1}
  5   {5,3,1}  {5,4,3,2}
  1   {5,3,1}  {1,5,4,3}
  2   {2,5,3}  {2,1,5,4}
  3   {2,5,3}  {3,2,1,5}
  4   {4,2,5}  {4,3,2,1}
  5   {4,2,5}  {5,4,3,2}

Le 3-cache avait 5 défauts de page, tandis que le 4-cache en avait 10. Nous sommes également revenus à notre état d'origine.

Ici, si nous répétons la pagination {1, 2, 3, 4, 5}, nous atteindrions asymptotiquement le rapport de 2.

Nous pouvons étendre ce phénomène à des capacités de cache plus élevées afin de pouvoir paginer {1, 2, 3, ... , 2n + 1}et nous retrouver avec n'importe quel ratio.

JungHwan Min
la source