Synchronization mechanisms for distributed event-driven computation

Abstract

We analyze distributed event-driven computation on message-passing parallel computing systems. Synchronization is the mechanism that ensures that causality in the ordering of stochastically generated events for execution during the computation is maintained. We characterize distributed event-driven computation into weakly coupled (weak interactions) and strongly coupled (strong interactions) distributed systems and propose and analyze a number of new algorithms for efficient synchronization. The analytical results for steady state performance are complemented with detailed simulations of the transient performance. We show that synchronization enforced separately from computation results in an efficient implementation. Effects of the memory hierarchy and communication delays are also incorporated.

Keywords

This publication has 16 references indexed in Scilit:

Seismic migration algorithms on parallel computers
IEEE Transactions on Signal Processing, 1991
Asynchronous algorithms for the parallel simulation of event-driven dynamical systems
ACM Transactions on Modeling and Computer Simulation, 1991
Parallel discrete event simulation
Communications of the ACM, 1990
Efficient distributed event-driven simulations of multiple-loop networks
Communications of the ACM, 1989
Multicomputers: message-passing concurrent computers
Computer, 1988
Virtual time
ACM Transactions on Programming Languages and Systems, 1985
Response change in linearized circuits and systems: Computational algorithms and applications
Proceedings of the IEEE, 1985
Wavefront Array Processor: Language, Architecture, and Applications
IEEE Transactions on Computers, 1982
Asynchronous distributed simulation via a sequence of parallel computations
Communications of the ACM, 1981
Data Flow Supercomputers
Computer, 1980