Estudo de Redes Multiestágios em presença de Multicast

• Caio Von Rondow Morais UFV
• Jose Nacif UFV
• Ricardo Ferreira UFV

DOI: https://doi.org/10.5753/sscad_estendido.2024.244747

Resumo

As redes multiestágio são uma alternativa econômica, com um custo de O(n log(n)) em termos de elementos de chaveamento. No entanto, encontrar um roteamento válido nessas redes é um grande desafio. Uma solução possível é utilizar redes rearranjáveis, que podem ser reconfiguradas para conectar qualquer entrada a qualquer saída, reorganizando suas conexões internas para evitar bloqueios. No entanto, em aplicações reais, as conexões geralmente seguem um padrão multicast, o que torna o roteamento mais complexo, mesmo em redes rearranjáveis. Demonstramos que, embora a rede Benes seja amplamente reconhecida na literatura como a principal referência em redes rearranjáveis, ela perde essa propriedade na presença de multicast. Para contornar esse problema, exploramos redes Omega ou shuffle-exchange com estágios extras e mostramos que elas podem ser reorganizadas de maneira a evitar bloqueios. Como o espaço de busca de soluções é exponencial, utilizamos uma implementação em GPU, o que nos permitiu derivar algumas propriedades importantes. Também avaliamos algoritmos de aprendizado de máquina utilizando os dados gerados pela GPU. Finalmente, este estudo aponta novas direções para o desenvolvimento de redes rearranjáveis na presença de multicast.

Referências

Beneš, V. E. (1965). Mathematical theory of connecting networks and telephone traffic. Academic press.

Choi, Y.-k., Chi, Y., Qiao, W., Samardzic, N., and Cong, J. (2021). Hbm connect: High-performance hls interconnect for fpga hbm. In ACM FPGA.

Dai, H. and Shen, X. (2008). Rearrangeability of 7-stage 16× 16 shuffle exchange networks. Frontiers of Electrical and Electronic Engineering in China, 3:440–458.

Ferreira, R., Canesche, M., Coelho, K., and Nacif, J. (2018). Minimum switching networks. In Brazilian Symposium on Computing Systems Engineering (SBESC).

Ferreira, R. S., Cardoso, J. M., Damiany, A., Vendramini, J., and Teixeira, T. (2011). Fast placement and routing by extending coarse-grained reconfigurable arrays with omega networks. Journal of Systems Architecture, 57(8):761–777.

Gazit, I. and Malek, M. (1989). On the number of permutations performable by extra-stage multistage interconnection networks. IEEE trans on computers, 38(2).

Jastrzkebski, A. and Kubale, M. (2010). Rearrangeability in multicast clos networks is np-complete. In International Conference on Information Technology,(ICIT). IEEE.

Lawrie, D. H. (1975). Access and alignment of data in an array processor. IEEE Transactions on computers, 100(12):1145–1155.

Morais, C. V. R., Penha, J., Nacif, J. A., and Ferreira, R. (2023). New kids on the unblocking: Strategies to overcome blocking networks. In Simpósio em Sistemas Computacionais de Alto Desempenho.

Silva, L., Ferreira, R., Canesche, M., Penha, J., , and Nacif, J. (2019). Ready: A fine-grained multithreading overlay framework for modern cpu-fpga dataflow applications. ACM Transactions on Embedded Computing Systems (TECS), 18.

Vendramini, J. C. G. and Ferreira, R. (2010). Parallel routing algorithm for extra level omega networks on reconfigurable systems. In Symposium on Computing Systems.

Waksman, A. (1968). A permutation network. Journal of the ACM (JACM), 15(1).

Wu, C.-L. and Feng, T.-Y. (1980). On a class of multistage interconnection networks. IEEE trans. on Computers, 100(8).

Zhao, L., Li, Z., and Ma, T. (2024). Making path selection bright: A routing algorithm for on-chip benes networks. Electronics, 13(5):981.