Los algoritmos y las estructuras de datos ajenos a la memoria caché son algo bastante nuevo, presentado por Frigo et al. en algoritmos ajenos a la memoria caché, 1999 . La tesis de Prokop del mismo año también presenta las primeras ideas.
El artículo de Frigo et al. presentar algunos resultados experimentales que muestran el potencial de la teoría y de los algoritmos y estructuras de datos ajenos a la memoria caché. Muchas estructuras de datos ajenas al caché se basan en árboles de búsqueda estáticos. Los métodos de almacenamiento y navegación de estos árboles se han desarrollado bastante, quizás más notablemente por Bender et al. y también por Brodal et al. Demaine da una buena visión general .
El trabajo experimental de investigar el comportamiento del caché en la práctica fue realizado al menos por Ladner et al. en una comparación de Cache Aware y Cache Oblivious Static Search Trees usando Program Instrumentation, 2002 . Ladner y col. comparó el comportamiento del caché de los algoritmos que resuelven el problema de búsqueda binaria, utilizando el algoritmo clásico, el algoritmo ajeno al caché y el algoritmo compatible con el caché. Cada algoritmo se comparó con métodos de navegación implícitos y explícitos. Además de esto, la tesis de Rønn, 2003 analizó los mismos algoritmos con bastante detalle y también realizó pruebas aún más exhaustivas de los mismos algoritmos que Ladner et al.
Mi pregunta es
¿Ha habido alguna investigación más reciente sobre la evaluación comparativa del comportamiento de la caché de los algoritmos ajenos a la caché en la práctica desde entonces? Estoy especialmente interesado en el rendimiento de los árboles de búsqueda estáticos, pero también estaría contento con cualquier otro algoritmo y estructuras de datos ajenos a la memoria caché.
Respuestas:
Ya ha cubierto bastante bien la investigación de antecedentes sobre algoritmos ajenos a la memoria caché. En términos de evaluación comparativa y resultados prácticos, veo este reciente artículo de Intel como una lectura interesante:
Un enfoque sinérgico para la computación de rendimiento en computadoras de escritorio multinúcleo basadas en x86
fuente