Algoritmos e estruturas de dados alheios ao cache são algo bastante novo, introduzido por Frigo et al. em algoritmos alheios a cache, 1999 . A tese de Prokop do mesmo ano também apresenta as idéias iniciais.
O artigo de Frigo et al. apresentar alguns resultados experimentais mostrando o potencial da teoria e dos algoritmos e estruturas de dados que não fazem parte do cache. Muitas estruturas de dados que ignoram o cache são baseadas em árvores de pesquisa estáticas. Os métodos de armazenamento e navegação nessas árvores foram desenvolvidos bastante, talvez mais notavelmente por Bender et al. e também por Brodal et al. Demaine oferece uma boa visão geral .
O trabalho experimental de investigar o comportamento do cache na prática foi realizado pelo menos por Ladner et al. em Uma comparação de árvores de pesquisa estática inconscientes e desconhecidas do cache usando a instrumentação de programa, 2002 . Ladner et al. comparou o comportamento do cache dos algoritmos que resolvem o problema de pesquisa binária, usando o algoritmo clássico, o algoritmo que não faz parte do cache e o algoritmo que reconhece o cache. Cada algoritmo foi comparado com métodos de navegação implícita e explícita. Além disso, a tese de Rønn, 2003 analisou os mesmos algoritmos com detalhes bastante altos e também realizou testes ainda mais detalhados dos mesmos algoritmos que Ladner et al.
Minha pergunta é
Houve alguma pesquisa mais recente sobre benchmarking do comportamento do cache de algoritmos alheios ao cache na prática desde então? Estou especialmente interessado no desempenho das árvores de pesquisa estática, mas também ficaria feliz com quaisquer outros algoritmos e estruturas de dados que não fazem cache.
Respostas:
Você já cobriu bastante a pesquisa em segundo plano sobre algoritmos que ignoram o cache. Em termos de benchmarking e resultados práticos, vejo este artigo recente da Intel como uma leitura interessante:
Uma abordagem sinérgica da computação de produtividade em desktops multicore baseados em x86
fonte