Load Balancing For High Performance Computing Using Quantum Annealing: Conclusions and Outlook

Table of Links

Abstract and Introduction

Methods

• Quantum Annealing
• Adaptive Mesh Refinement
• Smoothed Particle Hydrodynamics

Results

• Grid Based Application
• Particle Based Application

Conclusions and Outlook, Acknowledgements, and References

Conclusions and Outlook

This study explored the utilization of quantum annealing as a strategic approach for the critical task of workload allocation to processors in parallel HPC applications. Initially focusing on less complex, grid-based applications, QA demonstrated improvements over simpler classical strategies, yet it did not conclusively surpass more sophisticated classical methods. A significant challenge for QA, unlike these classical methods, is the limited connectivity between physical qubits. This limitation results in a critical barrier to scalability, particularly given the fully connected nature of the problem at hand.

However, this drawback is somewhat mitigated in the context of the second application, which focused on load balancing in particle based codes. While the smallest problem configuration which was studied here is fully connected due to each cell’s proximity within the system, this is not expected to hold for larger problems. Recall that SPH kernels are characterized by compact support, this implies that larger problem graphs, while more extensive, are not likely to be fully connected. This subtlety enhances the feasibility of applying QA, especially in the Noisy Intermediate Scale Quantum (NISQ) era where inter-qubit connectivity can sometimes be a more critical constraint than the total number of qubits. Moreover, for simpler 2D/quasi-planar configurations this might not be as severe a constraint even for larger problem sizes. This is due to the compatibility between the problem graph and alignment of qubits with their couplers, which when implemented on a chip are inherently quasi-planar as well.

In addition, QA demonstrated an improvement in performance even against a state of the art classical method, despite the problem’s evolution into a complex multi-objective optimization. The Lagrange parameter formulation allows the user to explore the Pareto front and obtain highly optimised solutions tailored towards individual hardware architectures. Although this necessitated running a representative simulation and partitioning it repeatedly to explore the state space here, in general more cost effective methods such as machine learning could be used to estimate a good value a priori. This approach draws strong parallels with existing efforts that have endeavoured to do so for some of the other annealing parameters[79], [80]. The Ising formulation can also be readily extended to allow concurrent partitioning into multiple subsets simultaneously rather than recursively[24] to better accommodate larger problems.

Given the observed enhancements in solution quality and the reduced connectivity demands in larger problem graphs, it is conceivable that as annealers continue to evolve, they may become viable for graph partitioning tasks such as this. This is particularly relevant for hybrid applications such as load balancing where the majority of the algorithm could still be executed on CPUs, with only a select, complex segment offloaded to the quantum processor in tandem. As such, perhaps a heterogeneous architecture integrating both quantum and classical computing resources could be a strategic path forward. Particularly so in light of recent endeavours to strive towards such integrated systems[81], [82]. Moreover, one of the most time consuming components of the QA algorithm is currently the communication time between classical and quantum hardware and associated latency costs. This would be crucially reduced to almost negligible levels by co-locating the respective chips in the same data center. The time for each anneal itself remains competitive at around 20µs compared to the roughly 15µs needed by METIS and is likely to improve with evolving hardware. However, this will be of comparatively little consequence as co-location will allow the system to run in parallel, thus best leveraging the inherent strengths of each respective system.

Acknowledgements

The authors would like to thank Dr Peter Draper at Durham University and Dr Matthieu Schaller at Leiden University for insightful discussions. Similarly, the authors are grateful to Prof Vivien Kendon at University of Strathclyde for useful comments and discussion on this work, as well as the rest of the QEVEC/QuANDiE teams. The authors acknowledge funding through UKRI EPSRC projects (EP/W00772X/2 and EP/Y004515/1). This work used the DiRAC@Durham facility managed by the Institute for Computational Cosmology on behalf of the STFC DiRAC HPC Facility (www.dirac.ac.uk). The equipment was funded by BEIS capital funding via STFC capital grants ST/K00042X/1, ST/P002293/1, ST/R002371/1 and ST/S002502/1, Durham University and STFC operations grant ST/R000832/1. DiRAC is part of the National e-Infrastructure.

References

1. Andrew Danowitz, Kyle Kelley, James Mao, John P Stevenson, and Mark Horowitz. Cpu db: Recording microprocessor history: With this open database, you can mine microprocessor trends over the past 40 years. Queue, 10(4):10–27, 2012.

1. Herb Sutter et al. The free lunch is over: A fundamental turn toward concurrency in software. Dr. Dobb’s journal, 30(3):202–210, 2005.

   
   

