Análise da Complexidade de Algoritmo para Arquiteturas Paralelas: Estudo da Técnica da Divisão e Conquista

  • Laira Vieira Toscani PUC Rio / UFRGS
  • Celso Carneiro Ribeiro ENST / PUC Rio

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.
Publicado
13/05/1987
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.