Acelerando simulações de cache de armazenamento em multi-níveis usando detecção de joelhos

Resumo

Hierarquias de armazenamento em cache incluem topologias diversificadas, parâmetros e políticas variados e dispositivos com características de desempenho diferentes. A simulação permite uma exploração eficiente do espaço de configuração enquanto evita experimentos físicos caros. Curvas de Taxa de Falhas (MRCs) caracterizam eficientemente o desempenho de um cache em uma variedade de tamanhos de cache, revelando "pontos-chave" para simulação de cache, como joelhos na curva que seguem imediatamente encostas íngremes. Infelizmente, não existem técnicas automatizadas para encontrar eficientemente pontos-chave em MRCs, e a aplicação cruzada de algoritmos de detecção de joelhos existentes produz resultados imprecisos. Apresentamos uma estrutura em multi-etapas que identifica pontos-chave em qualquer MRC, tanto para algoritmos de expulsão baseados em pilha (por exemplo, LRU) quanto para algoritmos de expulsão mais sofisticados (por exemplo, ARC). Nossa abordagem localiza rapidamente candidatos usando amostragem baseada em hash eficiente, simplificação de curva, detecção de joelhos e filtros de pós-processamento novos. Introduzimos o Z-Method, um novo algoritmo de detecção de multi-joelhos que emprega detecção de valores estatísticos atípicos para escolher pontos promissores de forma robusta e eficiente.