Algoritmos para Descobrir o Máximo em um Multicomputador Baseado em Barramentos Hierárquicos
Resumo
Este artigo apresenta algoritmos para determinação do valor máximo dentre n valores distintos, em um multicomputador baseado em barramentos hierárquicos. É analisada a influência, no projeto e desempenho desses algoritmos, de características da arquitetura, como: número total de EPs (elementos de processamento), razão entre número de "clusters" e número de EPs por "cluster", e relacionamento entre tempo para transmissão de mensagens em um barramento e tempo para processamento em um EP.
Referências
DANDAMUDI,S.P. & EAGER,D.L. Hierarchical interconnection networks for multicomputer systems. IEEE Trans. Comp., v. 39, n. 6, p. 786-797, Jun. 1990.
DECHTER,R. & KLEINROCK,L. Broadcast communications and distributed algorithms. IEEE ans. Comp., v. C-35, n. 3, p. 210-219, Mar. 1986.
KIRNER,C. Design of a recursively structured parallel computer. In: PROCEEDINGS OF THE ACM-COMPUTER SCIENCE CONFERENCE - CSC, Louisville, Kentucky, USA, Feb. 1989.
KIRNER,C. Arquitetura de Sistemas Avançados de Computação. In: XI CONGRESSO NACIONAL DA SBC - X JORNADA DE ATUALIZAÇÃO EM INFORMÁTICA. Santos - SP, ago. 1991.
LEVITAN,S.P. & FOSTER,C.C. Finding an extremum in a network. In: PROC. 9TH ANN. SYMP. COMP. ARCHITECT., Austin, Texas, USA, 1982. p. 321-325.
YANG,C.-B; LEE,R.C.T.; CHEN,W.-T. Finding minimum spanning trees based upon single-channel broadcast communications. In: PROC. INT'L COMPUTER SYMPOSIUM, Taipei, Taiwan, 1988, p. 1451-1456.
YANG,C-B; LEE,R.C.T.; CHEN,W-T. Parallel graph algorithms based upon broadcast communications. IEEE Trans. Comp., v. 39, n. 12, p. 1468-1472, Dec. 1990.
YANG,C.-B. Reducing conflict resolution time for solving graph problems in broadcast communications. In: PROC. IASTED 9TH INT'L SYMP. APPLIED INFORMATICS, Innsbruck, Austria, Feb. 1991. p. 445-448.
YANG,C-B; LEE,R.C.T.; CHEN, W-T. Conflict-free sorting algorithms under single-channel and multi-channel broadcast communication models. In: PROC. INT'L CONF. COMPUTING AND INFORMATION, Ottawa, Canada, May 1991. p. 350-359.
DECHTER,R. & KLEINROCK,L. Broadcast communications and distributed algorithms. IEEE ans. Comp., v. C-35, n. 3, p. 210-219, Mar. 1986.
KIRNER,C. Design of a recursively structured parallel computer. In: PROCEEDINGS OF THE ACM-COMPUTER SCIENCE CONFERENCE - CSC, Louisville, Kentucky, USA, Feb. 1989.
KIRNER,C. Arquitetura de Sistemas Avançados de Computação. In: XI CONGRESSO NACIONAL DA SBC - X JORNADA DE ATUALIZAÇÃO EM INFORMÁTICA. Santos - SP, ago. 1991.
LEVITAN,S.P. & FOSTER,C.C. Finding an extremum in a network. In: PROC. 9TH ANN. SYMP. COMP. ARCHITECT., Austin, Texas, USA, 1982. p. 321-325.
YANG,C.-B; LEE,R.C.T.; CHEN,W.-T. Finding minimum spanning trees based upon single-channel broadcast communications. In: PROC. INT'L COMPUTER SYMPOSIUM, Taipei, Taiwan, 1988, p. 1451-1456.
YANG,C-B; LEE,R.C.T.; CHEN,W-T. Parallel graph algorithms based upon broadcast communications. IEEE Trans. Comp., v. 39, n. 12, p. 1468-1472, Dec. 1990.
YANG,C.-B. Reducing conflict resolution time for solving graph problems in broadcast communications. In: PROC. IASTED 9TH INT'L SYMP. APPLIED INFORMATICS, Innsbruck, Austria, Feb. 1991. p. 445-448.
YANG,C-B; LEE,R.C.T.; CHEN, W-T. Conflict-free sorting algorithms under single-channel and multi-channel broadcast communication models. In: PROC. INT'L CONF. COMPUTING AND INFORMATION, Ottawa, Canada, May 1991. p. 350-359.
Publicado
26/10/1992
Como Citar
FREITAS, Alex Alves; KIRNER, Claudio.
Algoritmos para Descobrir o Máximo em um Multicomputador Baseado em Barramentos Hierárquicos. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 4. , 1992, São Paulo/SP.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
1992
.
p. 289-303.
DOI: https://doi.org/10.5753/sbac-pad.1992.22717.
