Algoritmo de Posicionamento Polinomial para FPGA Baseado em Travessia de Grafos

Abstract

O hardware reconfigurável é uma solução intermediária entre software e hardware, oferece a flexibilidade do software e o desempenho do hardware. Nos anos oitenta, os FPGAs surgiram como circuitos reconfiguráveis comerciais e escaláveis. Possuem muita flexibilidade e resolveram com sucesso vários problemas nas últimas décadas com uma aceleração de 2 a 3 ordens de grandeza em relação à versão em software. Além disso, as aplicações são heterogêneas e demandam soluções que se adaptem em tempo de execução. Com a evolução da tecnologia, a complexidade do FPGA aumentou significativamente passando de centenas de blocos lógicos/interconexões para a ordem de milhões. Este avanço possibilita mais desempenho e flexibilidade, entretanto a complexidade para mapear as aplicações aumenta significativamente. Sendo que para soluções geradas em tempo de execução, o tempo para mapear as aplicações é mais crítico. O mapeamento é realizado em dois passos: posicionamento e roteamento. O problema de encontrar a melhor maneira de posicionar uma computação nos blocos lógicos (posicionamento) é NP-Completo. Uma vez posicionados, os blocos devem ser interligados (roteamento) que também é um problema NP-completo. Ambos os problemas são grandes desafios atuais para as ferramentas de FPGA. Esta dissertação tem foco no problema de posicionamento. Várias heurísticas já foram propostas ao longo das três últimas décadas, porém poucas apresentaram um desempenho adequado para posicionar e rotear blocos lógicos em tempo de execução. Este trabalho propõe uma exploração do espaço de projeto de um algoritmo polinomial de posicionamento baseado em travessia em grafos. Variações de travessia (largura e profundidade) são propostas e a qualidade da solução é avaliada medindo o tempo de execução, o caminho crítico e o número total de conexões. As variações tem foco nos pontos com múltiplos fanout e fanouts reconvergentes.

Nowadays, many applications requires high performance solutions, which could not be achieved by a software approach. Problems in bioinformatics, simulations, telecommunications, encryption, compression of large volumes of data are examples of these applications. A hardware approaches are high-performance, however, these approaches have high design costs. The reconfigurable hardware is an intermediate solution between software and hardware, as it offers the flexibility of the software and the performance of the hardware. Since 1980s, FPGA circuits have emerged as commercial and scalable platform for reconfigurable hardware. Several problems have been modeled and implemented by using FPGA with acceleration from 2 to 3 orders of magnitude. However, the FPGA complexity has significantly increased from hundreds of logical blocks/interconnections to the order of millions in last decades. First, the application should be mapped to the FPGA. The mapping consists on two steps: placement and routing. The placement will map the computing elements in logic blocks. This step is NP-Complete. Then, the routing step will perform the interconnections between the logic blocks. It is also a NP-complete problem. Both problems are one of current challenges in FPGA tools. Several heuristics have been proposed, but few of them are suitable for run-time approach. This dissertation proposes an exploration of the design space of a polynomial algorithm based on graph traversal. Depth-first and Breadth-first traversals are evaluated by looking the reconvergent fanout and high fanout nodes. Experimental results analyze the execution time, critical path, distribution degree and total wire length.