A study on the acceleration of search heuristics in programmable logic

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 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%.

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%.