Computing high-degree polynomial gradients in memory.
Journal
Nature communications
ISSN: 2041-1723
Titre abrégé: Nat Commun
Pays: England
ID NLM: 101528555
Informations de publication
Date de publication:
18 Sep 2024
18 Sep 2024
Historique:
received:
19
02
2024
accepted:
11
09
2024
medline:
19
9
2024
pubmed:
19
9
2024
entrez:
18
9
2024
Statut:
epublish
Résumé
Specialized function gradient computing hardware could greatly improve the performance of state-of-the-art optimization algorithms. Prior work on such hardware, performed in the context of Ising Machines and related concepts, is limited to quadratic polynomials and not scalable to commonly used higher-order functions. Here, we propose an approach for massively parallel gradient calculations of high-degree polynomials, which is conducive to efficient mixed-signal in-memory computing circuit implementations and whose area scales proportionally with the product of the number of variables and terms in the function and, most importantly, independent of its degree. Two flavors of such an approach are proposed. The first is limited to binary-variable polynomials typical in combinatorial optimization problems, while the second type is broader at the cost of a more complex periphery. To validate the former approach, we experimentally demonstrated solving a small-scale third-order Boolean satisfiability problem based on integrated metal-oxide memristor crossbar circuits, with competitive heuristics algorithm. Simulation results for larger-scale, more practical problems show orders of magnitude improvements in area, speed and energy efficiency compared to the state-of-the-art. We discuss how our work could enable even higher-performance systems after co-designing algorithms to exploit massively parallel gradient computation.
Identifiants
pubmed: 39294142
doi: 10.1038/s41467-024-52488-y
pii: 10.1038/s41467-024-52488-y
doi:
Types de publication
Journal Article
Langues
eng
Sous-ensembles de citation
IM
Pagination
8211Subventions
Organisme : United States Department of Defense | Defense Advanced Research Projects Agency (DARPA)
ID : FA8650-23-3-7313
Informations de copyright
© 2024. The Author(s).
Références
Boyd, S. & Vandenberghe, L. Convex Optimization (Cambridge U. Press, 2004).
Nocedal, J. & Wright, S. J. Numerical Optimization (Springer, 1999).
Lasdon, L., Mitter, S. & Waren, A. The conjugate gradient methods for optimal control problems. IEEE Trans. Autom. Control 12, 132–138 (1967).
doi: 10.1109/TAC.1967.1098538
Glover, F., Kochenberger, G., Henning, R. & Du, Y. Quantum bridge analytics I: A tutorial on formulating and using QUBO models. Ann. Oper. Res. 314, 141–183 (2022).
doi: 10.1007/s10479-022-04634-2
Ruder, S. An overview of gradient descent optimization algorithms. Preprint at arXiv https://doi.org/10.48550/arXiv.1609.04747 (2017).
Mohseni, N., McMahon, P. L. & Byrnes, T. Ising machines as hardware solvers of combinatorial optimization problems. Nat. Rev. Phys. 4.6, 363–379 (2023).
Calvanese Strinati, M. & Conti, C. Multidimensional hyperspin machine. Nat. Commun. 13, 7248 (2022).
doi: 10.1038/s41467-022-34847-9
pubmed: 36433964
pmcid: 9700766
Hopfield, J. J. Neural networks and physical systems with emergent collective computational abilities. Proc. Natl Acad. Sci. USA 79, 2554–2558 (1982).
doi: 10.1073/pnas.79.8.2554
pubmed: 6953413
pmcid: 346238
Ackley, D. H., Hinton, G. E. & Sejnowski, T. J. A learning algorithm for Boltzmann machines. Cogn. Sci. 9, 147–169 (1985).
Hopfield, J. J. Neurons with graded response have collective computational properties like those of two-state neurons. Proc. Natl Acad. Sci. USA 81, 3088–3092 (1984).
doi: 10.1073/pnas.81.10.3088
pubmed: 6587342
pmcid: 345226
Strachan, J. P. & Datta, S. Chapter 11: Emerging hardware approaches for optimization. In: Christensen, D.V. et al. 2022 Roadmap on neuromorphic computing and engineering. IOP Neuromorphic Comput. Eng. 2, 2 (2022).
Eryilmaz, S. B. et al. Brain-like associative learning using a nanoscale nonvolatile phase change synaptic device array. Front. Neurosci. 8, 205 (2014).
doi: 10.3389/fnins.2014.00205
pubmed: 25100936
pmcid: 4106403
Afoakwa, R. et al. BRIM: Bistable resistively-coupled Ising machine. HPCA’21 (2021).
Guo, X. et al. Modeling and experimental demonstration of a Hopfield network analog-to-digital converter with hybrid CMOS/memristor circuits. Front. Neurosci. 9, 488 (2015).
doi: 10.3389/fnins.2015.00488
pubmed: 26732664
pmcid: 4689862
Mahmoodi, M. R., Prezioso, M. & Strukov, D. B. Versatile stochastic dot product circuits based on nonvolatile memories for high performance neurocomputing and neuro- optimization. Nat. Commun. 10, 5113 (2019).
doi: 10.1038/s41467-019-13103-7
pubmed: 31704925
pmcid: 6841978
Cai, F. et al. Power-efficient combinatorial optimization using intrinsic noise in memristor Hopfield neural networks. Nat. Electron. 3, 409–418 (2020).
doi: 10.1038/s41928-020-0436-6
Jiang, M., Shan, K., He, C. & Li, C. Efficient combinatorial optimization by quantum-inspired parallel annealing in analogue memristor crossbar. Nat. Commun. 14, 5927 (2023).
doi: 10.1038/s41467-023-41647-2
pubmed: 37739944
pmcid: 10516914
Li, C. et al. Analogue signal and image processing with large memristor crossbars. Nat. Electron. 1, 52–59 (2018).
doi: 10.1038/s41928-017-0002-z
Wan, W. et al. A compute-in-memory chip based on resistive random access memory. Nature 608, 504–512 (2022).
doi: 10.1038/s41586-022-04992-8
pubmed: 35978128
pmcid: 9385482
Amirsoleimani, A. et al. In-memory vector-matrix multiplication in monolithic complementary metal–oxide–semiconductor-memristor integrated circuits: Design choices, challenges, and perspectives. Adv. Intell. Syst. 2, 2640–4567 (2020).
doi: 10.1002/aisy.202000115
Sebastian, A., Le Gallo, M., Khaddam-Aljameh, R. & Eleftheriou, E. Memory device and applications for in-memory computing. Nat. Nanotechnol. 15, 529–544 (2020).
doi: 10.1038/s41565-020-0655-z
pubmed: 32231270
Hizzani, M. et al. Memristor-based hardware and algorithms for higher-order Hopfield optimization solver outperforming quadratic Ising machines. In IEEE International Symposium on Circuits and Systems (ISCAS) 1–5 (2024).
Senjowski, T. J. High-order Boltzmann Machines. Neural Networks for Computing, (1986).
Bybee, C. et al. Efficient optimization with higher-order Ising Machines. Nat. Commun. 14, 6033 (2023).
doi: 10.1038/s41467-023-41214-9
pubmed: 37758716
pmcid: 10533504
Johnson, J. L. A neural network approach to the 3-satisfiability problem. J. Parallel Distrib. Comput. 6, 435–449 (1989).
doi: 10.1016/0743-7315(89)90068-3
Joya, G., Atencia, M. A. & Sandoval, F. Hopfield neural networks for optimization: Study of the different dynamics. Neurocomputing 43, 219–237 (2002).
doi: 10.1016/S0925-2312(01)00337-X
Chermoshentsev, D. A., et al. Polynomial unconstrained binary optimization inspired by optical simulation. Preprint at arXiv https://doi.org/10.48550/arXiv.2106.13167 (2021).
Sharma, A. et al. Augmented electronic Ising machine as an effective SAT solver. Nat. Sci. Rep. 13, 22858 (2023).
Lucas, A. Ising formulations of many NP problems. Front. Phys. 2, 5 (2014).
doi: 10.3389/fphy.2014.00005
Hart, W. E. & Istrail, S. Robust proofs of NP-hardness for protein folding: general lattices and energy potentials. J. Comput. Biol. 4, 1–22 (1997).
doi: 10.1089/cmb.1997.4.1
pubmed: 9109034
McArdle, S. et al. Quantum computational chemistry. Rev. Mod. Phys. 92, 015003 (2020).
doi: 10.1103/RevModPhys.92.015003
Finnila, A. B. et al. Quantum annealing: A new method for minimizing multidimensional functions. Chem. Phys. Lett. 219, 343–348 (1994).
doi: 10.1016/0009-2614(94)00117-0
Xia, R. & Teng, B. & Sabre K. Electronic structure calculations and the Ising Hamiltonian. J. Phys. Chem. B 122, 3384–3395 (2017).
doi: 10.1021/acs.jpcb.7b10371
pubmed: 29099600
Lenstra, J. K., Rinnooy Kan, A. H. G. & Brucker, P. Complexity of machine scheduling problems. Ann. Discret. Math. 1, 343–362 (1977).
doi: 10.1016/S0167-5060(08)70743-X
Prasad, M. R., Biere, A. & Gupta, A. A survey of recent advances in SAT-based formal verification. Int. J. Softw. Tools Technol. Transf. 7, 156–173 (2005).
doi: 10.1007/s10009-004-0183-4
Glos, A., Krawiec, A. & Zimboras, Z. Space-efficient binary optimization for variational quantum computing. NPJ Quantum Inf. 8, 39 (2022).
doi: 10.1038/s41534-022-00546-y
Papadimitriou, C. & Steiglitz, K. Combinatorial Optimization (Dover Publications, 1998).
Krotov, D. & Hopfield, J. J. Dense associative memory for pattern recognition. 29 NIPS’16 (2016).
Hoover, B., Horng Chau, D., Strobelt, H. & Krotov, D. A universal abstraction for hierarchical Hopfield networks. NIPS’22 Workshop on The Symbiosis of Deep Learning and Differential Equations (2022).
Kosmatopoulos, E. B., Polycarpou, M. M., Christodoulou, M. A. & Ioannou, P. A. High-order neural network structures for identification of dynamical systems. IEEE Trans. Neural Netw. 6, 422–431 (1995).
doi: 10.1109/72.363477
pubmed: 18263324
Jordán, C. Calculus of Finite Differences. American Mathematical Soc. (1965).
Hoos, H. H. & Stutzle, T. Stochastic local search: Foundations and applications. (Elsevier 2004).
Selman, B., Kautz, H. A. & Cohen, B. Noise strategies for improving local search. Proc. AAAI-94 337–343 (1994).
Selman, B., Mitchell, D. & Levesque, H. Generating hard satisfiability problems. Artif. Intell. 81, 17–29 (1996).
doi: 10.1016/0004-3702(95)00045-3
Sheng, X. et al. Low‐conductance and multilevel CMOS‐integrated nanoscale oxide memristors. Adv. Electron. Mater. 5.9, 1800876 (2019).
doi: 10.1002/aelm.201800876
Froleyks, N. et al. SAT competition 2020. Artif. Intell. 301, 103572 (2021).
doi: 10.1016/j.artint.2021.103572
Hoos, H. SATLIB — Benchmark problems https://www.cs.ubc.ca/~hoos/SATLIB/benchm.html (2011).
Balyo, T. et al. Solver and benchmark descriptions. Proceedings of SAT Competition. http://hdl.handle.net/10138/318450 (2020).
Purdom, P. & Sabry, A. CNF Generator for Factoring Problems https://cgi.luddy.indiana.edu/~sabry/cnf.html (2018).
Strukov, D. B. & Likharev, K. K. CMOL FPGA: A reconfigurable architecture for hybrid digital circuits with two-terminal nanodevices. IOP Nanotechnol. 16, 888 (2005).
doi: 10.1088/0957-4484/16/6/045
Boroumand, A. et al. Google workloads for consumer devices: Mitigating data movement bottlenecks. In Architectural Support for Programming Languages and Operating Systems (2018).
Bavandpour, M., Mahmoodi, M. R. & Strukov, D. B. aCortex: An energy-efficient multi-purpose mixed-signal inference accelerator. IEEE J. Explor. Solid State Comput. Devices Circuits 6, 98–106 (2020).
doi: 10.1109/JXCDC.2020.2999581
Inagaki, T. et al. A coherent Ising machine for 2000-node optimization problems. Science 354.6312, 603–606 (2016).
doi: 10.1126/science.aah4243
Willsch, D. et al. Benchmarking advantage and D-Wave 2000Q quantum annealers with exact cover problems. Quantum Inf. Process. 21.4, 141 (2022).
doi: 10.1007/s11128-022-03476-y
Aadit, N. A. et al. Massively parallel probabilistic computing with sparse Ising machines. Nat. Electron. 5.7, 460–468 (2022).
doi: 10.1038/s41928-022-00774-2
Park, S., Nam, J. W. & Gupta, S. K. HW-BCP: A custom hardware accelerator for SAT suitable for single chip implementation for large benchmarks. In Asia and South Pacific Design Automation Conference (2021).
Pedretti, G. et al. Zeroth and high-order logic with content addressable memories. In International Electron Devices Meeting (2023).
Xie, S. et al. Snap-SAT: A one-shot energy-performance-aware all-digital compute0in-memory solver for large-scale hard Boolean satisfiability problems. ISSCC’23 420-423 (2023).
Li, C. M., & Huang, W. Q. Diversification and determinism in local search for satisfiability. In Proceedings of Theory and Applications of Satisfiability Testing Conference. 158−172 (Springer Berlin Heidelberg, 2005).
Aramon, M. et al. Physics-inspired optimization for quadratic unconstrained problems using a digital annealer. Front. Phys. 7, 48 (2019).
doi: 10.3389/fphy.2019.00048
Li, C. et al. CMOS integrated nanoscale memristive crossbars for CNN and optimization acceleration. IMW’20 (2020).
Bhattacharya, T. Computing high-degree polynomial gradients in memory. tinish123/imc_hdGrad: v1.0.0. Zenodo https://doi.org/10.5281/zenodo.13508539 (2024).
Tseytin, G. S. On the complexity of derivation in propositional calculus. In Slisenko, A. O. (ed.) Studies in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics 115–125. Steklov Mathematical Institute (1970).