Influência da Política de Seleção de Sáida no Desempenho de um Algoritmo de Roteamento Adaptativo
Resumo
A idéia central deste trabalho é demonstrar que a política de seleção de saída dos canais tem influência direta na latência média de comunicação da rede de interconexão. São apresentados alguns resultados de simulações para um sistema em malha tridimensional com controle de fluxo tipo wormhole e variação no número de canais virtuais, utilizando um algoritmo de roteamento adaptativo com variação na política de seleção de saída. Estes resultados são comparados aos obtidos utilizando conhecido algoritmo estático ordenado por dimensões.
Referências
Bennan, P. et al. Adaptive deadlock- and livelock-free routing with all minimal paths in torus networks. In: Symposium on Parallel Algorithms and Architectures, 4., Madison, 1992. Proceedings. New York, ACM, 1992, p.3-12.
Boppana, R. V.; Chalasani, S. A comparison of wormhole routing algorithms based on adaptivity. Computer Architecture News, v.21, n.2, p.351-60, May 1993.Dally,
Glass, C.J.; Ni, L.M. The turn model for adaptative routing. Computer Architecture News, v.20, n.2, p.278-87, May 1992.
Ngai, J. A framework for adaptive routing in multicomputers networks. Pasadena, 1989. 169p. (Phd)Thesis - Computer Science Department, California Institute of Technology. (Caltech-CS-TR-89-09).
Linder, D.H.; Harden, J.C. An adaptive and fault-tolerant wormhole routing strategy for k-ary n-cubes. IEEE Transactions on Computers, v.40, n.1, p.2-12, Jan. 1991.
Dally, W.J. Virtual-channel flow control. IEEE Transactions on Parallel and Distributed Systems, v.3, n.2, p.194-205, Mar. 1992.
Gaughan, P.T.; Yalamanchili; S. Adaptive routing protocols for hypercube interconnection networks. IEEE Computer, v.26, n.S, p. l2-23, May 1993.
Santos, C.A.S. et al. Um algoritmo de roteamento adaptativo em estruturas mesh n-dimensionais. In: Simpósio Brasileiro de Arquiteturas de Computadores / Processamento de Alto Desempenho, 5., Florianópolis, 1993. Anais. Florianópolis, UFSC, 1993. v.1, p.49-58.
Li, Q. Minimum deadlock-free message routing restrictions in binary hypercubes. Journal of Parallel and Distributed Computing, n.1 5, p.1 53-9, 1992.
Dally, W.J. Deadlock-free message routing in multiprocessor interconnetion networks. IEEE Transactions on Computers, v.36, n.5, p.547-53, May 1987.
Santos, C. A. S. et al. Análise de desempenho de um algoritmo de roteamento adaptativo em malhas 3d sob diversos padrões de tráfego. In: Simpósio Brasileiro de Arquiteturas de Computadores / Processamento de Alto Desempenho, 6., Caxambu, 1994. Anais. Belo Horizonte, UFMG, 1994. p.273-86.
Reed, D.A.; Fujimoto, R.M. Multicomputer networks: message-based parallel processing. Cambridge, The MIT Press, 1987. (Scientific Computation Series).
Santos, C. A. S. Um algoritmo de roteamento adaptativo em malhas tridimensionais. São Paulo, 1994. 101p. Dissertação (Mestrado) - Escola Politécnica, Universidade de São Paulo.
Boppana, R. V.; Chalasani, S. A comparison of wormhole routing algorithms based on adaptivity. Computer Architecture News, v.21, n.2, p.351-60, May 1993.Dally,
Glass, C.J.; Ni, L.M. The turn model for adaptative routing. Computer Architecture News, v.20, n.2, p.278-87, May 1992.
Ngai, J. A framework for adaptive routing in multicomputers networks. Pasadena, 1989. 169p. (Phd)Thesis - Computer Science Department, California Institute of Technology. (Caltech-CS-TR-89-09).
Linder, D.H.; Harden, J.C. An adaptive and fault-tolerant wormhole routing strategy for k-ary n-cubes. IEEE Transactions on Computers, v.40, n.1, p.2-12, Jan. 1991.
Dally, W.J. Virtual-channel flow control. IEEE Transactions on Parallel and Distributed Systems, v.3, n.2, p.194-205, Mar. 1992.
Gaughan, P.T.; Yalamanchili; S. Adaptive routing protocols for hypercube interconnection networks. IEEE Computer, v.26, n.S, p. l2-23, May 1993.
Santos, C.A.S. et al. Um algoritmo de roteamento adaptativo em estruturas mesh n-dimensionais. In: Simpósio Brasileiro de Arquiteturas de Computadores / Processamento de Alto Desempenho, 5., Florianópolis, 1993. Anais. Florianópolis, UFSC, 1993. v.1, p.49-58.
Li, Q. Minimum deadlock-free message routing restrictions in binary hypercubes. Journal of Parallel and Distributed Computing, n.1 5, p.1 53-9, 1992.
Dally, W.J. Deadlock-free message routing in multiprocessor interconnetion networks. IEEE Transactions on Computers, v.36, n.5, p.547-53, May 1987.
Santos, C. A. S. et al. Análise de desempenho de um algoritmo de roteamento adaptativo em malhas 3d sob diversos padrões de tráfego. In: Simpósio Brasileiro de Arquiteturas de Computadores / Processamento de Alto Desempenho, 6., Caxambu, 1994. Anais. Belo Horizonte, UFMG, 1994. p.273-86.
Reed, D.A.; Fujimoto, R.M. Multicomputer networks: message-based parallel processing. Cambridge, The MIT Press, 1987. (Scientific Computation Series).
Santos, C. A. S. Um algoritmo de roteamento adaptativo em malhas tridimensionais. São Paulo, 1994. 101p. Dissertação (Mestrado) - Escola Politécnica, Universidade de São Paulo.
Publicado
29/07/1995
Como Citar
SANTOS, Celso Alberto Saibel; KOFUJI, Sérgio Takeo; MARTINS, Carlos A. P. S..
Influência da Política de Seleção de Sáida no Desempenho de um Algoritmo de Roteamento Adaptativo. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 7. , 1995, Canela.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1995
.
p. 425-437.
DOI: https://doi.org/10.5753/sbac-pad.1995.19878.
