Comunicação em hipergrades e hipertoros usando barramentos
Resumo
Em sistemas multiprocessadores MIMD de memória distribuída, processadores são ligados por uma rede de interconexão ponto-a-ponto, usualmente modelada por um grafo onde processadores são vértices do grafo e canais de comunicação são as arestas. Como comunicação inter-processador constitui-se frequentemente em sérios gargalos, diversas arquiteturas foram propostas que adicionam à topologia ponto-a-ponto um sistema de barramentos múltiplos. Neste artigo mostramos o interesse de arquiteturas paralelas onde comunicações se realizam somente por barramentos. Vamos introduzir o hiperanel e hipertoro, que são as versões baseadas em barramentos das correspondentes redes ponto-a-ponto. Mostramos como usar conceitos de hipergrafos para modelar a comunicação entre processadores em tais redes de interconexão e damos algoritmos eficientes para as operações de difusão (broadcast) e troca completa (gossiping). Desenvolvemos uma nova ferramenta chamada simplificação. A idéia é construir um grafo, chamada grafo simplificado, da topologia original de hipergrafo, de tal modo que ficará fácil descrever e realizar esquemas de comunicação, uma vez que o conceito de simplificação nos permitirá utilizar algoritmos conhecidos para redes usuais, sem barramentos.
Referências
A. Bar-Noy and D. Peleg, Square meshes are not always optimal, ACM Symposium on Parallel Algorithms and Architectures, (ACM, 1989) 138-147.
C. Berge, Hypergraphs, (North Holland, 1989).
J-C. Bermond, J. Bond and C. Peyrat, Interconnection networks with each node on two buses, in Parallel Algorithms and Architectures, eds. M. Cosnard, Y. Robert, P. Quinton and M. Tchunte, (North Holland, 1984) 155-167.
J-C. Bermond, J. Bond, M. Paoli and C. Peyrat, Graphs and interconnection networks: diameter and vulnerability, in Surveys in Combinatorics, ed, E.K. LLoyd, (Cambridge University Press, 1983) 1-29.
J-C. Bermond, Le problème des "ouvroirs" (Hypergraph gossip problem), in Colloques Internacionaux du Centre National de la Recherche Scientifique, No. 260, Orsay, 1976, 31-34.
L.N. Bhuy: network, and D.P. Agrawal, Generalized hypercube and hyperbus structures for a computer E: Transactions on Computers 33 (1984) 323-333.
S.-H. Bokhari, Finding maximum on an array processor with a global bus, IEEE Transactions on Computers 33 (1984) 133-139.
G. Cybenko, D.W, Krumme, and K.N. Venkataraman, Gossiping in minimum time, SIAM Journal on Computing, Vol.21, no.1, pp. 111-139, Feb 1992.
A.M. Farley and S. T. Hedetniemi, Broadcasting in grid graphs, In Congressus Numerantium XXI, editor, Proc 9th S-E conf. combinatorics, graph theory, and computing, pages 275-288,
P. Fraigniaud and E. Lazard, Methods and problems of communication in usual networks, Repport de Recherche LIP 9, Laboratoire de l'Informatique du Parallélisme, Ecole Normale Supérieure de Lyon. October, 1991.
H. Jiang and K Smith. PPMB: a partial-multiple-bus multiprocessor architecture with improved gost-effectiveness. IEEE Transactions on Computers 41 (1992) 361-366.
D.W. Kramime. G. Cybenko and K.N, Venkataraman, Gossiping in minimal time, SIAM J. Computing 21 (1992) 111-139.
F. Meyer auf der Heide and H.T, Pham, On the performance of networks with multiple buses in STACS'92 9th Annual Symposium on Theoretical Aspects of Computer Science, eds. A. Finkel and M. Jantzen. In Lecture Notes in Computer Science, (Springer-Verlay, 1992) 97-108.
S. Olariu, J.L. Schwing and J.Y. Zhang, On the power of two-dimensional processor arrays with reconfigurable bus systems. Parallel Processing Letters 1 (1991) 29-34.
Q.F. Stout, Meshes with multiple buses, Proc, 27th IEEE Symposium on the Foundations of Computer Science (1986) 264-273.
B. Wilkinson. On crossbar switch and multiple bus interconnection networks with overlapping connectivity, IEEE Transactions on Computers 41 (1992) 738-746.
