Parallelization methods in the semi-lagrangian advection scheme

The purpose of this thesis was to investigate methods of parallelization in the semi-Lagrangian advection scheme. Semi-Lagrangian advection or trans-port (SLT) is a numerical scheme for dealing with advective terms often found in systems of partial differential equations. These advective terms occur in various applications including weather prediction and groundwater contam-ination models. Semi-Lagrangian advection has gained increased attention in the last decade due to its ability to take larger timesteps than Eulerian schemes while maintaining the a regular resolution. Parallelization of the semi-Lagrangian advection scheme has the poten-tial to further increase the efficiency of the scheme by dividing it into smaller independent sub-tasks that can be performed simultaneously on several pro-cessors. Ideally, if the sub-tasks could be evenly assigned to N processors, then the parallel approach should be able to complete the advection N times faster than the sequential method. However, this is usually an unobtainable goal as processor must communicate with each other at certain points in or-der to complete the total task. This is an additional overhead not needed in a sequential setting which reduces the computational speed up to be less than N times faster. Since communication is an important factor in computational efficiency, the communication algorithm used becomes important. Two com-munication algorithms are proposed in this thesis called process migration and data migration. These two approaches are evaluated and compared un-der varying circumstances in order to understand the computational behavior of each. This thesis briefly reviews mathematical transport theory, provides a background for semi-Lagrangian advection, and derives a popular version of SLT known as the three-time-level scheme. Variations of and applications of SLT are discussed. A parallelization of SLT is presented as well as various communication algorithms including data and process migration. Special programming considerations are discussed and a series of tests are conducted on two versions of SLT: the three-time-level and the D_N scheme. These tests serve to evaluate the scalability and performance of the parallelization. The performance of the parallelization depended primarily on the magnitude of the velocity field. The larger the magnitude, the greater the communication requirement. In order to better interpret results, most tests were conducted under a constant velocity field. The results of the tests suggest that the latency period (an initialization period before a message is passed) plays a significant role in the parallelization. As a result, under the conditions that were tested, data migration was found to be better for the three-time-level scheme and for the D_N scheme until a velocity of about .2. Furthermore, the D_N scheme was found to have a computational advantage over the three-time-level scheme using either communication algorithm. These results should not be extended to non-constant velocity as is is illustrated in the final test.