Virtualization and implementation of algorithms in FPGA: an modulo scheduling algorithm for coarse-grained reconfigurable archi- tecture

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.In most stream applications for embedded systems, the innermost loop codes domi- nate the total execution time. Coarse-grained reconfigurable architecture (CGRA) could achieve high performance to implement innermost loop codes by using soft- ware pipelining approach. More specifically, modulo scheduling which is a software pipelining approach are used. This technique improve the performance by overlap- ping the loop iteration execution. In additional, CGRA are energetically efficient in terms of operations/watts. However, the previous modulo scheduling approa- ches are time-consuming and commercial CGRA and tools are not available in the market. This work proposes to implement a Virtual CGRA as a layer in a com- mercial FPGA, and moreover, we present the first hardware-based implementation of a modulo scheduling algorithm. The CGRA is based on a global interconnection network. An interconnection design exploration is performed by using crossbar and multistage interconnection network in a commercial target FPGA. The proposed architectures are compared to a baseline 2D-mesh CGRA mesh, since most previ- ous work are based on it. The experimental results demonstrate that the proposed global interconnection architecture has area/delay comparable to the 2D-mesh. In addition, since the global approach simplify the modulo scheduling algorithm, we present the first FPGA hardware-based implementation. The modulo scheduling hardware implementation is from 4x up to 7x faster than a software core approach. Moreover, the area overhead of our modulo scheduling hardware is less than 10% of the CGRA area. Although the implementation is based on a greedy modulo sche- duling algorithm, the experimental results demonstrate that the algorithm could mapped a multimedia benchmark set on a target Virtual CGRA implemented on the top of a commercial FPGA. The CGRA evaluated architectures have 16, 32 and 64 execution units 32 bit width. Finally, we show that the proposed approach is xiiifast enough to be used in dynamic framework to map loop code to a target CGRA accelerator in run-time.Coordenação de Aperfeiçoamento de Pessoal de Nível Superio