2. Weiliang Tan, Peizhen Lin, Bo Liang, and Hui Deng. Influence of network bandwidth on parallel computing performance with intra-node and inter-node communication. In 2009 Second International Conference on Intelligent Networks and Intelligent Systems, pages 534–537. IEEE, 2009.

   
   

3. Rolf Rabenseifner et al. Hybrid parallel programming on hpc platforms. In proceedings of the Fifth European Workshop on OpenMP, EWOMP, volume 3, pages 185–194, 2003.

   
   

4. Hermann Amandus Schwarz. Ueber einige Abbildungsaufgaben: aus einer Mittheilung an Herrn Richelot in Königsberg.

   
   

5. K Hessenius and T Pulliam. A zonal approach to solution of the euler equations. In 3rd Joint Thermophysics, Fluids, Plasma and Heat Transfer Conference, page 969, 1982.

   
   

6. William D Henshaw and G Chesshire. Multigrid on composite meshes. SIAM Journal on Scientific and Statistical Computing, 8(6):914–923, 1987.

   
   

7. R Glowinski, QV Dinh, and J Periaux. Domain decomposition methods for nonlinear problems in fluid dynamics. Computer methods in applied mechanics and engineering, 40(1):27–109, 1983.

   
   

8. David E Keyes, Lois C McInnes, Carol Woodward, William Gropp, Eric Myra, Michael Pernice, John Bell, Jed Brown, Alain Clo, Jeffrey Connors, et al. Multiphysics simulations: Challenges and opportunities. The International Journal of High Performance Computing Applications, 27(1):4–83, 2013.

   
   

9. G Houzeaux, JC Cajas, Marco Discacciati, B Eguzkitza, A Gargallo-Peiró, M Rivero, and M Vázquez. Domain decomposition methods for domain composition purpose: Chimera, overset, gluing and sliding mesh methods. Archives of Computational Methods in Engineering, 24:1033–1070, 2017.

   
   

10. HS Tang, RD Haynes, and G Houzeaux. A review of domain decomposition methods for simulation of fluid flows: Concepts, algorithms, and applications. Archives of Computational Methods in Engineering, 28:841–873, 2021.

    
    

11. Peng Wang, Tom Abel, and Ralf Kaehler. Adaptive mesh fluid simulations on gpu. New Astronomy, 15(7):581–589, 2010.

    
    

12. JA Bennett and ME Botkin. Structural shape optimization with geometric description and adaptive mesh refinement. AIAA journal, 23(3):458–464, 1985.

    
    

13. Lorenzo Botti, Marina Piccinelli, Bogdan Ene-Iordache, Andrea Remuzzi, and Luca Antiga. An adaptive mesh refinement solver for large-scale simulation of biological flows. International Journal for Numerical Methods in Biomedical Engineering, 26(1):86–100, 2010.

    
    

14. Gerhard Zumbusch. Parallel multilevel methods: adaptive mesh refinement and loadbalancing. Springer Science & Business Media, 2012.

    
    

15. Anshu Dubey, Ann Almgren, John Bell, Martin Berzins, Steve Brandt, Greg Bryan, Phillip Colella, Daniel Graves, Michael Lijewski, Frank Löffler, et al. A survey of high level frameworks in block-structured adaptive mesh refinement packages. Journal of Parallel and Distributed Computing, 74(12):3217–3227, 2014.

    
    

16. Robert A Gingold and Joseph J Monaghan. Smoothed particle hydrodynamics: theory and application to non-spherical stars. Monthly notices of the royal astronomical society, 181(3):375–389, 1977.

18. Joseph J Monaghan. Smoothed particle hydrodynamics and its diverse applications. Annual Review of Fluid Mechanics, 44:323–346, 2012.

19. M Safdari Shadloo, G Oger, and David Le Touzé. Smoothed particle hydrodynamics method for fluid flows, towards industrial applications: Motivations, current state, and challenges. Computers & Fluids, 136:11–34, 2016.

20. Steven J Lind, Benedict D Rogers, and Peter K Stansby. Review of smoothed particle hydrodynamics: towards converged lagrangian flow modelling. Proceedings of the royal society A, 476(2241):20190801, 2020.

21. Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse ising model. Physical Review E, 58(5):5355, 1998. 22. Andrew Lucas. Ising formulations of many np problems. Frontiers in physics, 2:5, 2014.

