Índice
-
- INF05010: Otimização combinatória
- INF05016/CMP 588: Algoritmos avançados
- CMP612: Algorithms
- CMP268: Técnicas de busca heurística
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)