Idle waves in high-performance computing

The vast majority of parallel scientific applications distributes computation among processes that are in a busy state when computing and in an idle state when waiting for information from other processes. We identify the propagation of idle waves through processes in scientific applications with a local information exchange between the two processes. Idle waves are nondispersive and have a phase velocity inversely proportional to the average busy time. The physical mechanism enabling the propagation of idle waves is the local synchronization between two processes due to remote data dependency. This study provides a description of the large number of processes in parallel scientific applications as a continuous medium. This work also is a step towards an understanding of how localized idle periods can affect remote processes, leading to the degradation of global performance in parallel scientific applications.

Figure 1

Physical mechanism for the generation of idle waves in a computation distributed over nine processes. Time is presented in the $x$ axis, while the rank of the process is presented in the $y$ axis. The busy periods are represented by the dark gray (red), idle periods in black, and communication in light gray (blue) lines. An extended busy period in the process with rank four generates two idle periods on nearest-neighbor processes (rank three and five). These idle periods propagate to other processes by local synchronization of nearest-neighbor processes as a wave.

Figure 2

Idle waves in a simulation with 96 processes, $N=100000$ and a driven perturbation of the busy period (five times the average busy period) on process with rank 50 at time $t=110\text{ms}$. The plot in the top panel presents time on the $x$ axis and process rank on the $y$ axis. The white and black colors indicate the busy and idle periods, respectively. The bottom panel shows the numerical dispersion relation plot obtained by spectral analysis (maximum amplitude in red). Two nondispersive waves with opposite propagation speeds $v_P\simeq \pm 0.0012\text{rank}/\mu \text{s}$ are present.

Figure 3

Idle waves in a simulation with 2040 processes with $N=100000$ and without a perturbation. In the top panel, a contour plot of busy periods. The insert presents an enlargement of the contour plot including 168 processes. The bottom panel shows the numerical dispersion relation of idle waves.

Figure 4

$1/v_P$ dependency on $\langle T_B\rangle$ (top panel), $L$ (bottom panel black line), and $o$ (bottom panel red line). Linear best fits are superimposed to the data points.

Figure 5

Interaction between two idle waves in a simulation with 384 processes, $N=100000$, and a driven perturbation of the busy period on rank zero. The plot presents time on the $x$ axis and process rank on the $y$ axis. The white and black colors indicate the busy and idle periods, respectively. The insert in the picture represents an enlargement of the rank-time plot during the idle wave interaction.

Figure 6

Numerical dispersion relation obtained from a simulation with communication with nearest-neighbor communication and a collective operation at each computational cycle with $N=100000$ on 96 processes.

Figure 7

Numerical dispersion relation obtained from a simulation using nonblocking send and receive for communication between nearest-neighbor processes with $N=100000$ on 96 processes. In this case, the propagation speed of idle waves is $v_P\simeq \pm 0.0027\text{rank}/\mu \text{s}$.