Solving Max‐Cut Problem Using Spiking Boltzmann Machine Based on Neuromorphic Hardware with Phase Change Memory
Abstract Efficiently solving combinatorial optimization problems (COPs) such as Max‐Cut is challenging because the resources required increase exponentially with the problem size. This study proposes a hardware‐friendly method for solving the Max‐Cut problem by implementing a spiking neural network...
Saved in:
| Main Authors: | , , , , , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2024-12-01
|
| Series: | Advanced Science |
| Subjects: | |
| Online Access: | https://doi.org/10.1002/advs.202406433 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850247142404259840 |
|---|---|
| author | Yu Gyeong Kang Masatoshi Ishii Jaeweon Park Uicheol Shin Suyeon Jang Seongwon Yoon Mingi Kim Atsuya Okazaki Megumi Ito Akiyo Nomura Kohji Hosokawa Matthew BrightSky Sangbum Kim |
| author_facet | Yu Gyeong Kang Masatoshi Ishii Jaeweon Park Uicheol Shin Suyeon Jang Seongwon Yoon Mingi Kim Atsuya Okazaki Megumi Ito Akiyo Nomura Kohji Hosokawa Matthew BrightSky Sangbum Kim |
| author_sort | Yu Gyeong Kang |
| collection | DOAJ |
| description | Abstract Efficiently solving combinatorial optimization problems (COPs) such as Max‐Cut is challenging because the resources required increase exponentially with the problem size. This study proposes a hardware‐friendly method for solving the Max‐Cut problem by implementing a spiking neural network (SNN)‐based Boltzmann machine (BM) in neuromorphic hardware systems. To implement the hardware‐oriented version of the spiking Boltzmann machine (sBM), the stochastic dynamics of leaky integrate‐and‐fire (LIF) neurons with random walk noise are analyzed, and an innovative algorithm based on overlapping time windows is proposed. The simulation results demonstrate the effective convergence and high accuracy of the proposed method for large‐scale Max‐Cut problems. The proposed method is validated through successful hardware implementation on a 6‐transistor/2‐resistor (6T2R) neuromorphic chip with phase change memory (PCM) synapses. In addition, as an expansion of the algorithm, several annealing techniques and bias split methods are proposed to improve convergence, along with circuit design ideas for efficient evaluation of sampling convergence using cell arrays and spiking systems. Overall, the results of the proposed methods demonstrate the potential of energy‐efficient and hardware‐implementable approaches using SNNs to solve COPs. To the best of the author's knowledge, this is the first study to solve the Max‐Cut problem using an SNN neuromorphic hardware chip. |
| format | Article |
| id | doaj-art-5ad1ef6a3e054f138e290bdd7ad96a3d |
| institution | OA Journals |
| issn | 2198-3844 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | Wiley |
| record_format | Article |
| series | Advanced Science |
| spelling | doaj-art-5ad1ef6a3e054f138e290bdd7ad96a3d2025-08-20T01:59:00ZengWileyAdvanced Science2198-38442024-12-011146n/an/a10.1002/advs.202406433Solving Max‐Cut Problem Using Spiking Boltzmann Machine Based on Neuromorphic Hardware with Phase Change MemoryYu Gyeong Kang0Masatoshi Ishii1Jaeweon Park2Uicheol Shin3Suyeon Jang4Seongwon Yoon5Mingi Kim6Atsuya Okazaki7Megumi Ito8Akiyo Nomura9Kohji Hosokawa10Matthew BrightSky11Sangbum Kim12Department of Material Science & Engineering Inter‐University Semiconductor Research Center Research Institute of Advanced Materials Seoul National University Seoul 08826 Republic of KoreaIBM Research‐Tokyo Chuo‐ku Tokyo 103‐0015 JapanDepartment of Material Science & Engineering Inter‐University Semiconductor Research Center Research Institute of Advanced Materials Seoul National University Seoul 08826 Republic of KoreaDepartment of Material Science & Engineering Inter‐University Semiconductor Research Center Research Institute of Advanced Materials Seoul National University Seoul 08826 Republic of KoreaDepartment of Material Science & Engineering Inter‐University Semiconductor Research Center Research Institute of Advanced Materials Seoul National University Seoul 08826 Republic of KoreaDepartment of Material Science & Engineering Inter‐University Semiconductor Research Center Research Institute of Advanced Materials Seoul National University Seoul 08826 Republic of KoreaDepartment of Material Science & Engineering Inter‐University Semiconductor Research Center Research Institute of Advanced Materials Seoul National University Seoul 08826 Republic of KoreaIBM Research‐Tokyo Chuo‐ku Tokyo 103‐0015 JapanIBM Research‐Tokyo Chuo‐ku Tokyo 103‐0015 JapanIBM Research‐Tokyo Chuo‐ku Tokyo 103‐0015 JapanIBM Research‐Tokyo Chuo‐ku Tokyo 103‐0015 JapanIBM Thomas J. Watson Research Center Yorktown Heights NY 10598 USADepartment of Material Science & Engineering Inter‐University Semiconductor Research Center Research Institute of Advanced Materials Seoul National University Seoul 08826 Republic of KoreaAbstract Efficiently solving combinatorial optimization problems (COPs) such as Max‐Cut is challenging because the resources required increase exponentially with the problem size. This study proposes a hardware‐friendly method for solving the Max‐Cut problem by implementing a spiking neural network (SNN)‐based Boltzmann machine (BM) in neuromorphic hardware systems. To implement the hardware‐oriented version of the spiking Boltzmann machine (sBM), the stochastic dynamics of leaky integrate‐and‐fire (LIF) neurons with random walk noise are analyzed, and an innovative algorithm based on overlapping time windows is proposed. The simulation results demonstrate the effective convergence and high accuracy of the proposed method for large‐scale Max‐Cut problems. The proposed method is validated through successful hardware implementation on a 6‐transistor/2‐resistor (6T2R) neuromorphic chip with phase change memory (PCM) synapses. In addition, as an expansion of the algorithm, several annealing techniques and bias split methods are proposed to improve convergence, along with circuit design ideas for efficient evaluation of sampling convergence using cell arrays and spiking systems. Overall, the results of the proposed methods demonstrate the potential of energy‐efficient and hardware‐implementable approaches using SNNs to solve COPs. To the best of the author's knowledge, this is the first study to solve the Max‐Cut problem using an SNN neuromorphic hardware chip.https://doi.org/10.1002/advs.202406433Boltzmann machinescombinatorial optimizationsleaky integrate‐and‐fire neuronsmax‐cut problemsneuromorphic hardwarespiking neural networks |
| spellingShingle | Yu Gyeong Kang Masatoshi Ishii Jaeweon Park Uicheol Shin Suyeon Jang Seongwon Yoon Mingi Kim Atsuya Okazaki Megumi Ito Akiyo Nomura Kohji Hosokawa Matthew BrightSky Sangbum Kim Solving Max‐Cut Problem Using Spiking Boltzmann Machine Based on Neuromorphic Hardware with Phase Change Memory Advanced Science Boltzmann machines combinatorial optimizations leaky integrate‐and‐fire neurons max‐cut problems neuromorphic hardware spiking neural networks |
| title | Solving Max‐Cut Problem Using Spiking Boltzmann Machine Based on Neuromorphic Hardware with Phase Change Memory |
| title_full | Solving Max‐Cut Problem Using Spiking Boltzmann Machine Based on Neuromorphic Hardware with Phase Change Memory |
| title_fullStr | Solving Max‐Cut Problem Using Spiking Boltzmann Machine Based on Neuromorphic Hardware with Phase Change Memory |
| title_full_unstemmed | Solving Max‐Cut Problem Using Spiking Boltzmann Machine Based on Neuromorphic Hardware with Phase Change Memory |
| title_short | Solving Max‐Cut Problem Using Spiking Boltzmann Machine Based on Neuromorphic Hardware with Phase Change Memory |
| title_sort | solving max cut problem using spiking boltzmann machine based on neuromorphic hardware with phase change memory |
| topic | Boltzmann machines combinatorial optimizations leaky integrate‐and‐fire neurons max‐cut problems neuromorphic hardware spiking neural networks |
| url | https://doi.org/10.1002/advs.202406433 |
| work_keys_str_mv | AT yugyeongkang solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT masatoshiishii solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT jaeweonpark solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT uicheolshin solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT suyeonjang solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT seongwonyoon solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT mingikim solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT atsuyaokazaki solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT megumiito solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT akiyonomura solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT kohjihosokawa solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT matthewbrightsky solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory AT sangbumkim solvingmaxcutproblemusingspikingboltzmannmachinebasedonneuromorphichardwarewithphasechangememory |