23. B Camino, J Buckeridge, PA Warburton, V Kendon, and SM Woodley. Quantum computing and materials science: A practical guide to applying quantum annealing to the configurational analysis of materials. Journal of Applied Physics, 133(22), 2023.

24. Hayato Ushijima-Mwesigwa, Christian FA Negre, and Susan M Mniszewski. Graph partitioning using quantum annealing on the d-wave system. In Proceedings of the Second International Workshop on Post Moores Era Supercomputing, pages 22–29, 2017.

25. Hugh Collins and Chris Nay. Ibm unveils 400 qubit-plus quantum processor and next-generation ibm quantum system two, 2022.

26. D-Wave Quantum Inc. D-wave announces 1,200+ qubit advantage2™ prototype in new, lower-noise fabrication stack, demonstrating 20x faster time-to-solution on important class of hard optimization problems, 2024. [Press release].

27. Helmut G Katzgraber, Firas Hamze, and Ruben S Andrist. Glassy chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines. Physical Review X, 4(2):021008, 2014.

28. Helmut G Katzgraber, Firas Hamze, Zheng Zhu, Andrew J Ochoa, and Humberto Munoz-Bauza. Seeking quantum speedup through spin glasses: The good, the bad, and the ugly. Physical Review X, 5(3):031026, 2015.

29. Sergio Boixo, Vadim N Smelyanskiy, Alireza Shabani, Sergei V Isakov, Mark Dykman, Vasil S Denchev, Mohammad H Amin, Anatoly Yu Smirnov, Masoud Mohseni, and Hartmut Neven. Computational multiqubit tunnelling in programmable quantum annealers. Nature communications, 7(1):10327, 2016.

30. Vasil S Denchev, Sergio Boixo, Sergei V Isakov, Nan Ding, Ryan Babbush, Vadim Smelyanskiy, John Martinis, and Hartmut Neven. What is the computational value of finite-range tunneling? Physical Review X, 6(3):031015, 2016.

31. Sheir Yarkoni, Elena Raponi, Thomas Bäck, and Sebastian Schmitt. Quantum annealing for industry applications: Introduction and review. Reports on Progress in Physics, 2022.

32. Humberto Munoz Bauza and Daniel A Lidar. Scaling advantage in approximate optimization with quantum annealing. arXiv preprint arXiv:2401.07184, 2024.

33. Nicholas Chancellor, Robert Cumming, and Tim Thomas. Toward a standardized methodology for constructing quantum computing use cases. arXiv preprint arXiv:2006.05846, 2020.

34. J Aguilar Mena, Omar Shaaban, Victor Lopez, Marta Garcia, Paul Carpenter, E Ayguad, and Jesus Labarta. Transparent load balancing of mpi programs using ompss-2@ cluster and dlb. In 51st International Conference on Parallel Processing (ICPP), 2022.

35. Guixun Zhu, Jason Hughes, Siming Zheng, and Deborah Greaves. A novel mpi-based parallel smoothed particle hydrodynamics framework with dynamic load balancing for free surface flow. Computer Physics Communications, 284:108608, 2023.

36. Ali Mohammed, Aurélien Cavelan, Florina M Ciorba, Rubén M Cabezón, and Ioana Banicescu. Two-level dynamic load balancing for high performance scientific applications. In Proceedings of the 2020 SIAM Conference on Parallel Processing for Scientific Computing, pages 69–80. SIAM, 2020.

37. Kyle G Miller, Roman P Lee, Adam Tableman, Anton Helm, Ricardo A Fonseca, Viktor K Decyk, and Warren B Mori. Dynamic load balancing with enhanced shared-memory parallelism for particle-in-cell codes. Computer Physics Communications, 259:107633, 2021.

38. Bin Liu, Dawid Zydek, Henry Selvaraj, and Laxmi Gewali. Accelerating high performance computing applications: Using cpus, gpus, hybrid cpu/gpu, and fpgas. In 2012 13th International Conference on Parallel and Distributed Computing, Applications and Technologies, pages 337–342. IEEE, 2012.

39. Gang Chen, Guobo Li, Songwen Pei, and Baifeng Wu. High performance computing via a gpu. In 2009 First International Conference on Information Science and Engineering, pages 238–241. IEEE, 2009.

40. Devesh Tiwari, Saurabh Gupta, James Rogers, Don Maxwell, Paolo Rech, Sudharshan Vazhkudai, Daniel Oliveira, Dave Londo, Nathan DeBardeleben, Philippe Navaux, et al. Understanding gpu errors on large-scale hpc systems and the implications for system design and operation. In 2015 IEEE 21st International Symposium on High Performance Computer Architecture (HPCA), pages 331–342. IEEE, 2015.

