Programação dinâmica eficiente com algoritmos Cache-Oblivious

Abstract

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.

Memory in modern computers is usually organized in a complex hierarchy. Thus, it is important to design algorithms that use the cache efficiently. Moreover, the configuration of memory and cache varies greatly from a computer to another. Therefore, it is necessary that the algorithms developed depend on the minimum information from the machine to use the cache in a efficient way. In the ideal-cache model, there are two levels of memory. The first one has random access and is infinite (main memory), but has a cost associated with its access, while the other can be quickly accessed, but has a finite size. An algorithm is said to be cache-oblivious if it uses the cache efficiently even without having any information about the cache. To measure the complexity of such a algorithm, it is not enough to use only the work complexity. Thus, we also use the cache-miss complexity, which can be measured using the ideal-cache model, measuring how efficiently an algorithm accesses the cache. Many problems have not yet been analyzed for their cache efficiency. An example of such problems is the knapsack problem. Given a bag of a certain size and a number of items with a weight and profit associated to it, discover the combination of items that fit in the bag such that the profit is maximized. The solution to this problem is of utmost importance to several areas of computer science, and subproblem of many other problems. An example of such problem is the Bin-Packing, which has many practical applications. In this work we present a cache-oblivious algorithm to the Unlimited Knapsack Problem. Furthermore, we also present a research and analysis of problems in which a cacheoblivious algorithms has already been developed.