A study on the acceleration of search heuristics in programmable logic
View/ Open
Date
2016Author
Advisor
Co-advisor
Academic level
Graduation
Title alternative
Um estudo sobre a aceleração de heurísticas de busca em lógica programável
Subject
Abstract
Search 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 ...
Search 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%. ...
Abstract in Portuguese (Brasil)
Algoritmos 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 dis ...
Algoritmos 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%. ...
Institution
Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Engenharia de Computação.
Collections
This item is licensed under a Creative Commons License