Show simple item record

dc.contributor.advisorNazar, Gabriel Lucapt_BR
dc.contributor.authorMiranda, Marina Silvapt_BR
dc.date.accessioned2017-01-19T02:30:17Zpt_BR
dc.date.issued2016pt_BR
dc.identifier.urihttp://hdl.handle.net/10183/151039pt_BR
dc.description.abstractSearch algorithms are used in several applications nowadays; they are used for finding the best path from a place to another in a city or between two nodes in a complex graph in a data base system. There is a growing interest in accelerating applications, such as these, in Field Programmable Gate Arrays (FPGAs). An FPGA is an integrated circuit whose logic cells can be configured by the user, at any time. Lately these devices integrate processors with the programmable logic, an example of this is the ZYNQ device from Xilinx with an ARM processor embedded. This work presents a hybrid design of the best path search algorithm A*, in which most of the algorithm was implemented to run in a processor and a part was selected to be implemented in hardware (VHDL). The selected part was the priority queue, which is based on a min binary heap, that the A* algorithm utilizes.The ZEDBOARD (AVNET/Digilent) with a ZYNQ inside was used to develop the proposed solution, which can improve the performance of a min binary heap implemented purely in software by 68.8%.en
dc.description.abstractAlgoritmos de busca estão sendo utilizados em diversas aplicações atualmente; são usados para encontrar o melhor caminho entre um lugar e outro em uma cidade ou entre dois nós em um grafo complexo em um sistema de banco de dados. Existe uma tendência cada vez maior de acelerar aplicações, como estas, em Field Programmable Gate Arrays (FPGAs). Um FPGA é um circuito integrado no qual as células lógicas podem ser reconfiguradas pelo usuário/desenvolvedor a qualquer momento. Recentemente, estes dispositivos integram processadores com lógica programável, um exemplo disso é o ZYNQ da Xilinx com um processador ARM embarcado. Este trabalho apresenta um design híbrido do algoritmo de busca de melhor caminho A*, no qual a maior parte do algoritmo é implementada para rodar em um processador e a uma parte foi selecionada para implementação em hardware. A parte implementada em hardware (VHDL) é a lista de prioridades que o A* utiliza, a qual é baseada na estrutura de um heap binário. A placa ZEDBOARD (AVNET/Digilent) com um ZYNQ dentro foi escolhida para desenvolver a solução proposta, que melhora a performance de um heap binário (lista de prioridades) implementada puramente em software em 68.8%.pt_BR
dc.format.mimetypeapplication/pdfpt_BR
dc.language.isoengpt_BR
dc.rightsOpen Accessen
dc.subjectFPGAen
dc.subjectCircuito integradopt_BR
dc.subjectProgrammable logicen
dc.subjectProcessoren
dc.subjectZYNQen
dc.subjectPriority queueen
dc.subjectA* algorithmen
dc.subjectHeuristicsen
dc.titleA study on the acceleration of search heuristics in programmable logicpt_BR
dc.title.alternativeUm estudo sobre a aceleração de heurísticas de busca em lógica programável pt
dc.typeTrabalho de conclusão de graduaçãopt_BR
dc.contributor.advisor-coLelis, Levipt_BR
dc.identifier.nrb001009653pt_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.date2016pt_BR
dc.degree.graduationEngenharia de Computaçãopt_BR
dc.degree.levelgraduaçãopt_BR


Files in this item

Thumbnail
   

This item is licensed under a Creative Commons License

Show simple item record