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.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com