==== Algoritmos cache-oblivious ==== {{CO_model.png?250}} 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: [[http://www.inf.ufrgs.br/~fcrodrigues|Félix C. Rodrigues]]) === Referências ===