41. Adam Callison and Nicholas Chancellor. Hybrid quantum-classical algorithms in the noisy intermediate-scale quantum era and beyond. Phys. Rev. A, 106:010101, Jul 2022.

42. Nathalie P De Leon, Kohei M Itoh, Dohun Kim, Karan K Mehta, Tracy E Northup, Hanhee Paik, BS Palmer, Nitin Samarth, Sorawis Sangtawesin, and David W Steuerman. Materials challenges and opportunities for quantum computing hardware. Science, 372(6539):eabb2823, 2021.

43. Sangil Kwon, Akiyoshi Tomonaga, Gopika Lakshmi Bhai, Simon J Devitt, and Jaw-Shen Tsai. Gate-based superconducting quantum computing. Journal of Applied Physics, 129(4):041102, 2021.

44. Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information. Cambridge university press, 2010.

45. Tameem Albash and Daniel A Lidar. Adiabatic quantum computation. Reviews of Modern Physics, 90(1):015002, 2018.

46. Wim Van Dam, Michele Mosca, and Umesh Vazirani. How powerful is adiabatic quantum computation? In Proceedings 42nd IEEE symposium on foundations of computer science, pages 279–287. IEEE, 2001.

47. Dorit Aharonov, Wim Van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, and Oded Regev. Adiabatic quantum computation is equivalent to standard quantum computation. SIAM review, 50(4):755–787, 2008.

48. Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. arXiv preprint quant-ph/0001106, 2000.

49. Tosio Kato. On the adiabatic theorem of quantum mechanics. Journal of the Physical Society of Japan, 5(6):435–439, 1950.

50. Sabine Jansen, Mary-Beth Ruskai, and Ruedi Seiler. Bounds for the adiabatic approximation with applications to quantum computation. Journal of Mathematical Physics, 48(10), 2007.

51. Alexander Elgart and George A Hagedorn. A note on the switching adiabatic theorem. Journal of Mathematical Physics, 53(10), 2012.

52. RB Stinchcombe. Ising model in a transverse field. i. basic theory. Journal of Physics C: Solid State Physics, 6(15):2459, 1973.

53. Andrew D King, Sei Suzuki, Jack Raymond, Alex Zucca, Trevor Lanting, Fabio Altomare, Andrew J Berkley, Sara Ejtemaee, Emile Hoskinson, Shuiyuan Huang, et al. Coherent quantum annealing in a programmable 2,000 qubit ising chain. Nature Physics, 18(11):1324–1328, 2022.

54. E. J. Crosson and D. A. Lidar. Prospects for quantum enhancement with diabatic quantum annealing. Nature Reviews Physics, 3(7):466–489, Jul 2021.

55. Adam Callison, Max Festenstein, Jie Chen, Laurentiu Nita, Viv Kendon, and Nicholas Chancellor. Energetic perspective on rapid quenches in quantum annealing. PRX Quantum, 2:010338, Mar 2021.

56. Dimitris Bertsimas and John Tsitsiklis. Simulated annealing. Statistical science, 8(1):10–15, 1993.

57. Ran Yaacoby, Nathan Schaar, Leon Kellerhals, Oren Raz, Danny Hermelin, and Rami Pugatch. Comparison between a quantum annealer and a classical approximation algorithm for computing the ground state of an ising spin glass. Physical Review E, 105(3):035305, 2022.

58. Elias Starchl and Helmut Ritsch. Unraveling the origin of higher success probabilities in quantum annealing versus semi-classical annealing. Journal of Physics B: Atomic, Molecular and Optical Physics, 55(2):025501, 2022.

59. Nicholas Chancellor and Viv Kendon. Experimental test of search range in quantum annealing. Phys. Rev. A, 104:012604, Jul 2021.

60. Mohsen Razavy. Quantum theory of tunneling. World Scientific, 2013.

61. Erica K Grant and Travis S Humble. Adiabatic quantum computing and quantum annealing. In Oxford Research Encyclopedia of Physics. 2020.

62. Pascal Scholl, Michael Schuler, Hannah J Williams, Alexander A Eberharter, Daniel Barredo, Kai-Niklas Schymik, Vincent Lienhard, Louis-Paul Henry, Thomas C Lang, Thierry Lahaye, et al. Quantum simulation of 2d antiferromagnets with hundreds of rydberg atoms. Nature, 595(7866):233–238, 2021.

