Aceleración de simulaciones de caché de almacenamiento de varios niveles mediante detección de rodillas

Resumen

Las jerarquías de caché de almacenamiento incluyen topologías diversas, parámetros y políticas variados, y dispositivos con características de rendimiento diferentes. La simulación permite una exploración eficiente de su espacio de configuración mientras se evitan experimentos físicos costosos. Las curvas de relación de fallos (MRC, por sus siglas en inglés) caracterizan eficientemente el rendimiento de una caché en un rango de tamaños de caché, revelando «puntos clave» para la simulación de caché, como las rodillas en la curva que siguen inmediatamente a las escarpadas pendientes. Desafortunadamente, no existen técnicas automatizadas para encontrar eficientemente los puntos clave en las MRC, y la aplicación cruzada de los algoritmos de detección de rodillas existentes produce resultados inexactos. Presentamos un marco de varios estágios que identifica puntos clave en cualquier MRC, tanto para algoritmos de expulsión basados en pila (por ejemplo, LRU) como para algoritmos de expulsión más sofisticados (por ejemplo, ARC). Nuestro enfoque localiza rápidamente a los candidatos utilizando una muestra basada en hash eficiente, simplificación de curvas, detección de rodillas y filtros de posprocesamiento novedosos. Introducimos el método Z, un nuevo algoritmo de detección de rodillas múltiples que emplea la detección de valores atípicos estadísticos para elegir puntos prometedores de manera robusta y eficiente.