Ponto de partida para algoritmos alheios ao cache?

9

Eu sou interessante em aprender mais sobre algoritmos e estruturas de dados que ignoram o cache, mas existem tantos trabalhos por aí que honestamente não sei por onde começar. Encontrei a tese original do Prokup sobre o assunto, o que parece ser um bom ponto de partida, mas se houver uma introdução simples e acessível ao assunto, prefiro começar por aí. Existe uma referência padrão sobre o assunto?

Obrigado!

templatetypedef
fonte

Respostas:

7

Ainda acho um dos artigos originais (também o encontrei no Google Scholar) bastante interessante e claro ... nesse caso, não é extremamente "científico-y":

M. Frigo, CE Leiserson, H. Prokop e S. Ramachandran. Algoritmos que ignoram o cache. Em Anais do 40º Simpósio IEEE de Fundamentos da Ciência da Computação (FOCS 99), p.285-297. 1999.

Além disso, aqui estão as palestras em vídeo de Erik Demaine sobre co algos, que também são muito boas.

Dervin Thunk
fonte