Análise de Desempenho de um Algoritmo de Roteamento Adaptativo em Malhas 3D Sob Diversos Padrões de Tráfego
Resumo
Este artigo análisa o desempenho dos algoritmos de roteamento determinístico e adaptativo em sistemas multicomputadores baseados em malhas tridimensionais, sob vários padrões de tráfego. Para realizar este estudo foi desenvolvido um simulador denominado SIM3D. Os resultados obtidos nas simulações são comparados considerando-se a latência e o throughput. Entre os fatores utilizados na avaliação do desempenho temos: o tipo de algoritmo de roteamento, o padrão de tráfego e o tamanho das mensagens.
Referências
ATHAS, W.C.; SEITZ, C.L. Muticomputers: Message-Passing Concurrent Computers. IEEE Computer. v.21, n.8, p.9-24, Aug. 1988.
BERMAN, P.; et al. Adaptive deadlock- and livelock-free routing with all minimal paths in torus networks. SYMPOSIUM ON PARALLEL ALGORITHMS AND ARCHITECTURES, 4., 1992. Proceedings. ACM, p.3-12, 1992.
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.
CHIEN, K.; KIM, J.H. Planar-adaptive routing: Low-cost adaptive networks for multiprocessors. Computer Architecture News. v.20, n.2, p.268-77, May 1992.
DALLY, W.J.; SEITZ, C.L. Deadlock-free message routing in multiprocessor interconection networks. IEEE Transactions on Computers. v.36, n.S, p.547-53, May 1987.
DALL Y, W.J. A VLSI architecture for concurrent data structures. Norwell, Kluwer Academic Publishers, 1987.
DALL Y, W.J. Performance Analysis of k-ary n-cube interconnection networks. IEEE Transactions on Computers v.39, n.6, p.775-85, June 1990.
DALL Y, W.J. Virtual-channel flow control. IEEE Transactions on Parallel and Distributed Systems. v.3, n.2, p.194-205, Mar. 1992.
DALL Y, W.J.; AOK.I, H. Deadlock-free adaptive routing in multicomputer networks using virtual channels. IEEE Transactions on Parallel and Distributed Systems. v.4, n.4, p.466- 75 Apr. 1993.
FELPERIN, S.A.; et al. Routing techniques for massively parallel communication. Proceedings of the IEEE. v.79, n.4, p.488-503, Apr. 1991.
GAUGHAN, P. T.; Y ALAMANCHILI; S. Adaptive routing protocols for hypercube interconnection networks. IEEE Computer. v.26, n.S, p.12-23, May 1993.
GLASS, C.J.; NI, L.M. The turn model for adaptative routing. Computer Architecture News. v.20, n.2, p.278-87, May 1992.
GRUNWALD, D.C. Circuit switched multicomputers and heuristic load placement. Urbana, 1990. 216p. (PhD)Thesis - Department of Computer Science, University of Illinois at Urbana-Champaign. /June 1990, revised/
KERMANI, P.; KLEINROCK, L. Virtual cut through: A new computer communication switching technique. Computer Networks. v3, p.267-86, 1979.
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.
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).
NI, L.M.; MCKINLEY, P.K. A survey of wormhole routing techniques in direct networks. IEEE Computer. v.26, n.2, p.62-76, Feb. 1993.
PRITSKER, AAB. lntroduction to simulation and SLAM ll. 3.ed., Systems Publishing, 1986.
REED, D.A.; FUJIMOTO, R.M. Multicomputer networks: message-based parallel processing. Cambridge, The MIT Press, 1987. (Scientific Computation Series).
SANTOS, C.AS. et ai. Um algoritmo de roteamento adaptativo em estruturas mesh odimensionais. In: SIMPÓSIO BRASILEIRO DE ARQUITETURAS DE COMPUTADORES I PROCESSAMENTO DE ALTO DESEMPENHO, 5., Florianópolis, 1993. Anais. Florianópolis, UFSC, 1993. v.1, p.49-58.
TALIA, D. Message-routing systems for transputer-based multicomputers. IEEE Micro, p.62-72, June 1993.
BERMAN, P.; et al. Adaptive deadlock- and livelock-free routing with all minimal paths in torus networks. SYMPOSIUM ON PARALLEL ALGORITHMS AND ARCHITECTURES, 4., 1992. Proceedings. ACM, p.3-12, 1992.
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.
CHIEN, K.; KIM, J.H. Planar-adaptive routing: Low-cost adaptive networks for multiprocessors. Computer Architecture News. v.20, n.2, p.268-77, May 1992.
DALLY, W.J.; SEITZ, C.L. Deadlock-free message routing in multiprocessor interconection networks. IEEE Transactions on Computers. v.36, n.S, p.547-53, May 1987.
DALL Y, W.J. A VLSI architecture for concurrent data structures. Norwell, Kluwer Academic Publishers, 1987.
DALL Y, W.J. Performance Analysis of k-ary n-cube interconnection networks. IEEE Transactions on Computers v.39, n.6, p.775-85, June 1990.
DALL Y, W.J. Virtual-channel flow control. IEEE Transactions on Parallel and Distributed Systems. v.3, n.2, p.194-205, Mar. 1992.
DALL Y, W.J.; AOK.I, H. Deadlock-free adaptive routing in multicomputer networks using virtual channels. IEEE Transactions on Parallel and Distributed Systems. v.4, n.4, p.466- 75 Apr. 1993.
FELPERIN, S.A.; et al. Routing techniques for massively parallel communication. Proceedings of the IEEE. v.79, n.4, p.488-503, Apr. 1991.
GAUGHAN, P. T.; Y ALAMANCHILI; S. Adaptive routing protocols for hypercube interconnection networks. IEEE Computer. v.26, n.S, p.12-23, May 1993.
GLASS, C.J.; NI, L.M. The turn model for adaptative routing. Computer Architecture News. v.20, n.2, p.278-87, May 1992.
GRUNWALD, D.C. Circuit switched multicomputers and heuristic load placement. Urbana, 1990. 216p. (PhD)Thesis - Department of Computer Science, University of Illinois at Urbana-Champaign. /June 1990, revised/
KERMANI, P.; KLEINROCK, L. Virtual cut through: A new computer communication switching technique. Computer Networks. v3, p.267-86, 1979.
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.
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).
NI, L.M.; MCKINLEY, P.K. A survey of wormhole routing techniques in direct networks. IEEE Computer. v.26, n.2, p.62-76, Feb. 1993.
PRITSKER, AAB. lntroduction to simulation and SLAM ll. 3.ed., Systems Publishing, 1986.
REED, D.A.; FUJIMOTO, R.M. Multicomputer networks: message-based parallel processing. Cambridge, The MIT Press, 1987. (Scientific Computation Series).
SANTOS, C.AS. et ai. Um algoritmo de roteamento adaptativo em estruturas mesh odimensionais. In: SIMPÓSIO BRASILEIRO DE ARQUITETURAS DE COMPUTADORES I PROCESSAMENTO DE ALTO DESEMPENHO, 5., Florianópolis, 1993. Anais. Florianópolis, UFSC, 1993. v.1, p.49-58.
TALIA, D. Message-routing systems for transputer-based multicomputers. IEEE Micro, p.62-72, June 1993.
Publicado
01/08/1994
Como Citar
SANTOS, Celso A. Saibel; MARTINS, Carlos Augusto P. S.; ORDOÑEZ, Edward D. M.; DELGADO, Martha X. T.; KOFUJI, Sergio T..
Análise de Desempenho de um Algoritmo de Roteamento Adaptativo em Malhas 3D Sob Diversos Padrões de Tráfego. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 6. , 1994, Caxambu.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1994
.
p. 273-286.
DOI: https://doi.org/10.5753/sbac-pad.1994.21891.
