Contributors:
Abstract: We propose a nonlinear physical model for describing the dynamics of processes in
message-passing parallel programs. The starting point is the Kuramoto model, which exhibits
self-synchronization across oscillators mediated by a long-range sinusoidal interaction potential.
The phenomenology of distributed applications with regular compute-communicate cycles
suggests a physical interpretation of processes as coupled oscillators. The bottleneck structure
in terms of memory bandwidth, network injection bandwidth, and full-system bisection
bandwidth is reflected in the interaction potential. A bottleneck-free program is best described
by a Kuramoto-like potential, since the dynamics of the parallel code exhibits
auto-synchronization. In presence of bottlenecks, a short-range repulsive interaction must be
superposed, yielding stability points away from the translationally symmetric, unstable
bulk-synchronous mode.
The modified Kuramoto model can characterize the dynamics of massively parallel code via a
system of coupled ODEs. Although the optimal interaction potentials are still unknown, the
model qualitatively describes a surprising number of effects such as resynchronization and
desynchronization, propagation and decay of idle waves, bottleneck evasion via computational
wavefronts, and the impact of fine-grained noise on program performance. As a major feature, it
mimics the symmetry-breaking behavior of bottlenecked programs.
Although large- and medium-scale phenomena are well described at least qualitatively, the
microscopic behavior is certainly problematic. Current research includes the search for
interaction potentials that provide a more quantitative characterization on the higher levels, the
incorporation of fine-grained noise in the model, and the investigation of potential Goldstone
modes emerging from the breaking of a global symmetry.
