Global communication schemes for the sparse grid combination technique

Abstract

High-dimensional simulations pose a challenge even for next-generation high-performance computers. Hierarchical methods can reduce these extreme computational demands, but they tend to introduce more complicated communication patterns. One such approach is the sparse grid combination technique that splits the problem into several smaller full grids that are synchronized regularly. We analyze this communication task for arbitrary dimension d by deriving lower bounds and giving algorithms. For the special 2-dimensional case we present an algorithm that is optimal up to constant factors. These theoretical results are supported by preliminary experiments. The baseline Sparse Grid Reduce is based on a single AllReduce. The new approach Subspace Reduce beats this baseline by up to 10x in two and 3.5x in three dimensions for large discretization levels.