Experimentos com um Algoritmo Distribuído para Troca Ordenada de Mensagens em Tarefas que Migram
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
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.
