Repositório Digital

A- A A+

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

.

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

Mostrar registro completo

Estatísticas

Título Programação dinâmica eficiente com algoritmos Cache-Oblivious
Outro título Efficient cache-oblivious dynamic programming algorithms
Autor Rodrigues, Félix Carvalho
Orientador Ritt, Marcus Rolf Peter
Co-orientador Buriol, Luciana Salete
Data 2008
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Algoritmos
Memoria : Computadores
Memoria cache
Programação dinâmica
[en] Bin-packing problem
[en] Cache-oblivious algorithms
[en] Dynamic programming
[en] Unbounded knapsack problem
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.
Abstract 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.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/16007
Arquivos Descrição Formato
000680180.pdf (681.7Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.