- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review Applied

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Parallel tempering–inspired distributed binary optimization with in-memory computing

Xiangyi Zhang, Elisabetta Valiante, Moslem Noori, Chan-Woo Yang, and Ignacio Rozada*

Fabian Böhm, Thomas Van Vaerenbergh, Giacomo Pedretti, Masoud Mohseni, and Raymond Beausoleil

  • *Contact author: ignacio.rozada@1qbit.com
PDF

Phys. Rev. Applied 23, 034031 – Published 14 March, 2025

DOI: https://doi.org/10.1103/PhysRevApplied.23.034031

Abstract

This paper is a contribution to the Physical Review Applied collection titled Physics-Inspired Computing.

In-memory computing (IMC) has been shown to be a promising approach for solving binary optimization problems while significantly reducing energy and latency. Building on the advantages of parallel computation, we propose an IMC-compatible parallelism framework based on the physics-inspired parallel tempering (PT) algorithm, enabling cross-replica communication to improve the performance of IMC solvers. This framework not only enables an IMC solver to improve performance beyond what can be achieved through parallelization, but also affords greater flexibility for the search process with low hardware overhead. We justify that the framework can be applied to almost any IMC solver. We demonstrate the effectiveness of the framework for the Boolean satisfiability problem, using the WalkSAT heuristic as a proxy for existing IMC solvers. The resulting PT-inspired cooperative WalkSAT (PTIC-WalkSAT) algorithm outperforms the standard WalkSAT heuristic in terms of the iterations to solution in 84.0% of the tested problem instances, and its naive parallel variant does so in 64.9% of the instances, and with a higher success rate in most instances. An estimate of the energy overhead of the PTIC framework for two hardware accelerator architectures indicates that in both cases the overhead of running the PTIC framework would be less than 1% of the total energy required to run each accelerator.

View figure in article

Physics Subject Headings (PhySH)

Collections

This article appears in the following collection:

Collection on Physics-Inspired Computing

Physical Review Applied is pleased to present a Collection on Physics-Inspired Computing, highlighting the rapidly evolving field of energy-efficient computing techniques, from hardware technologies to algorithms, where physics inspiration serves as the crucial link. Contributions to this collection will be published throughout 2025. This Collection is being curated by Guest Editors Kerem Camsari and Supriyo Datta.

Article Text

