2009-06-17 27 views
9

¿Existe una teoría unificada del almacenamiento en caché? Es decir, colecciones de teoremas y algoritmos para construir cachés y/u optimizarlos?Teoría del almacenamiento en caché

La pregunta es deliberadamente amplia, porque los resultados que estoy buscando también son amplios. Fórmulas para acelerar al máximo, métricas para algoritmos de almacenamiento en caché, cosas así. Un libro de texto de nivel universitario probablemente sea ideal.

Respuesta

2

Si puede asumir que un golpe de caché es mucho más rápido que un error de caché, encontrará que las horas extraordinarias, incluso si solo tiene fallas de caché, usar un caché seguirá siendo tan rápido o más rápido que no usar un caché.

Véase más abajo para los cálculos:

Number of hits = NumRequests - #CacheMisses 

AverageTime = ((NumRequests-#CacheMisses) * TimePerHit + #CacheMisses * TimePerMiss)/NumRequests 

Si entonces se supone que NumRequests es infinito (esto es un problema de límite, no temen al cálculo), podemos ver esto:

AverageTime = Infinity*TimePerHit/Infinity - #CacheMisses*TimePerHit/Infinity + #CacheMisses*TimePerMiss/Infinity 

Ambos términos con los #CacheMisses llega a cero, pero toda la ecuación, resuelve:

AverageTime = TimePerHit 

concede esta es para cuando el número de solicitudes es infinito, pero puede ver cómo esto acelerará fácilmente su sistema al usar un caché.

+0

Su cálculo se ve muy bien. Desafortunadamente, implica la suposición de que el número de errores de caché es constante, lo que parece muy poco probable. El número correcto sería: HitProbability * TimePerHit + (1 - HitProbability) * TimePerMiss –

+0

Sé que las matemáticas son un poco dudosas; esta es una prueba que tuve que aprender para una clase que tomé el otoño pasado y solo traté de recordarla desde allí. Sin embargo, teniendo en cuenta su punto, dado que tengo CacheHits frente a CacheMisses, esta es una razón, ¿no sería esto lo mismo que usar una probabilidad de acierto? – samoz

+0

No del todo. Suponiendo que hay una probabilidad constante distinta de cero de errores de caché, habrá infinitas fallas si se realizan ensayos infinitos. Su fórmula sería correcta si la caché es lo suficientemente grande como para contener todos los datos que alguna vez se solicitarán. Luego hay un límite superior constante al número de fallas. –

2

La gran mayoría del almacenamiento en caché del mundo real implica la explotación de la "regla 80-20" o Pareto distribution. Ver más abajo para cómo se ve

Pareto distribution

Esto se manifiesta en aplicaciones como:

  • La mayor parte del tiempo de ejecución se gasta en la misma pieza de código (haciendo cachés de código en las CPU efectivos)
  • A menudo, cuando se accede a una variable, se volverá a acceder a ella pronto (haciendo cachés de datos en las CPU)
  • Cuando un navegador busca el nombre de un sitio web una vez, accederá a él con bastante frecuencia en el futuro cercano (m aking DNS caches effective)

Por lo tanto, yo diría que la "teoría del almacenamiento en caché" es utilizar unos pocos recursos adicionales que son generalmente "raros" pero "rápidos" para compensar las cosas más repetidas lo voy a hacer

La razón por la que hace esto es tratar de "nivelar" el número de veces que hace la operación "lenta" en función de la tabla altamente sesgada de arriba.

2

Hablé con uno de los profesores de mi escuela, que me señaló online algorithms, que parece ser el tema que estoy buscando.

Existe una gran cantidad de superposición entre los algoritmos de almacenamiento en caché y los algoritmos de reemplazo de página. Probablemente edite las páginas de WikiPedia para estos temas para aclarar la conexión, una vez que yo haya aprendido más sobre el tema.

Cuestiones relacionadas