Algoritmo de Posicionamento Polinomial para FPGA Baseado em Travessia de Grafos

• Ano de defesa: 2013
• Autor(a) principal: Cardoso, Luciana Rocha
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Viçosa; BR; Metodologias e técnicas da Computação; Sistemas de Computação; Mestrado em Ciência da Computação; UFV
• Palavras-chave em Português: FPGA; Posicionamento; Tempo de execução; Positioning; Execution time; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://locus.ufv.br/handle/123456789/2662

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.