Design and Analysis of Two Highly Scalable Sparse Grid Combination Algorithms

Abstract

Many petascale and exascale scientific simulations involve the time evolution of systems modelled as Partial Differential Equations (PDEs). The sparse grid combination technique (SGCT) is a cost-effective method for solve time-evolving PDEs. It consists of evolving PDE over a set of grids of differing resolution in each dimension, and then combining the results to approximate the solution of the PDE on a grid of high resolution in all dimensions. We present two new parallel algorithms for the SGCT that support the full distributed memory parallelization over the dimensions of the component grids, as well as across the grids as well. They also support algorithmic-based fault tolerance. The direct algorithm is so called because it directly implements a SGCT combination formula. We give details of the design and implementation of a `partial' sparse grid data structure, which is needed for its efficient implementation. The second algorithm converts each component grid into their hierarchical surpluses, and then uses the direct algorithm on each of the hierarchical surpluses. The conversion to/from the hierarchical surpluses is also an important algorithm in its own right. It requires a technique called sub-griding in order to correctly deal with the combination of very small surpluses. An analysis of both indicates the direct algorithm minimizes the number of messages, whereas the hierarchical surplus minimizes memory consumption and offers a modest reduction in bandwidth. The direct algorithm also scales better with respect to SGCT level and grid dimensionality. Experimental results indicates that, for scenarios of practical interest, both are sufficiently scalable with respect to core count but algorithm has generally better performance, at least by a factor of 2 in most cases. It also scales better with the SGCT level. Hierarchical surplus formation is much less communication intensive, but shows less scalability with increasing core counts. Altering the layout of processes in the process grids and the mapping of processes affects the performance of the 2D SGCT by less than 10%, and affects even less the application part of an SGCT advection application even less.