Proxy-equation paradigm: A strategy for massively parallel asynchronous computations

Massively parallel simulations of transport equation systems call for a paradigm change in algorithm development to achieve efficient scalability. Traditional approaches require time synchronization of processing elements (PEs), which severely restricts scalability. Relaxing synchronization requirement introduces error and slows down convergence. In this paper, we propose and develop a novel “proxy equation” concept for a general transport equation that (i) tolerates asynchrony with minimal added error, (ii) preserves convergence order and thus, (iii) expected to scale efficiently on massively parallel machines. The central idea is to modify a priori the transport equation at the PE boundaries to offset asynchrony errors. Proof-of-concept computations are performed using a one-dimensional advection (convection) diffusion equation. The results demonstrate the promise and advantages of the present strategy.

Figure 1

Schematic of synchronous and asynchronous (in italics) errors. Logic of proxy equation is also shown.

Figure 2

The delay error, $E_i^{\tilde{k}}-E_i$, for the original equation (red squares) and the proxy equation (blue triangles) at (a) $tc/l=0.08$ (b) $tc/l=1.0$. Simulation parameters: $N=128, P=4, c=1, \alpha =0.01, r_{\alpha }=0.1$, with $\{p_0,p_1\}=\{0.3,0.7\}$

Figure 3

Scaling of average error with number of grid points for proxy equation and unmodified equation at $tc/l=1.0$ with $r_{\alpha }=0.1, c=1.0, \lambda =2$, and $\alpha =0.1$. All proxy equation solutions fall on the same line.

Figure 4

Scaling of average error with number of grid points for proxy equation and unmodified equation at $tc/l=1.0$ with $r_{\alpha }=0.1, c=1.0, \lambda =8$, and $\alpha =0.1$. All proxy equation solutions fall on the same line.

Figure 5

Delay error comparisons at $tc/l=1.0$ for the proxy equation (solid blue line) and the original equation with (a) asynchrony tolerant scheme, (b) delay difference scheme (dot dashed red). Simulation parameters: $N=128, P=4, c=1.0, \alpha =0.01, r_{\alpha }=0.1$, with $\{p_0,p_1\}=\{0.3,0.7\}$.

Figure 6

Scaling of average error with number of grid points for proxy equation and unmodified Burgers equation at $tc/l=1.0$, with $r_{\alpha }=0.1$ and $\alpha =0.1$. All proxy equation solutions fall on the same line.