Ferramentas de Utilizador

Ferramentas de Site


algoritmos_cache-oblivious

Algoritmos cache-oblivious

A memória nos computadores modernos geralmente está organizada em uma hierarquia complexa. Dessa forma, torna-se importante projetar algoritmos que utilizem a cache de forma eficiente. Além disso, as configurações da memória e da cache tem grande va- riação de computador para computador. Assim, é necessário também que os algoritmos desenvolvidos dependam o mínimo possível de informações da máquina para usar a cache eficientemente.

No modelo de cache ideal, existem dois níveis de memória. Uma é tem acesso ale- atório e é infinita (memória principal), porém tem um custo associado ao seu acesso, enquanto que a outra é de acesso rápido, porém com um tamanho finito.

Um algoritmo é dito cache-oblivious se ele usa a cache de forma eficiente mesmo sem ter nenhuma informação sobre a cache. Para medirmos a complexidade desse tipo de algoritmo, não basta utilizarmos somente a complexidade do número de instruções executadas. Dessa maneira, utilizamos também a complexidade de cache-misses, que pode ser medida utilizando o modelo de cache ideal, para medir o quão eficientemente um algoritmo acessa a cache.

Existem muitos problemas ainda não analisados quanto a sua eficiência de cache.

(Texto e imagem: Félix C. Rodrigues)

Referências

  • Ulrich Meyer, Peter Sanders, and Jop Sibeyn, editors. Algorithms for Memory Hierarchies, chapter 8 – Cache-oblivous algorithms. LNCS. Springer, 2003.
  • Matteo Frigo. Portable High-Performance Programs. PhD thesis, MIT, 1999.
  • M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proc. 40th IEE Sympos. Found. Comp. Sci., pages 285–297, 1999.
  • Lars Arge, Gerth Stolting Brodal, and Rolf Fagerberg. Cache-oblivious data structures. In Handbook on Data Structures and Applications, 2004.
  • Rezaul Alam Chowdhury and Vijaya Ramachandran. Cache-oblivious dynamic programming. In SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 591–600, New York, NY, USA, 2006. ACM. (doi:10.1145/1109557.1109622)
  • Frederik Rønn. Cache-oblivious searching and sorting. Master's thesis, University of Copenhagen, 2003.
  • Jesper Holm Olsen and Søren Christian Skov. Cache-oblivious algorithms in practice. Master's thesis, University of Copenhagen, 2002.
  • Rezaul Alam Chowdhury. Experimental evaluation of an efficient cache-oblivious lcs algorithm. Technical Report TR-05-43, University of Texas, Austin, October 2005.

algoritmos_cache-oblivious.txt · Esta página foi modificada pela última vez em: 2010/01/18 15:45 (Edição externa)