Influência da Política de Seleção de Sáida no Desempenho de um Algoritmo de Roteamento Adaptativo
Abstract
The focus of this paper is to show that the channel output selection policy influences closely the communication latency mean of the interconection network. Some simulations results are presented for a tridimensional mesh and wormhole routing system with variation in the virtual channel number using a adaptive routing algorithm with variation in the output selection policy. That results are compared with the well known dimension ordered static algorithm.
References
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.
Published
1995-07-29
How to Cite
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.
