Virtualização e execução de algoritmos em FPGA: um algoritmo de modulo scheduling para arranjos reconfiguráveis de grão grosso

• Ano de defesa: 2014
• Autor(a) principal: Meireles Filho, Waldir Dénver Muniz
• 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: Programação (Matemática); Algoritmos; Modulo Scheduling; Software Pipeline; Arquitetura reconfigurável; Programming (Mathematics); Algorithms; Modulo scheduling; Pipeline software; Reconfigurable architecture; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: http://locus.ufv.br/handle/123456789/2671

Em muitas aplicações para sistemas embarcados, os laços mais internos dominam o tempo total de execução dos algorítimos. As arquiteturas reconfiguráveis de grão grosso (CGRA) alcançam um alto desempenho executando estes laços através de uma abordagem de software pipelining, mais especificamente através da técnica de modulo scheduling. Esta técnica melhora o desempenho fazendo a sobreposição de diversas iterações do laço em intervalos constantes. Os CGRA são energeticamente eficientes em termos de operações/watts. Por outro lado, as abordagens anteriores de modulo scheduling tem um tempo de execução elevado. Além disso os CGRAs e ferramentas comercias não estão disponíveis no mercado. Este trabalho propõe um CGRA virtual implementado como uma camada sobre um FPGA comercial. Além disso, apresentamos a primeira implementação de um algoritmo de modulo schedu- ling em hardware. O CGRA baseia-se em uma rede de interconexão global, através do uso de redes crossbar ou redes multiestágio implementadas em um FPGA comer- cial. As arquiteturas propostas foram comparadas com uma arquitetura CGRA 2D em malha, uma vez que a maioria dos trabalhos anteriores são baseados neste tipo de CGRA. Os resultados experimentais demonstram que a arquitetura com intercone- xão global proposta tem área/atraso comparável com a arquitetura 2D em malha. Além disso, uma vez que a abordagem global simplifica o algoritmo de escalona- mento, apresentamos também a implementação do modulo scheduling em hardware em um FPGA. Esta implementação em hardware é cerca de 4× a 7× mais rápida do que uma abordagem em software-core executando em um FPGA. A área ocupada pelo módulo de escalonamento em hardware é menor que 10% da área ocupada pelo CGRA. Embora a implementação seja baseada em um algoritmo guloso, os resulta- dos experimentais demonstram que o algoritmo pode mapear aplicações multimídia no CGRA virtual implementado no sobre um FPGA comercial. As arquiteturas xiCGRA avaliadas possuem 16, 32 e 64 unidades de processamento de 32 bits. Por fim, mostramos que a abordagem de escalonamento proposta é rápida o suficiente para mapear o código de um laço dinamicamente para o acelerador CGRA com um rede global.