Experimentos com um Algoritmo Distribuído para Troca Ordenada de Mensagens em Tarefas que Migram

  • N. C. Couri UFF
  • S. C. S. Porto UFF
  • V. C. Barbosa UFRJ

Resumo


Para muitos algoritmos que utilizam trocas de mensagens, é fundamental que o sistema de computação garanta a entrega ordenada de mensagens entre processadores. No entanto, mesmo quando esta garantia é oferecida, a migração de tarefas entre processadores pode fazer com que a ordenação seja perdida. Neste trabalho, consideramos o PSP (Pipe Shortening Protocol), um algoritmo distribuído assíncrono que garante a entrega ordenada de mensagens entre tarefas que migram. Um ambiente de teste, composto por uma aplicação sintética e diferentes políticas de migração, foi construído para experimentação do algoritmo numa máquina paralela real. Para diferentes aplicações paralelas sintéticas foram considerados dois casos distintos: com e sem o uso do algoritmo PSP. Foram gerados resultados numéricos comparativos do tempo de resposta a fim de delimitar as configurações dos parâmetros sob as quais o algoritmo PSP alcança melhor desempenho.

Referências

V.C. BARBOSA e S.C.S. PORTO, "An algorithm for FIFO delivery among migrating tasks", Information Processing Letters 53 (1995), 261-267.

K.M. CHANDY e L. LAMPORT, "Distributed snapshots: determining global states of distributed systems", ACM Trans. on Computer Systems 3 (1985), 63-75.

E.W. DIJKSTRA e C.S. SCHOLTEN, "Termination detection for diffusion computations", Information Processing Letters 11 (1980), 1-4.

M.R. ESKICIOGLU e L.-F. CABRERA, "Process migration: an annotated bibliography", Technical Report RJ 7935 (72918), IBM Research Division, San Jose, CA, 1991.

M. GERLA e L. KLEINROCK, "Flow control protocols", in P. E. Green, Jr. (Ed.), Computer Network Architectures and Protocols, Plenum Press, New York, NY, 1982, 361-412.

Intel Supercomputer Systems Division, comunicação interna sobre iPSC/860 and Paragon systems.

D.R. JEFFERSON, "Virtual time", ACM Trans. on Programming Languages and Systems 7 (1985), 404-425.

L. LAMPORT e N.A. LYNCH, "Distributed computing: models and methods", in J. van Leeuwen (Ed.), Handbook of Theoretical Computer Science, Vol. B, The MIT Press, Cambridge, MA, 1990, 1156-1199.

L.M. NI e P.K. McKINLEY, "A survey of wormhole routing techniques in direct networks", IEEE Computer Jan. (1993), 62-76.

J.K. OUSTERHOUT, A.R. CHERENSON, F. DOUGLIS, M.N. NELSON, e B.B. WELCH, "The Sprite network operating system", IEEE Computer (1988), 23-36.

T.M. RAVI e D. JEFFERSON, "A basic protocol for routing messages to migrating processes", Proc. Int. Conf. on Parallel Processing, Saint Charles, IL, 1988, 188-196.

T.T.Y. SUEN e J.S.K.WONG, "Efficient Task Migration Algorithm for Distributed Systems", IEEE Transactions on Parallel and Distributed 3 July (1992), 488-499.

M. THEIMER, K. LANTZ e D. CHERITON, "Preemptable remote execution facilities for the V-System", Proc. 10th Symp. on Operating System Principies, 1985, 2-12.
Publicado
07/10/1997
COURI, N. C.; PORTO, S. C. S.; BARBOSA, V. C.. Experimentos com um Algoritmo Distribuído para Troca Ordenada de Mensagens em Tarefas que Migram. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 9. , 1997, Campos do Jordão/SP. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1997 . p. 185-200. DOI: https://doi.org/10.5753/sbac-pad.1997.22624.