Physical Oscillator Model for Parallel Distributed Computing
Information
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.
- Georg Hager (Friedrich-Alexander-University Erlangen-Nuremberg (FAU))
- Gerhard Wellein (Friedrich-Alexander-University Erlangen-Nuremberg (FAU))
- Ayesha Afzal (Friedrich-Alexander-University Erlangen-Nuremberg (FAU))
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.
