SISTEMAS OPERATIVOS-CACHE AJENO ESTRUCTURA DE DATOS.

...

En contraste con el modelo externo, la memoria, los algoritmos en el modelo-cache externo no pueden gestionar de forma explícita la caché (leer bloque asunto y las solicitudes de bloque de escritura). Esta pérdida de la libertad es necesaria porque los tamaños de bloque y de caché son desconocidos. Además, este modelo de gestión automática se aproxime más cachés físicas distintas del nivel entre la memoria principal y el disco: que bloquean para reemplazar normalmente se decide por el hardware de caché de acuerdo con una estrategia de reemplazo de páginas fijo, no por un programa general.

Pero ¿cómo vamos a diseñar algoritmos que minimizan el número de transferencias en bloque si no sabemos la estrategia de sustitución pagina? Una estrategia de reemplazo de páginas de confrontación siempre podía desalojar el bloque siguiente al que se accederá, reduciendo efectivamente M a 1 en cualquier algoritmo. Para evitar este problema, el modelo-cache ajeno asume una caché ideal que defiende un punto de vista utópico: reemplazo de páginas es óptimo, y la caché es totalmente asociativa. Estos supuestos son importantes para entender, y parecerán poco realista, pero en teoría están justificadas como se describe en la siguiente sección.

El primer supuesto – sustitución de pagina optima - especifica que la estrategia de sustitución de páginas conoce el futuro y siempre desaloja la página que se accederá más lejana en el futuro. Este ideal omnisciente es exactamente lo contrario de la estrategia de página de reemplazo acusatorio descrito anteriormente. Por el contrario, por supuesto, las memorias caché del mundo real no conocen el futuro, y emplean estrategias de sustitución de páginas más realistas, como el desalojo del bloque utilizado menos recientemente (LRU) o desalojar el bloque más antiguo (FIFO).

El segundo supuesto - plena asociatividad - puede no parecer un supuesto para aquellos más familiarizados con memoria externa que con cachés del mundo real: dice que cualquier bloque puede ser almacenado en cualquier lugar de la memoria caché. En contraste, la mayoría de cachés por encima del nivel entre la memoria principal y el disco tienen asociatividad limitada lo que significa que cada bloque pertenece a un grupo de entre 1 y M, por lo general el módulo de dirección de bloque M, y como máximo una pequeña constante c de bloques de un grupo común puede ser almacenados en la memoria caché a la vez. Típicos cachés del mundo real o bien se asignan con indicado (c = 1) o 2 vías asociativas (c = 2). Algunos cachés tienen más asociatividad - 4 vías o de 8 vías -, pero la constante c es ciertamente limitado. Dentro de cada grupo, cachés pueden aplicar una estrategia de página de reemplazo como FIFO o LRU o OPT; pero una vez que el clúster se llena, otro bloque debe ser desalojado. A primera vista, esta política parece limitar M a c en el peor de los casos.

2.3 JUSTIFICACIÓN DEL MODELO

Frigo et al. [FLPR99, Pro99] justificar el modelo ideal-cache descrito en el apartado anterior por un conjunto de reducciones que modifican un algoritmo ideales-cache para operar en un modelo de caché más realista. El tiempo de ejecución del algoritmo se degrada un poco, pero en la mayoría de los casos por solamente un factor constante. Aquí resumimos los principales pasos, sin entrar en los detalles de las pruebas.

2.3.1 ESTRATEGIA DE REEMPLAZO

La primera reducción elimina (omnisciente) óptima la estrategia de reemplazo prácticamente irrealizable que utiliza información sobre las solicitudes futuras.

Lema 1 ([FLPR99, Lemma 12]). Si un algoritmo hace transferencias T de memoria en una memoria caché de tamaño M / 2 con el reemplazo óptimo, entonces tiene en la mayoría de las transferencias de memoria 2T en un escondrijo de la talla M con LRU o reemplazo FIFO (y el mismo tamaño de bloque B).

En otras palabras, LRU y el reemplazo FIFO hacen tan bien como reemplazo óptimo hasta un factor constante de las transferencias de memoria y hasta un factor de desperdicio constante de la memoria caché. Este establecimiento situado en la competitividad de las LRU y FIFO se remonta a un documento de Sleator y Tarjan [ST85a] 1.985. En el ajuste algorítmico, siempre y cuando el número de transferencias de memoria depende polinómicamente en el tamaño de la caché M, a continuación, reducir a la mitad M será sólo afectan el tiempo de ejecución por un factor constante. Más en general, lo que se necesita es la condición regularidad que T (B, M) = O (T (B; M / 2)).

Así tenemos esta reducción:

Corolario 1 ([FLPR99 Corolario 13]). Si el número de transferencias de memoria realizados por un algoritmo en una memoria caché con el reemplazo óptimo, T (B; M), satisface la condición de regularidad, entonces el algoritmo hace £ (T (B, M)) transferencias de memoria en una memoria caché con LRU o reemplazo FIFO.

2.3.2 ASOCIATIVIDAD Y SUSTITUCIÓN AUTOMÁTICA

Las reducciones para convertir plena asociatividad en 1 vía asociatividad (sin asociatividad) y para convertir la sustitución automática en la gestión de memoria manual se combinan inseparablemente en una sola:

Lema 2 ([FLPR99, el Lema 16]). Por alguna constante ®> 0, una caché LRU de ®M tamaño y tamaño de bloque B se puede simular en el espacio M tal que el acceso a un bloque de toma O (1) hora.

La idea básica es usar las funciones de hash 2-universales para implementar la asociatividad con solamente O (1) conflictos. Por supuesto, esta reducción requiere el conocimiento de B y M.

3 ALGORITMOS

Siguiente nos fijamos en cómo hacer que algunas transferencias de memoria en el modelo-cache ajeno. Comenzamos con algunos algoritmos simples pero sin embargo útiles a base de "escaneo" en la Sección 3.1. Entonces miramos varios ejemplos del enfoque de divide y vencerás en la Sección 3.2. Sección 3.3 considera que el problema de la clasificación clásica, donde el nivel de divide y enfoque -conquer (por ejemplo, ordenamiento por mezcla) no es óptima, y se necesitan técnicas más sofisticadas. Por último, la Sección 3.4 da referencias a cache-ajenos algoritmos en los algoritmos de la geometría y de gráficos computacionales.

3.1 Digitalización

3.1.1 Transversal y Agregados

Para hacer que la existencia de algoritmos de caché ajeno eficientes más intuitivos, vamos a empezar con un ejemplo trivial. Supongamos que tenemos que recorrer

...