References (42)

  1. M. N. Bojnordi and E. Ipekin 2016 IEEE International Symposium on High Performance Computer Architecture (HPCA) (IEEE, Barcelona, Spain, 2016), p. 1.
  2. F. Cai, S. Kumar, T. Van Vaerenbergh, R. Liu, C. Li, S. Yu, Q. Xia, J. J. Yang, R. Beausoleil, W. Lu, et al., Harnessing intrinsic noise in memristor Hopfield neural networks for combinatorial optimization, ArXiv:1903.11194.
  3. G. Pedretti, F. Böhm, M. Hizzani, T. Bhattacharya, P. Bruel, J. Moon, S. Serebryakov, D. Strukov, J. Strachan, J. Ignowski, et al., in 2023 International Electron Devices Meeting (IEDM) (IEEE, San Francisco, CA, USA, 2023), p. 1.
  4. T. Bhattacharya, G. H. Hutchinson, G. Pedretti, X. Sheng, J. Ignowski, T. Van Vaerenbergh, R. Beausoleil, J. P. Strachan, and D. B. Strukov, Computing high-degree polynomial gradients in memory, Nat. Commun. 15, 8211 (2024).
  5. A. Sharma, M. Burns, A. Hahn, and M. Huang, Augmenting an electronic Ising machine to effectively solve Boolean satisfiability, Sci. Rep. 13, 22858 (2023).
  6. T. G. Crainic and M. Toulouse, Parallel Meta-heuristics (Springer, Boston, MA, USA, 2010).
  7. T. Harada and E. Alba, Parallel genetic algorithms: A useful survey, ACM Comput. Surv. (CSUR) 53, 1 (2020).
  8. A. Silva, L. C. Coelho, and M. Darvish, Quadratic assignment problem variants: A survey and an effective parallel memetic iterated tabu search, Eur. J. Oper. Res. 292, 1066 (2021).
  9. A. McDonald, Parallel WalkSAT with clause learning, Data analysis project papers (2009).
  10. T. G. Crainic, M. Gendreau, P. Hansen, and N. Mladenović, Cooperative parallel variable neighborhood search for the p-median, J. Heuristics 10, 293 (2004).
  11. O. Polat, A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups, Comput. Oper. Res. 85, 71 (2017).
  12. P. Jarvis and A. Arbelaez, in Evolutionary Computation in Combinatorial Optimization: 20th European Conference, EvoCOP 2020, Held as Part of EvoStar 2020, Seville, Spain, April 15–17, 2020, Proceedings 20 (Springer, Seville, Spain, 2020), p. 83.
  13. K. Hukushima and K. Nemoto, Exchange Monte Carlo method and application to spin glass simulations, J. Phys. Soc. Jpn. 65, 1604 (1996).
  14. C. J. Geyer, in 23rd Symposium on the Interface, edited by E. M. Keramidas (Interface Foundation, Fairfax Station, VA, 1991), p. 156.
  15. J. Moreno, H. G. Katzgraber, and A. K. Hartmann, Finding low-temperature states with parallel tempering simulated annealing and simple Monte Carlo, Int. J. Mod. Phys. C 14, 285 (2003).
  16. Z. Zhu, C. Fang, and H. G. Katzgraber, Borealis—A generalized global update algorithm for Boolean optimization problems, Optim. Lett. 14, 2495 (2020).
  17. D. J. Earl and M. W. Deem, Parallel tempering: Theory applications, and new perspectives, Phys. Chem. Chem. Phys. 7, 3910 (2005).
  18. C. Wang, J. D. Hyman, A. Percus, and R. Caflisch, Parallel tempering for the traveling salesman problem, Int. J. Mod. Phys. C 20, 539 (2009).
  19. M. Bagherbeik, P. Ashtari, S. F. Mousavi, K. Kanda, H. Tamura, and A. Sheikholeslami, in International Conference on Parallel Problem Solving from Nature (Springer, Leiden, The Netherlands, 2020), p. 317.
  20. A. Almeida, J. D. C. Lima, and M. A. Carvalho, Revisiting the parallel tempering algorithm: High-performance computing and applications in operations research, Available at SSRN 4756904 (2024).
  21. M. Kim, S. Mandrà, D. Venturelli, and K. Jamieson, in Proceedings of the 27th Annual International Conference on Mobile Computing and Networking (Association for Computing Machinery, New York, NY, USA, New Orleans LA, USA, 2021), p. 42.
  22. S. A. Cook, in Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC ’71 (Association for Computing Machinery, New York, NY, United States, 1971), p. 151.
  23. D. S. Johnson, Approximation algorithms for combinatorial problems, J. Comput. Syst. Sci. 9, 256 (1974).
  24. I. Mironov and L. Zhang, in Theory and Applications of Satisfiability Testing-SAT 2006: 9th International Conference, Seattle, WA, USA, August 12–15, 2006. Proceedings 9 (Springer, Seattle, WA, USA, 2006), p. 102.
  25. D. Brand, in Proceedings of 1993 International Conference on Computer Aided Design (ICCAD) (IEEE, Santa Clara, CA, USA, 1993), p. 534.
  26. C. Castellini, E. Giunchiglia, and A. Tacchella, SAT-based planning in complex domains: Concurrency constraints and nondeterminism, Artif. Intell. 147, 85 (2003).
  27. D. E. Knuth, The Art of Computer Programming, Fascicle 6: Satisfiability (4.Addison-Wesley Professional, 2015).
  28. C. Shim, J. Bae, and B. Kim, in 2024 IEEE International Solid-State Circuits Conference (ISSCC) (IEEE, San Francisco, CA, USA, 2024), Vol. 67, p. 486.
  29. S. Xie, M. Yang, S. A. Lanham, Y. Wang, M. Wang, S. Oruganti, and J. P. Kulkarni, in 2023 IEEE International Solid-State Circuits Conference (ISSCC) (IEEE, San Francisco, CA, USA, 2023), p. 420.
  30. B. Selman, H. A. Kautz, and B. Cohen, Local search strategies for satisfiability testing, Cliq. Color. Satisfiab. 26, 521 (1993).
  31. H. Kautz, WalkSAT, https://gitlab.com/HenryKautz/Walksat.
  32. N. Metropolis, A. W. Rosenbluth, M. N. Rosenbluth, A. H. Teller, and E. Teller, Equation of state calculations by fast computing machines, J. Chem. Phys. 21, 1087 (1953).
  33. W. K. Hastings, Monte Carlo sampling methods using Markov chains and their applications, Biometrika 57, 97 (1970).
  34. M. Hizzani, A. Heittmann, G. Hutchinson, D. Dobrynin, T. Van Vaerenbergh, T. Bhattacharya, A. Renaudineau, D. Strukov, and J. P. Strachan, in 2024 IEEE International Symposium on Circuits and Systems (ISCAS) (IEEE, Singapore, Singapore, 2024), p. 1.
  35. B. Murmann, ADC performance survey 1997–2024, https://github.com/bmurmann/ADC-survey.
  36. A. Ankit, I. E. Hajj, S. R. Chalamalasetti, G. Ndu, M. Foltin, R. S. Williams, P. Faraboschi, W.-M. W. Hwu, J. P. Strachan, K. Roy, et al., in Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems (Association for Computing Machinery, New York, NY, USA, Providence RI USA, 2019), p. 715.
  37. J. Bebel, in Proceedings of SAT Race 2019: Solver and Benchmark Descriptions, edited by M. J. Heule, M. Järvisalo, and M. Suda (Department of Computer Science, University of Helsinki, Lisboa, Portugal, 2019), p. 47.
  38. F. Krzakala, M. Mézard, and L. Zdeborová, Reweighted belief propagation and quiet planting for random K-SAT, J. Satisf. Boolean Model. Comput. 8, 149 (2012).
  39. S. Mertens, M. Mézard, and R. Zecchina, Threshold values of random K-SAT from the cavity method, Random Struct. Algorithms 28, 340 (2006).
  40. M. Aramon, G. Rosenberg, E. Valiante, T. Miyazawa, H. Tamura, and H. G. Katzgraber, Physics-inspired optimization for quadratic unconstrained problems using a digital annealer, Front. Phys. 7, 48 (2019).
  41. I. Rozada, M. Aramon, J. Machta, and H. G. Katzgraber, Effects of setting temperatures in the parallel tempering Monte Carlo algorithm, Phys. Rev. E 100, 043311 (2019).
  42. K. Hukushima, Domain-wall free energy of spin-glass models: Numerical method and boundary conditions, Phys. Rev. E 60, 3606 (1999).

Outline

Information

Phys. Rev. Applied 23, 034031– Published 14 March, 2025
  • Received 8 November 2024
  • Accepted 13 February 2025
Article part of CHORUS
Crossmark - Check for updates button

© 2025 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation