Integrated Circuits and Systems >

2025 , Vol. 2 >Issue 1: 22 - 27

DOI: https://doi.org/10.23919/ICS.2025.3553464

Special Issue Papers

An Area-Efficient Ising Machine Combining Parallel Tempering and Stochastic Cellular Automata

  • YANG ZHANG ,
  • LONGYUAN KANG ,
  • XIANGRUI WANG ,
  • ENYI YAO
Expand
  • School of Microelectronics, South China University of Technology, Guangzhou 511442, China
ENYI YAO (e-mail: ).

ENYI YAO (Member, IEEE)

Received date: 2024-12-31

  Revised date: 2025-02-27

  Accepted date: 2025-03-16

  Online published: 2025-10-22

Supported by

Guangdong Basic and Applied Basic Research Foundation under Grant(2022A1515110045)

Guangdong Basic and Applied Basic Research Foundation under Grant(2023A1515011241)

GJYC program of Guangzhou under Grant(2024D03J0006)

Fold

Abstract

As a potential solver for combinatorial optimization problems (COPs), the convergence speed and accuracy of Ising machines still have room to be improved at the level of algorithm and architecture design. In this paper, a novel parallel stochastic cellular automata tempering (PSCAT) algorithm is proposed, which combines the high parallel efficiency of stochastic cellular automata annealing (SCA) with the more balanced Monte Carlo sampling of parallel tempering (PT), to enhance the performance of fully-connected Ising machines. To achieve an area-efficient hardware design, a modified temperature exchange probability is applied to reduce the number of replicas and the utilization of the spin update module is improved by reducing the flip decision block. Additionally, the proposed coefficient access pattern effectively reduces memory overhead by sharing the weight matrix. The design prototype with 2,048 spins and 8 replicas is validated on FPGA. Using the K2000 max-cut problem as a benchmark, our design achieves a solution accuracy of 98.94% within 0.5 ms, which is higher than two state-of-the-art works.

Key words： Combinatorial optimization; fully-connected ising model; hardware acceleration; parallel tempering; stochastic cellular automata annealing

Cite this article

YANG ZHANG , LONGYUAN KANG , XIANGRUI WANG , ENYI YAO . An Area-Efficient Ising Machine Combining Parallel Tempering and Stochastic Cellular Automata[J]. Integrated Circuits and Systems, 2025 , 2(1) : 22 -27 . DOI: 10.23919/ICS.2025.3553464

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
X. Yang et al., “A review: Machine learning for combinatorial optimization problems in energy areas,” Algorithms, vol. 15, no. 6, p. 205, 2022.

[2]
N. Mohseni, P. L. McMahon, and T. Byrnes, “Ising machines as hardware solvers of combinatorial optimization problems,” Nature Rev. Phys., vol. 4, no. 6, pp. 363-379, 2022.

[3]
S. Tanaka, Y. Matsuda, and N. Togawa, “Theory of Ising machines and a common software platform for ising machines,” in Proc. 25th Asia South Pacific Des. Automat. Conf., 2020, pp. 659-666.

[4]
A. Lucas, “Ising formulations of many NP problems,” Front. Phys., vol. 2, p. 5, 2014.

[5]
H. Cilasun et al., “3SAT on an all-to-all-connected CMOS ising solver chip,” Sci. Rep., vol. 14, no. 1, 2024, Art. no. 10757.

[6]
D. Jiang, X.Wang, Z. Huang, Y. Yang, and E. Yao, “A network-on-chipbased annealing processing architecture for large-scale fully connected ising model,” IEEE Trans. Circuits Syst. I: Reg. Papers, vol. 70, no. 7, pp. 2868-2880, Jul. 2023.

[7]
Z. Huang, D. Jiang, X. Wang, and E. Yao, “An Ising model based annealing processor with 1024 fully-connected spins for combinatorial optimization problems,” IEEE Trans. Circuits Syst. II: Express Briefs, vol. 70, no. 8, pp. 3074-3078, Aug. 2023.

[8]
H. M. Waidyasooriya and M. Hariyama, “Temporal and spatial parallel processing of simulated quantum annealing on a multicore CPU,” J. Supercomput., vol. 78, no. 6, pp. 8733-8750, 2022.

[9]
K. Yamamoto et al., “STATICA: A 512-spin 0.25M-weight annealing processor with an all-spin-updates-at-once architecture for combinatorial optimization with complete spin-spin interactions,” IEEE J. Solid-State Circuits, vol. 56, no. 1, pp. 165-178, Jan. 2021.

[10]
B. H. Fukushima-Kimura, S. Handa, K. Kamakura, Y. Kamijima, K. Kawamura, and A. Sakai, “Mixing time and simulated annealing for the stochastic cellular automata,” J. Stat. Phys., vol. 190, no. 4, 2023, Art. no. 79.

[11]
K. Kawamura et al., “Amorphica: 4-replica 512 fully connected spin 336 MHz metamorphic annealer with programmable optimization strategy and compressed-spin-transfer multi-chip extension,” in Proc. IEEE Int. Solid-State Circuits Conf., 2023, pp. 42-44.

[12]
Y. Zhang et al., “An Isingmodel-based parallel tempering processing architecture for combinatorial optimization,” IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., vol. 43, no. 12, pp. 4572-4584, Dec. 2024.

[13]
D. Frenkel and B. Smit, Understanding Molecular Simulation: From Algorithms to Applications, 2nd ed. Amsterdam, The Netherlands: Elsevier, 1996.

[14]
Y. Zhang, X.Wang, and E. Yao, “An area-efficient Ising machine based on parallel stochastic cellular automata tempering,” in Proc. IEEE Int. Conf. Integr. Circuits Technol. Appl., 2024, pp. 120-121.

[15]
X. Wang, D. Jiang, Y. Zhang, H. Kang, and E. Yao, “A genuineequilibrium Monte Carlo sampling-based effective algorithm for fullyconnected ising models,” in Proc. IEEE Int. Conf. Integr. Circuits Technol. Appl., 2023, pp. 72-73.

[16]
S. G. Brush, “History of the lenz-Ising model,” Rev. Modern Phys., vol. 39, pp. 883-893, Oct. 1967.

[17]
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., vol. 21, no. 6, pp. 1087-1092, 1953.

[18]
S. Geman and D. Geman, “Stochastic relaxation, gibbs distributions, and the Bayesian restoration of images,” IEEE Trans. Pattern Anal. Mach. Intell., vol. PAMI-6, no. 6, pp. 721-741, Nov. 1984.

[19]
Y. F. Atchadé, G. O. Roberts, and J. S. Rosenthal, “Towards optimal scaling of metropolis-coupled Markov chain monte carlo,” Statist. Comput., vol. 21, pp. 555-568, 2011.

[20]
Simulated annealing for complete graphs, Github, Accessed:Dec. 15, 2024.[Online]. Available: https://github.com/hariby/SA-completegraph/tree/WK2000

[21]
Gset, Stanford University, Accessed: Jan. 20, 2024.[Online]. https://web.stanford.edu/∼yye/yyye/Gset/

[22]
H. Goto et al., “Combinatorial optimization by simulating adiabatic bifurcations in nonlinear hamiltonian systems,” Sci. Adv., vol. 5, Apr. 2019, Art. no. eaav2372.

Options
Outlines

/

〈 〉