Análise da Complexidade de Algoritmo para Arquiteturas Paralelas: Estudo da Técnica da Divisão e Conquista
Resumo
Este trabalho analisa a complexidade de uma implementação do método de desenvolvimento de algoritmos Divisão e Conquista numa arquitetura paralela com estrutura de árvore, comparando-a à complexidade de uma implementação seqüencial.
Referências
AHO, A.V. HOPCROFT, J.E. & ULLMAN, J.D. The Design and Analysis of Computer Algorithms. Reading, Mass., Addison-Wesley, 1974.
BROWNING, S.A. Algorithms for Tree Machine. In: Introduction to VLSI Systems. (C. Mead & L. Conway, authors). Addison-Wesley, 1980. p.295-312.
BURTON, F.W. & HUNTBACH, M.M. Virtual Tree Machine. IEEE Transactions on Computers. Vol C-33. No.3 March 1984. p.278-80.
HOROWITZ, Z. & ZORAT, A. Divide and Conquer for Parallel Processing. IEEE Transactions on Computers. Vol C-32 No. 6, June 1983. p.582-5.
KUNG, H.T. The Structure of Parallel Algorithms. CMU-CS 79-143. Carnegie-Mellon University August, 1979.
LINT, B. & AGERWALA, T. Communication Issues in the Design and Analysis of Parallel Algorithms. IEEE Transactions on Software Engineering. Vol. SE-7 No. 2. March 1981. p-174-88.
OPATRNY, J. Parallel Programming Constructs for Divide-and-Conquer, and Branch-and-Bound Paradigms. Information Systems and Operational Research INFOR. vol. 23 No.4, November 1985. p.403-16.
PETERS, F. Tree Machines and Divide - and - Conquer Algorithms. Lecture Notes CS111, 1981. D.25-35,
PREPARATA, F. Algorithms Design and VLSI Architectures. IBM Note de Seminari e Conferenze. Elaboratori Paralleli e Calcolo Scientifico - Roma 3-5 Marzo 1982. 20p.
RIBEIRO, C.C. Parallel Computer Models and Combinatorial Algorithms. Annals of Discrete Mathematics 31. Elsevier. Science Publishers B.V. (North-Holland) 1987. p.325-64.
TERADA, R. Desenvolvimento de Algoritmos e Complexidade de Computação. Depto. de Informática. PUC/RJ, 1982.
TOSCANI, L.V. & VELOSO, P.A.S. Divisão e Conquistes: Análise da Complexidade. Anais do VI Congresso da Sociedade Brasileira de Computacao. Olinda-PE, 19-25, julho 1986. p.89-104.
TOSCANI, L.V. & RIBEIRO, C.C. Análise da Complexidade da Divisão e Conquista para Máquinas Paralelas com estrutura de árvore. A publicar.
BROWNING, S.A. Algorithms for Tree Machine. In: Introduction to VLSI Systems. (C. Mead & L. Conway, authors). Addison-Wesley, 1980. p.295-312.
BURTON, F.W. & HUNTBACH, M.M. Virtual Tree Machine. IEEE Transactions on Computers. Vol C-33. No.3 March 1984. p.278-80.
HOROWITZ, Z. & ZORAT, A. Divide and Conquer for Parallel Processing. IEEE Transactions on Computers. Vol C-32 No. 6, June 1983. p.582-5.
KUNG, H.T. The Structure of Parallel Algorithms. CMU-CS 79-143. Carnegie-Mellon University August, 1979.
LINT, B. & AGERWALA, T. Communication Issues in the Design and Analysis of Parallel Algorithms. IEEE Transactions on Software Engineering. Vol. SE-7 No. 2. March 1981. p-174-88.
OPATRNY, J. Parallel Programming Constructs for Divide-and-Conquer, and Branch-and-Bound Paradigms. Information Systems and Operational Research INFOR. vol. 23 No.4, November 1985. p.403-16.
PETERS, F. Tree Machines and Divide - and - Conquer Algorithms. Lecture Notes CS111, 1981. D.25-35,
PREPARATA, F. Algorithms Design and VLSI Architectures. IBM Note de Seminari e Conferenze. Elaboratori Paralleli e Calcolo Scientifico - Roma 3-5 Marzo 1982. 20p.
RIBEIRO, C.C. Parallel Computer Models and Combinatorial Algorithms. Annals of Discrete Mathematics 31. Elsevier. Science Publishers B.V. (North-Holland) 1987. p.325-64.
TERADA, R. Desenvolvimento de Algoritmos e Complexidade de Computação. Depto. de Informática. PUC/RJ, 1982.
TOSCANI, L.V. & VELOSO, P.A.S. Divisão e Conquistes: Análise da Complexidade. Anais do VI Congresso da Sociedade Brasileira de Computacao. Olinda-PE, 19-25, julho 1986. p.89-104.
TOSCANI, L.V. & RIBEIRO, C.C. Análise da Complexidade da Divisão e Conquista para Máquinas Paralelas com estrutura de árvore. A publicar.
Publicado
13/05/1987
Como Citar
TOSCANI, Laira Vieira; RIBEIRO, Celso Carneiro.
Análise da Complexidade de Algoritmo para Arquiteturas Paralelas: Estudo da Técnica da Divisão e Conquista. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 1. , 1987, Gramado/RS.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1987
.
p. 343-352.
DOI: https://doi.org/10.5753/sbac-pad.1987.23591.
