Um Algoritmo de Roteamento Adaptativo em Estruturas Mesh N-Dimensionais
Resumo
Este artigo apresenta um algoritmo de roteamento livre de travamento (deadlock-free), livre de ciclos vivos (livelock-free), tolerante a falhas, adaptativo e minimal, sempre que possível. As características básicas deste modelo são a quebra de ciclos de espera de recursos, potencialmente causadores de deadlock, e a utilização de canais virtuais na solução de conflitos entre mensagens. Simulações em estruturas mesh tridimensionais serão apresentadas e seus resultados comparados com outros algoritmos tradicionais de roteamento.Referências
D. Lenoski, J. Laudon, K. Gharachorloo, A. Gupta, and J. Hennessy, "The directory-based cache coherence protocol for the DASH multiprocessor", Proc. of the 17th International Symposium on Computer Architecture, pp. 148-159, Mai 1990.
Seitz, C. L., "The cosmic cube", Communications of the ACM 28, 1, pp 22-23, Jan 1985.
Sullivan, H. e Brashkow, T. R., "A large scale homogeneous machine", Proc. of the 4th Annual Symposium on Computer Architecture, pp. 105-124, 1977.
Dally, W. J., "Desempenho analysis of k-ary n-cube interconection networks", IEEE Transactions on Computers, vol. C-39, pp. 775-785, Jun 1990.
Dally, W. J. e Seitz, C. L., "The torus routing chip", Journal of Distributed Computing, vol. 1, no. 3, pp 187-196, 1986.
Kermani, P. e Kleinrock, L., "Virtual cut through: A new computer communication switching technique", Computer Networks, vol. 3, pp. 267-286, 1979.
Dally, W. J., "A VLSI Architecture for concurrent data structures", Ph.D. thesis, California Institute of Technology, 1986.
Dally, W. J. e Seitz, C. L., "Deadlock-free message routing in multiprocessor interconection networks", IEEE Trans. on Computers, vol C-36, pp 547-553, Mai 1987.
Gelernter, D., "A DAG-based algorithm for prevention of store-and-foward deadlock in packet networks", IEEE Trans. on Communication, vol. COM-29, pp 512-524, Abr 1981.
Li, Q., "Minimum Deadlock-free Message Routing Restrictions in Binary Hypercubes", Journal of Parallel and Distributed Computing 15, pp 153-159, 1992.
Glass, C. J. e Ni, L. M., "The Turn Model for Adaptative Routing", Proc. of the 19th Annual Symposium on Computer Architecture, pp 278-287, Mai 1992,
Reed, D. A. e Fujimoto, R. M., "Multicomputer Networks : Message-Based Parallel Processing", MIT Press, 1987.
Vários, "VLSI and Parallel Computation", Editado por Robert Suay e Grahan, Morgan Kaufmann Publishers, INC 1990.
Ni, L. e McKinley, P. K.,"A Survey of Wormhole Routing Techniques in Direct Networks", Computer, vol 26, no. 2, pp 62-76, Fev 1993,
Grunwald, D. C., "Circuit Switched Multicomputers and Heuristic Load Placement", PhD Thesis, Universidade de Illinois - Urbana, Set. 1989.
Seitz, C. L., "The cosmic cube", Communications of the ACM 28, 1, pp 22-23, Jan 1985.
Sullivan, H. e Brashkow, T. R., "A large scale homogeneous machine", Proc. of the 4th Annual Symposium on Computer Architecture, pp. 105-124, 1977.
Dally, W. J., "Desempenho analysis of k-ary n-cube interconection networks", IEEE Transactions on Computers, vol. C-39, pp. 775-785, Jun 1990.
Dally, W. J. e Seitz, C. L., "The torus routing chip", Journal of Distributed Computing, vol. 1, no. 3, pp 187-196, 1986.
Kermani, P. e Kleinrock, L., "Virtual cut through: A new computer communication switching technique", Computer Networks, vol. 3, pp. 267-286, 1979.
Dally, W. J., "A VLSI Architecture for concurrent data structures", Ph.D. thesis, California Institute of Technology, 1986.
Dally, W. J. e Seitz, C. L., "Deadlock-free message routing in multiprocessor interconection networks", IEEE Trans. on Computers, vol C-36, pp 547-553, Mai 1987.
Gelernter, D., "A DAG-based algorithm for prevention of store-and-foward deadlock in packet networks", IEEE Trans. on Communication, vol. COM-29, pp 512-524, Abr 1981.
Li, Q., "Minimum Deadlock-free Message Routing Restrictions in Binary Hypercubes", Journal of Parallel and Distributed Computing 15, pp 153-159, 1992.
Glass, C. J. e Ni, L. M., "The Turn Model for Adaptative Routing", Proc. of the 19th Annual Symposium on Computer Architecture, pp 278-287, Mai 1992,
Reed, D. A. e Fujimoto, R. M., "Multicomputer Networks : Message-Based Parallel Processing", MIT Press, 1987.
Vários, "VLSI and Parallel Computation", Editado por Robert Suay e Grahan, Morgan Kaufmann Publishers, INC 1990.
Ni, L. e McKinley, P. K.,"A Survey of Wormhole Routing Techniques in Direct Networks", Computer, vol 26, no. 2, pp 62-76, Fev 1993,
Grunwald, D. C., "Circuit Switched Multicomputers and Heuristic Load Placement", PhD Thesis, Universidade de Illinois - Urbana, Set. 1989.
Publicado
07/09/1993
Como Citar
SANTOS, Celso A. S.; O., Edward D. Moreno; D., Martin X. Torres; KOFUJI, Sérgio T..
Um Algoritmo de Roteamento Adaptativo em Estruturas Mesh N-Dimensionais. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 5. , 1993, Florianópolis/SC.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1993
.
p. 49-58.
DOI: https://doi.org/10.5753/sbac-pad.1993.23022.
