Algoritmos de Posicionamento e Roteamento baseados em Travessia de Grafo para Arquiteturas Reconfiguráveis de Grão Grosso (CGRA)
Resumo
O hardware reconfigurável é flexível, eficiente energeticamente e oferece alto desempenho para vários domínios de aplicação. Os FPGAs são a tecnologia reconfigurável mais utilizada, entretanto o mapeamento da aplicação é NP-Completo. Os CGRAs simplificam o desenvolvimento de aplicações para hardware reconfigurável e alteram a granularidade das operações do nível de bit para o nível de palavras (8-32 bits). Este trabalho apresenta avanços no estado da arte para o problema de mapeamento em CGRA propondo novos algoritmos de travessia de grafos. As soluções alcançadas são ordens de grandeza mais rápidas sem comprometer a qualidade. Os algoritmos propostos foram 91x mais rápidos com uma redução de 1.7x nos recursos de balanceamento em comparação com a abordagem com Simulated Annealing.
Palavras-chave:
Arquiteturas Reconfiguráveis, CGRAs, Posicionamento, Roteamento
Referências
Canesche, M., Carvalho, W., Reis, L., Oliveira, M., Magalhaes, S., Jamieson, P., Nacif, J. M., and Ferreira, R. (2021). You only traverse twice: A yott placement, routing, and timing approach for cgras. ACM Trans. on Embedded Comp. Systems (TECS).
Canesche, M., Menezes, M., Carvalho, W., Torres, F., Jamieson, P., Nacif, J. A., and Ferreira, R. (2020). Traversal: A fast and adaptive graph-based placement and routing for cgras. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems.
Carvalho, O., Canesche, M., Reis, L., Torres, F., Jamieson, P., Silva, L., Nacif, J., and Ferreira, R. (2020). A design exploration of scalable mesh-based fullypipelined accelerators. In International Conf. on Field-Programmable Technology (ICFPT). IEEE.
Ferreira, R. and et al. (2007). A polynomial placement algorithm for data driven coarsegrained reconfigurable architectures. In IEEE Symposium on VLSI.
Ferreira, R. and et al (2013). A run-time graph-based polynomial placement and routing algorithm for virtual fpgas. In Field programmable Logic and Applications (FPL).
Gobieski, G. and et al. (2021). Snafu: an ultra-low-power, energy-minimal cgrageneration framework and architecture. In Int Symp on Computer Architecture (ISCA).
Kojima, T., Doan, N. A. V., and Amano, H. (2020). Genmap: A genetic algorithmic approach for optimizing spatial mapping of coarse-grained reconfigurable architectures. IEEE Transactions on Very Large Scale Integration (VLSI) Systems.
Lai, Y.-T., Lai, H.-Y., and Yeh, C.-N. (2005). Placement for the reconfigurable datapath architecture. In IEEE Symp on Circuits and Systems.
Liu, D. and et al (2018). Data-flow graph mapping optimization for cgra with deep reinforcement learning. IEEE Trans. on CAD of Integrated Circuits and Systems.
Murray, K. E. and et al (2020). Vtr 8: High-performance cad and customizable fpga architecture modelling. ACM Trans on Reconfigurable Technology and Systems (TRETS).
Nowatzki, T. and et al (2018). Hybrid optimization/heuristic instruction scheduling for programmable accelerator codesign. In Parallel Architectures and Compilation Tech.
Oliveira, W., Canesche, M., Reis, L., Nacif, J., and Ferreira, R. (2020). Design exploration of machine learning data-flows onto heterogeneous reconfigurable hardware. In Anais do XXI Simpósio em Sistemas Computacionais de Alto Desempenho. SBC.
Silva, L. B. D. and et al (2019). Ready: A fine-grained multithreading overlay framework for modern cpu-fpga dataflow applications. ACM Trans on Embedded Comp Systems.
Vieira, M., Canesche, M., Bragança, L., Campos, J., Silva, M., Ferreira, R., and Nacif, J. A. (2021). Reshape: A run-time dataflow hardware-based mapping for cgra overlays. In IEEE International Symposium on Circuits and Systems (ISCAS), pages 1–5. IEEE.
Walker, M. and et al. (2019). Generic connectivity-based cgra mapping via integer linear programming. In Field-Programmable Custom Computing Machines (FCCM).
Yin, S. and et al. (2017). Dfgnet: Mapping dataflow graph onto cgra by a deep learning approach. In IEEE Int Symp on Circuits and Systems (ISCAS).
Yoon, J. W. and et al. (2009). A graph drawing based spatial mapping algorithm for coarse-grained reconfigurable architectures. IEEE Trans on VLSI systems, 17(11).
Canesche, M., Menezes, M., Carvalho, W., Torres, F., Jamieson, P., Nacif, J. A., and Ferreira, R. (2020). Traversal: A fast and adaptive graph-based placement and routing for cgras. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems.
Carvalho, O., Canesche, M., Reis, L., Torres, F., Jamieson, P., Silva, L., Nacif, J., and Ferreira, R. (2020). A design exploration of scalable mesh-based fullypipelined accelerators. In International Conf. on Field-Programmable Technology (ICFPT). IEEE.
Ferreira, R. and et al. (2007). A polynomial placement algorithm for data driven coarsegrained reconfigurable architectures. In IEEE Symposium on VLSI.
Ferreira, R. and et al (2013). A run-time graph-based polynomial placement and routing algorithm for virtual fpgas. In Field programmable Logic and Applications (FPL).
Gobieski, G. and et al. (2021). Snafu: an ultra-low-power, energy-minimal cgrageneration framework and architecture. In Int Symp on Computer Architecture (ISCA).
Kojima, T., Doan, N. A. V., and Amano, H. (2020). Genmap: A genetic algorithmic approach for optimizing spatial mapping of coarse-grained reconfigurable architectures. IEEE Transactions on Very Large Scale Integration (VLSI) Systems.
Lai, Y.-T., Lai, H.-Y., and Yeh, C.-N. (2005). Placement for the reconfigurable datapath architecture. In IEEE Symp on Circuits and Systems.
Liu, D. and et al (2018). Data-flow graph mapping optimization for cgra with deep reinforcement learning. IEEE Trans. on CAD of Integrated Circuits and Systems.
Murray, K. E. and et al (2020). Vtr 8: High-performance cad and customizable fpga architecture modelling. ACM Trans on Reconfigurable Technology and Systems (TRETS).
Nowatzki, T. and et al (2018). Hybrid optimization/heuristic instruction scheduling for programmable accelerator codesign. In Parallel Architectures and Compilation Tech.
Oliveira, W., Canesche, M., Reis, L., Nacif, J., and Ferreira, R. (2020). Design exploration of machine learning data-flows onto heterogeneous reconfigurable hardware. In Anais do XXI Simpósio em Sistemas Computacionais de Alto Desempenho. SBC.
Silva, L. B. D. and et al (2019). Ready: A fine-grained multithreading overlay framework for modern cpu-fpga dataflow applications. ACM Trans on Embedded Comp Systems.
Vieira, M., Canesche, M., Bragança, L., Campos, J., Silva, M., Ferreira, R., and Nacif, J. A. (2021). Reshape: A run-time dataflow hardware-based mapping for cgra overlays. In IEEE International Symposium on Circuits and Systems (ISCAS), pages 1–5. IEEE.
Walker, M. and et al. (2019). Generic connectivity-based cgra mapping via integer linear programming. In Field-Programmable Custom Computing Machines (FCCM).
Yin, S. and et al. (2017). Dfgnet: Mapping dataflow graph onto cgra by a deep learning approach. In IEEE Int Symp on Circuits and Systems (ISCAS).
Yoon, J. W. and et al. (2009). A graph drawing based spatial mapping algorithm for coarse-grained reconfigurable architectures. IEEE Trans on VLSI systems, 17(11).
Publicado
31/07/2022
Como Citar
CANESCHE, Michael; FERREIRA, Ricardo.
Algoritmos de Posicionamento e Roteamento baseados em Travessia de Grafo para Arquiteturas Reconfiguráveis de Grão Grosso (CGRA). In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 35. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 150-159.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2022.223194.
