A note on reducing communication costs in explicit time stepping methods on parallel computers

摘要

We present a new parallel implementation of explicit time stepping methods for time dependent equations in one or two spatial dimensions. The aim is to minimize the number of data transfers. In one spatial dimension, τ explicit time steps on p processors using a grid of size n need O(τn/p) arithmetical operations and O(τ) startup operations. The method presented below also requires O(τn/p) arithmetical operations but only O(τp/n) startup operations. In two spatial dimensions, using a grid of size n × n and given the same algorithm, the startup time of O(τ) operations using the conventional approach is considerably reduced to O(τ√p/n) startup operations. All constants regarding the O-notation are less than 5.