Synchronization-free algorithms for exascale and beyond : A study of Asynchronous and Batched Iterative Methods

Computing at scale has enabled scientific discovery in various fields, such as bioinformatics, energy, healthcare, and transportation. The algorithmic and computing landscapes must adapt as our mathematical models grow, aiming to provide a more accurate and realistic view of our physical world.

In the exascale era, extracting maximum performance from a system requires efficient algorithms that can take advantage of the massive parallelism that these machines provide. The heterogeneous nature of these machines necessitates efficient implementations at single and multi-GPU levels, with GPUs providing most of the parallelism. Ensuring minimal synchronization bottlenecks is paramount for efficient computation across this whole hierarchy. Synchronization for information exchange is required for many state-of-the-art algorithms such as linear solvers, which form the workhorse of many scientific applications. Minimizing or removing these synchronizations can accelerate applications.

In this work, we look at two techniques that minimize synchronizations between parallel computing units. The first technique, batching, maximizes the available parallelism on a Graphics Processing unit (GPU) by utilizing the perfect parallelism available for the solution of independent but related linear systems. ... mehrMapping these independent linear system solutions at the appropriate compute hierarchy level enables almost perfect scaling for single and multi-GPU systems. With a careful design of the data structures and the linear solver kernels, we provide a high-performance implementation of the batched solvers that significantly outperform state-of-the-art implementations. We showcase the benefits of these batched solvers for problems from different origins, including integrations into two real-world applications.

The second technique removes existing synchronizations by following a data asynchronous approach. In this case, the parallel computing elements process the latest available local data and incorporate any required data from their neighbors asynchronously. Using a probabilistic model, we study and analyze these asynchronous iterative methods. We also showcase the benefits of using these asynchronous methods with an efficient GPU implementation that outperforms the synchronous variant. To enable scaling to multiple GPUs, we implement, evaluate, and analyze the asynchronous Schwarz methods and show that they can beat their synchronous counterparts for realistic test cases.

Synchronization-free techniques help accelerate scientific simulations, enabling them to maximize the available compute resources. This allows scientists to efficiently scale up their simulations, gain a deeper understanding of the physical phenomena, and perform ground-breaking science to further scientific inquiry.