tl; dr todo se hace a nivel de hardware utilizando circuitos lógicos digitales y cables. El almacenamiento en caché, en general, es una técnica que también se puede utilizar a nivel de software.
La caché en una CPU se implementa a nivel de hardware. Retrocedamos un momento y pensemos cómo lo haremos a nivel de software.
- Una matriz de elementos sin clasificar. Cada operación de búsqueda llevará tiempo O (N). Terrible
- Una matriz ordenada. Aquí podemos hacer búsquedas binarias para búsquedas y llevaría tiempo O (logN). Mejor verdad?
- Hashmap Una función hash asigna una tecla a una ubicación. Suponiendo que la función hash es ideal, obtenemos el tiempo de búsqueda O (1). Teóricamente no podemos hacerlo mejor que esto.
Entonces, digamos que elegimos hashmap como la estructura de datos a nivel de software. Esta es una buena opción a nivel de aplicación o incluso a nivel de kernel. Pero un caché en una máquina se usa TODO el tiempo. Bueno, no todos, pero para todas las operaciones de memoria. Dado que la estructura de datos se implementa en el nivel de software que se ejecuta en la parte superior del sistema operativo, tenemos que recorrer todo este camino para buscar un elemento. Esto no es práctico. Entonces, lo que necesitamos es una solución de hardware.
Pero la complejidad temporal de O (1) que obtuvimos a nivel de software parece bastante buena. ¿Cómo implementamos esto en hardware y eliminamos la dependencia del sistema operativo? Usamos circuitos lógicos digitales para asignar una clave a una ubicación de memoria. Aquí cada clave se asigna a una ubicación única. Esto se llama mapeo directo, que es costoso pero muy rápido. Ahora volviendo al hashmap. ¿Qué hacemos en caso de colisión? Hacemos encadenamiento donde cada depósito tiene una lista vinculada y todos los elementos asignados al mismo depósito se colocan en la lista. En el nivel de hardware podemos hacer algo similar. Como el mapeo directo es costoso, nos conformamos con el caché asociativo. Un caché asociativo de 2 vías significa que se pueden asignar casi dos elementos al mismo bloque de memoria. Esto significa menos cable y, por lo tanto, más barato. Pero es más lento que el caché mapeado directo.
Y, por último, el otro extremo del caché directo es el caché totalmente asociativo. Esto es similar a la solución de matriz sin clasificar en la que tuvimos que escanear la matriz completa linealmente. La única diferencia es que la lógica del hardware hace eso aquí.
Y finalmente la política de reemplazo. Idealmente, nos gustaría que todos nuestros datos estén en caché para no tener que ir a la memoria principal, que es “malditamente lenta”. Pero tenemos que vivir con un tamaño de caché pequeño, ya que son caros. Así que desalojamos un elemento de la memoria caché cuando se agrega un nuevo elemento. Por lo general, se elimina el elemento utilizado menos recientemente. Nuevamente, esto se hace a nivel de hardware. En el nivel de software, podemos pensar en hacer un seguimiento de una marca de tiempo de cuándo se usó un elemento en la memoria caché. Podemos tener un montón mínimo basado en la marca de tiempo de acceso de los elementos. Entonces, para eliminar el elemento min y agregar un nuevo elemento, se necesita tiempo O (logN).
- ¿Cómo trataría de conseguir una cooperativa después de mi primer año de Ingeniería en Computación?
- ¿Cuál es la diferencia entre BCA y Computer Engineering?
- ¿Los grados de ciberseguridad preparan uno para el campo de la seguridad?
- ¿Debo estudiar Ingeniería Informática en la universidad?
- ¿Por qué los viejos profesores de CS aman el lenguaje de programación Ada?
