Programação dinâmica eficiente com algoritmos Cache-Oblivious / Efficient cache-oblivious dynamic programming algorithms

AUTOR(ES)
DATA DE PUBLICAÇÃO

2009

RESUMO

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 variaçã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 aleató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. Um desses problemas é o Problema da Mochila. Nele, dado uma mochila de um certo tamanho e um conjunto de itens com um peso e um lucro associado, pede-se que se encontre a combinação de itens que caibam na mochila que resultem no maior lucro acumulado. Esse problema é de extrema importância para várias áreas da computação, sendo subproblema de muitos problemas. Um desses problemas é o Bin-Packing, de inúmeras aplicações práticas. Apresentamos, nesse trabalho, um algoritmo cache-oblivious para o Problema da Mochila Ilimitado. Além disso, apresentamos também uma pesquisa e análise de problemas em que já existem algoritmos cache-oblivious desenvolvidos.

ASSUNTO(S)

algoritmos dynamic programming cache-oblivious algorithms programação dinâmica unbounded knapsack problem memoria cache memoria : computadores bin-packing problem

ACESSO AO ARTIGO

Documentos Relacionados