Quantum Annealing Enhances Load Balancing in High Performance Computing

Load balancing in high performance computing (HPC) is crucial for maximizing system potential, particularly with the rise of exascale computing. It involves distributing computational work evenly across processors to minimize data communication between them and prevent resource wastage. Quantum annealing is being explored for its potential in load balancing, particularly in grid-based applications. Domain decomposition (DD) and adaptive mesh refinement (AMR) are key methods in HPC, with DD splitting computational domains into smaller subdomains and AMR varying spatial resolution to optimize resource use. Smoothed particle hydrodynamics (SPH) is a mesh-free simulation method used in off-grid applications.

What is Load Balancing in High Performance Computing?

Load balancing in high performance computing (HPC) is the distribution of computational work between available processors. This concept is critically important for leveraging the full potential of HPC systems, especially with the advent of exascale computing. The effectiveness of HPC applications heavily depends on the equitable distribution of computational workload across available resources. Load balancing encompasses not just fair distribution of the computational tasks across processors, but also doing so in a way that minimises the need to communicate data between processors.

All processors need to wait for the slowest one to finish before proceeding to the next step, thus potentially resulting in idling and resource wastage at a much larger scale if even a single processor lags behind. In addition to this, communication bandwidth between processors is usually not as efficient as within the processor itself and ideally should be minimised. The importance of load balancing clearly extends beyond any singular discipline. However, for the purposes of this paper, emphasis is placed on applications in the realm of computational fluid dynamics.

How Does Quantum Annealing Apply to Load Balancing?

Quantum annealing is investigated for its application to load balance two paradigmatic algorithms in high performance computing. These are adaptive mesh refinement and smoothed particle hydrodynamics, chosen as representative grid and off-grid target applications. While the methodology for obtaining real simulation data to partition is application-specific, the proposed balancing protocol itself remains completely general.

In a grid-based context, quantum annealing is found to outperform classical methods such as the round-robin protocol. However, it lacks a decisive advantage over more advanced methods such as steepest descent or simulated annealing, despite remaining competitive. The primary obstacle to scalability is found to be limited coupling on current quantum annealing hardware. However, for the more complex particle formulation approached as a multi-objective optimization, quantum annealing solutions are demonstrably Pareto dominant to state-of-the-art classical methods across both objectives. This signals a noteworthy advancement in solution quality, which can have a large impact on effective CPU usage.

What is Domain Decomposition in High Performance Computing?

In the context of grid-based applications, it is usually not the governing equations themselves that define the load balancing problem but the chosen method of domain decomposition (DD). DD is the art of splitting a computational domain into smaller subdomains. This allows solving each smaller problem individually before subsequently recombining into the global solution.

Historically, since its original proposal, DD in the realm of fluid simulations has been used to accommodate the inherent challenges of complex geometries or higher dimensionality. Extensive research in the last 40 years has led to rapid development, facilitating application to multiphysics problems, moving meshes, and a wider pool of applications. More importantly, in the context of modern HPC, DD is an indispensable tool for transforming the global simulation domain into subcomponents that can be assigned to individual processors.

What is Adaptive Mesh Refinement in High Performance Computing?

A popular choice of DD for large-scale simulations in the realms of fluids, stress analysis, and biological flows among others is adaptive mesh refinement (AMR). AMR operates on the principle that different areas of the computational domain are best solved with different levels of spatial resolution. This can prevent wastage of computational resources in regions with little activity while maintaining precision in zones of interest.

The method is particularly useful for applications with large variation of spatial scales or when high-resolution data is required in specific regions. This paper considers block-structured implementations as a representative class and does not make further distinctions with alternative AMR varieties.

What is Smoothed Particle Hydrodynamics in High Performance Computing?

For off-grid applications, the representative method here is smoothed particle hydrodynamics (SPH), a mesh-free simulation method for continuum mechanics. Since its original conception, its application has spread to encompass a wide variety of fields including but not limited to solid mechanics, engineering, astrophysics, and the food industry.

Fundamentally, SPH is an interpolation technique that utilizes a collection of unordered points or particles to ascertain the value of a function at a specific point. This process is facilitated through the use of a kernel function, which effectively integrates the influence of adjacent particles to compute the value of a function at the desired point. When applied in the context of computational fluids, this forms a Lagrangian particle method for solving hydrodynamic equations, thus forming an equivalent counterpart to the Eulerian equations solved by grid-based methods.