Um algoritmo de posicionamento e roteamento polinomial para arquiteturas reconfiguráveis de grão grosso com redes multiestágio

Abstract

Diferentes arquiteturas estão sendo utilizadas para o desenvolvimento de sistemas dedicados. Uma arquitetura reconfigurável muito difundida no mercado são os FPGAs (Field Programmable Gate Arrays), eles são uma estrutura flexível e eficiente, mas que exigem um grande esforço de configuração, mapeamento, pois são reconfiguráveis no nível de bits. Esta dissertação propõe utilizar uma arquitetura hibrida de grão grosso em duas dimensões sobre o FPGA de forma a reduzir a complexidade do mapeamento. A arquitetura hibrida é baseada em conexões locais e globais. As conexões locais são entre vizinhos (leste, oeste, norte e sul). As conexões globais são feitas por redes multiestágios. Além disso, são avaliados três algoritmos de posicionamento e roteamento (P&R) para as conexões locais com complexidade polinomial. Os algoritmos de posicionamento são baseados na busca em profundidade no grafo, priorizando ou não o caminho crítico.

Differents architectures have been proposed for embedded systems. The FPGAs (Field Programmable Gate Array) has an efficient and flexible structure. However it requires a great effort of configuration and mapping at bit level. This work proposes an hybrid 2-dimension architecture coarse grain, as a logic layer upon the FPGAs. This approach reduces the mapping complexity. The hybrid architecture are based on local and global connections. The local connections consist of neighbour links (east, west, north and south). The global connections are done by multistage interconnection network (MIN). Furthermore, three placement and routing polynomial algorithms are evaluated to perform the local connections. These algorithms are depth first search based and prioritize the critical path.