Desynchronization and Speedup in an Asynchronous Conservative Parallel Update Protocol

Résumé : In a state-update protocol for a system of $L$ asynchronous parallel processes that communicate only with nearest neighbors, global desynchronization in operation times can be deduced from kinetic roughening of the corresponding virtual-time horizon (VTH). The utilization of the parallel processing environment can be deduced by analyzing the microscopic structure of the VTH. We give an overview of how the methods of non-equilibrium surface growth (physics of complex systems) can be applied to uncover some properties of state update algorithms used in distributed parallel discrete-event simulations (PDES). In particular, we focus on the asynchronous conservative PDES algorithm in a ring communication topology. The time evolution of its VTH is simulated numerically as asynchronous cellular automaton whose update rule corresponds to the update rule followed by this algorithm. We give theoretical estimates of the performance as a function of $L$ and the load per processor, i.e., approximate formulas for the mean speedup and for the desynchronization. It is established that, for a given simulation size, there is a theoretical upper bound for the desynchronization and a theoretical non-zero lower bound for the utilization. The new approach to performance studies, outlined in this chapter, is particularly useful in the search for the design of a new-generation of algorithms that would efficiently carry out an autonomous or tunable synchronization.