Mostrar registro simples

dc.contributor.advisorRitt, Marcus Rolf Peterpt_BR
dc.contributor.authorRodrigues, Félix Carvalhopt_BR
dc.date.accessioned2009-06-04T04:13:08Zpt_BR
dc.date.issued2008pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/16007pt_BR
dc.description.abstractA 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.pt_BR
dc.description.abstractMemory 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.en
dc.format.mimetypeapplication/pdf
dc.language.isoporpt_BR
dc.rightsOpen Accessen
dc.subjectAlgoritmospt_BR
dc.subjectDynamic programmingen
dc.subjectCache-oblivious algorithmsen
dc.subjectProgramação dinâmicapt_BR
dc.subjectUnbounded knapsack problemen
dc.subjectMemoria cachept_BR
dc.subjectMemoria : Computadorespt_BR
dc.subjectBin-packing problemen
dc.titleProgramação dinâmica eficiente com algoritmos Cache-Obliviouspt_BR
dc.title.alternativeEfficient cache-oblivious dynamic programming algorithms en
dc.typeTrabalho de conclusão de graduaçãopt_BR
dc.contributor.advisor-coBuriol, Luciana Saletept_BR
dc.identifier.nrb000680180pt_BR
dc.degree.grantorUniversidade Federal do Rio Grande do Sulpt_BR
dc.degree.departmentInstituto de Informáticapt_BR
dc.degree.localPorto Alegre, BR-RSpt_BR
dc.degree.date2008pt_BR
dc.degree.graduationCiência da Computação: Ênfase em Ciência da Computação: Bachareladopt_BR
dc.degree.levelgraduaçãopt_BR


Thumbnail
   

Este item está licenciado na Creative Commons License

Mostrar registro simples