Una memoria caché que utiliza una política de desalojo menos utilizada recientemente puede manipularse fácilmente para que siempre falte. En cada falta, se desaloja la entrada de caché más antigua y se coloca una nueva en su lugar. Por lo tanto, siempre que la región a la que se accede no sea una de las N entradas a las que se accedió anteriormente, la caché se perderá, donde N es el tamaño de la caché en líneas.
En su problema, el caché consta de entradas de 64 bytes, pero el problema le pide que lea un byte a la vez. Entonces, después de leer el byte 0, la próxima falla llegará al leer el byte 64, luego el byte 128, etc.
Dado que hay 512 líneas de caché, la entrada en caché de bytes 0-63 caducará después de 512 lecturas siguiendo este patrón, que se compensa con 32768. Afortunadamente, esto es más pequeño que el tamaño de la matriz, por lo que es posible una solución.
- Cómo verificar si un algoritmo que hice en C ++ es eficiente en la vida real
- Cómo resolver este problema en la búsqueda binaria
- Cómo mejorar la lógica o la presentación de la conjetura descrita en una respuesta para que más personas puedan entender lo que creo que es un método sorprendente para crear algorítmicamente un conjunto primo potencialmente infinito
- ¿Cómo es diferente la cola circular del algoritmo de inserción?
- ¿Cuál es la diferencia entre el algoritmo que venció a los humanos en el ajedrez y el algo que venció a los humanos en Go?
Continúe avanzando 64 bytes; después de leer el final de la matriz, ha leído 1/64 del total de entradas, una vez. Luego regrese al principio y lea los bytes 1, 65, 129, etc.
Ahora, la lectura del byte 1 es la primera vez que leemos un byte dentro del mismo límite de la línea de caché. Pero debido a que hemos realizado 10,000 lecturas, y solo las últimas 512 lecturas permanecen en caché, podemos estar seguros de que la lectura del byte 1 también se pierde.
Haga esto para cada desplazamiento inicial entre 0 y 63. Cada una de esas lecturas es un error de caché debido a la propiedad LRU.
El problema nos pide que leamos cada byte dos veces, por lo que después de comenzar en el desplazamiento 63, comience todo el proceso nuevamente. La secuencia de lecturas se puede expresar como un bucle triplemente anidado.
Sin embargo, tenga en cuenta que la secuencia descrita anteriormente no es la única solución: cualquiera de los ordenamientos factoriales de 10000 de las líneas de caché podría usarse en cada pasada, o incluso podríamos intercalar pasadas o hacer diferentes ordenaciones para cada pasada siempre que mantengamos la distancia de 512 entradas entre lecturas a la misma región de 64 bytes.