63. Wolfgang Lechner, Philipp Hauke, and Peter Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Science advances, 1(9):e1500838, 2015.

64. Sepehr Ebadi, Tout T Wang, Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Dolev Bluvstein, Rhine Samajdar, Hannes Pichler, Wen Wei Ho, et al. Quantum phases of matter on a 256-atom programmable quantum simulator. Nature, 595(7866):227–232, 2021.

65. Diego de Falco and Dario Tamascelli. An introduction to quantum annealing. RAIRO-Theoretical Informatics and Applications, 45(1):99–116, 2011.

66. Omer Rathore and Salvador Navarro-Martinez. Flame dynamics modelling using artificially thickened models. Flow, Turbulence and Combustion, pages 1–31, 2023.

67. J Bell, A Almgren, V Beckner, M Day, M Lijewski, A Nonaka, and W Zhang. Boxlib user’s guide. github. com/BoxLibCodes/BoxLib, 2012.

68. Weiqun Zhang, Ann Almgren, Marcus Day, Tan Nguyen, John Shalf, and Didem Unat. Boxlib with tiling: An adaptive mesh refinement software framework. SIAM Journal on Scientific Computing, 38(5):S156–S172, 2016.

69. Ann S Almgren, Vincent E Beckner, John B Bell, MS Day, Louis H Howell, CC Joggerst, MJ Lijewski, Andy Nonaka, M Singer, and Michael Zingale. Castro: A new compressible astrophysical solver. i. hydrodynamics and self-gravity. The Astrophysical Journal, 715(2):1221, 2010.

70. Andrew Nonaka, AS Almgren, JB Bell, MJ Lijewski, CM Malone, and M Zingale. Maestro: An adaptive low mach number hydrodynamics algorithm for stellar flows. The Astrophysical Journal Supplement Series, 188(2):358, 2010.

71. George SH Pau, Ann S Almgren, John B Bell, and Michael J Lijewski. A parallel second-order adaptive mesh algorithm for incompressible flow in porous media. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 367(1907):4633–4654, 2009.

72. Mark S Day and John B Bell. Numerical simulation of laminar reacting flows with complex chemistry. Combustion Theory and Modelling, 4(4):535, 2000.

73. Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.

74. Matthieu Schaller, Josh Borrow, Peter W Draper, Mladen Ivkovic, Stuart McAlpine, Bert Vandenbroucke, Yannick Bahé, Evgenii Chaikin, Aidan BG Chalk, Tsang Keung Chan, et al. Swift: A modern highly-parallel gravity and smoothed particle hydrodynamics solver for astrophysical and cosmological applications. arXiv preprint arXiv:2305.13380, 2023.

75. Matthieu Schaller, Pedro Gonnet, Aidan BG Chalk, and Peter W Draper. Swift: Using task-based parallelism, fully asynchronous communication, and graph partition-based domain decomposition for strong scaling on more than 100,000 cores. In Proceedings of the platform for advanced scientific computing conference, pages 1–10, 2016.

76. George Karypis and Vipin Kumar. Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices. 1997.

77. Jun Cai, William G Macready, and Aidan Roy. A practical heuristic for finding graph minors. arXiv preprint arXiv:1406.2741, 2014.

78. Stefanie Zbinden, Andreas Bärtschi, Hristo Djidjev, and Stephan Eidenbenz. Embedding algorithms for quantum annealers with chimera and pegasus connection topologies. In International Conference on High Performance Computing, pages 187–206. Springer, 2020.

79. Aaron Barbosa, Elijah Pelofske, Georg Hahn, and Hristo N Djidjev. Optimizing embedding-related quantum annealing parameters for reducing hardware bias. In Parallel Architectures, Algorithms and Programming: 11th International Symposium, PAAP 2020, Shenzhen, China, December 28–30, 2020, Proceedings 11, pages 162–173. Springer, 2021.

80. Aaron Barbosa, Elijah Pelofske, Georg Hahn, and Hristo N Djidjev. Using machine learning for quantum annealing accuracy prediction. Algorithms, 14(6):187, 2021.

81. Gabriele Cavallaro, Morris Riedel, Thomas Lippert, and Kristel Michielsen. Hybrid quantum-classical workflows in modular supercomputing architectures with the JULICH unified infrastructure for quantum computing. In IGARSS 2022-2022 IEEE International Geoscience and Remote Sensing Symposium, pages 4149–4152. IEEE, 2022.

82. T Lippert and K Michielsen. Perspectives of quantum computing at the JULICH supercomputing centre. 2022.