SISTEMAS OPERATIVOS-CACHE AJENO ESTRUCTURA DE DATOS.

Algoritmos-Cache Ajeno y Estructuras de Datos

Abstract. Una dirección reciente en el diseño de algoritmos de caché-eficientes y eficaces de disco y estructuras de datos es la noción de olvido caché, introducido por Frigo, Leiserson, Prokop, y Ramachandran en 1999. algoritmos de caché ajeno buen desempeño en una jerarquía de memoria multinivel sin conociendo los parámetros de la jerarquía, sólo el conocimiento de la existencia de una jerarquía. De manera equivalente, un único algoritmo de caché ajeno es eficiente en todas las jerarquías de memoria al mismo tiempo. Si bien esos resultados podrían parecer imposible, un cuerpo reciente trabajo ha desarrollado algoritmos y estructuras de datos-cache ajeno que realizan tan bien o casi tan bien como estructuras externas de memoria estándar que requieren conocimiento de la cache / tamaño de la memoria y la transferencia de bloques de tamaño. Aquí se describen varios de estos resultados con la intención de elucidar las técnicas detrás de su diseño. Tal vez el más interesante de estos resultados son las estructuras de datos, que forman los bloques de construcción en general inmediatamente conducen a varios resultados algorítmicos.

1. Información general

Suponemos que el lector está familiarizado con la motivación para el diseño de algoritmos de caché-eficiente y eficaz de disco: jerarquías de memoria multinivel son cada vez más prominente, y sus costos en un factor dominante de tiempo de ejecución, por lo que la velocidad es crucial para minimizar estos costos . Comenzamos en la Sección 2, con una descripción del modelo de caché ajeno, después de una breve revisión de la modelo externo-memoria estándar. Luego, en la Sección 3 consideramos algunos algoritmos de caché-ajeno sencilla a moderadamente complejo: inversión, operaciones de matriz y de clasificación. La mayor parte de este trabajo culmina con el papel que primero se define la noción de algoritmos de caché ajeno [FLPR99]. A continuación en las secciones 4 y 5 se examinan las estructuras de datos estáticas y dinámicas-cache ajeno que se han desarrollado, sobre todo en los últimos años (2000 - 2003). Finalmente, la Sección 6 resume dónde estamos y qué direcciones pueden ser interesantes a seguir en el futuro (cercano).

1. Modelos

1.  Modelo Memoria Externa

Para contrastar con el modelo cache externo, primero revisamos el modelo estándar de la jerarquía de memoria de dos niveles con transferencias de bloques. Este modelo es conocido indistintamente como el modelo externo-memoria, el modelo de E / S, el modelo de acceso a disco, o el modelo-cache cuenta (para contrastar con olvido de caché). La referencia estándar para este modelo es Aggarwal y de Vitter 1988 papel [AV88], que también analiza el coste de la memoria de transferencia de la clasificación en este modelo. Versiones especiales del modelo se consideraron antes, por ejemplo, por Floyd en 1972 [Flo72] en su análisis del coste de memoria de transferencia de la transposición de la matriz.

El modelo define un ordenador como teniendo dos niveles (véase la Figura 1):

1. el caché que está cerca de la CPU, barato de acceso, pero limitado en el espacio; y
2.  el disco que es distante de la CPU, costoso de acceso, pero casi ilimitada en el espacio.

Utilizamos los términos "caché" y "disco" para los dos niveles para que los costos relativos clara (caché es más rápido que el disco); otros papeles utilizan ambigua "memoria" para hacer referencia a nivel lento (cuando se compara con caché) o el nivel rápido (al comparar en el disco). Utilizamos el término "memoria" para referirse genéricamente a todo el sistema de la memoria, en particular, la orden total en la que se almacenan los datos.

El aspecto central del modelo externo-memoria es que las transferencias entre la caché y disco implican bloques de datos. Específicamente el disco se divide en bloques de elementos de B cada uno, y acceder a un elemento de copias de disco toda su bloque de memoria caché,. El caché puede almacenar hasta bloques M / B, para un tamaño total de los elementos M, M> B. Antes de ir a buscar a una cuadra de disco cuando la memoria caché ya está lleno, el algoritmo debe decidir qué bloque para desalojar de la memoria caché.

Muchos algoritmos se han desarrollado en este modelo; ver encuesta de Vitter [Vit01]. Una de sus mayores ventajas, en contraste con una variedad de otros modelos, es que el algoritmo tiene que preocuparse de sólo dos niveles de memoria, y sólo dos parámetros. Naturalmente, sin embargo, los algoritmos existentes dependen crucialmente de B y M. Otro punto a destacar es que el algoritmo (al menos en principio) de forma explícita cuestiones leer y escribir peticiones al disco, y (de nuevo, en principio) gestiona de forma explícita la caché. Estas propiedades desaparecerán con el modelo-cache ajeno.

2.2 MODELO CACHE EXTERNO

El modelo de caché externo fue introducido por Frigo, Leiserson, Prokop, y Ramachandran en 1999 [FLPR99, Pro99]. Su principio idea es simple: diseñar externos - algoritmos de memoria sin saber B y M. Pero esta sencilla idea tiene varias consecuencias sorprendentemente poderosas.

Una consecuencia es que, si un algoritmo de caché externo funciona bien entre los dos niveles de la jerarquía de memoria (nominalmente llamados caché y disco), entonces debe trabajar de forma automática así entre dos niveles adyacentes de la jerarquía de memoria. Esta consecuencia sigue casi inmediatamente, aunque se basa en cada dos niveles adyacentes que se modela como una memoria externa, cada presumiblemente con diferentes valores para los parámetros B y M, de tal manera que los bloques en los niveles de memoria más cerca de la subconjuntos almacenar CPU de niveles de memoria más lejos de la CPU - la propiedad inclusión [HP96, p. 723]. Otra consecuencia, si el número de transferencias de memoria es óptima hasta un factor constante entre dos niveles de memoria adyacentes, entonces cualquier combinación ponderada de estas cuentas (con los pesos correspondientes a las velocidades relativas de los niveles de memoria) está también a un factor constante de óptima. De esta manera, podemos diseñar y analizar algoritmos en un modelo de memoria de dos niveles, y obtener resultados de una jerarquía de memoria muchas de nivel arbitrario - siempre y cuando podamos hacer los algoritmos de caché-inconsciente.

Otra consecuencia, más práctico es auto-sintonización. Algoritmos de caché eficiente típicos requieren sintonización para varios parámetros de caché que no siempre están disponibles del fabricante y, a menudo difícil de extraer automáticamente. Sintonización de parámetros hace que la portabilidad del código difícil. Tal vez la primera y más obvia motivación para algoritmos de caché ajeno es la falta de tal sintonía: un único algoritmo debe funcionar bien en todas las máquinas sin modificaciones. Por supuesto, el código aún está sujeta a algunos ajustes, por ejemplo, dónde recortar el caso base de una recursión, pero tales optimizaciones no deben ser efectos directos de la memoria caché.

...