All-to-all reconfigurability with sparse and higher-order Ising machines
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916443625357312 |
|---|---|
| author | Nikhar, Srijan Kannan, Sidharth Aadit, Navid Anjum Chowdhury, Shuvro Camsari, Kerem Y. |
| author_facet | Nikhar, Srijan Kannan, Sidharth Aadit, Navid Anjum Chowdhury, Shuvro Camsari, Kerem Y. |
| contents | Domain-specific hardware to solve computationally hard optimization problems has generated tremendous excitement. Here, we evaluate probabilistic bit (p-bit) based Ising Machines (IM) on the 3-regular 3-Exclusive OR Satisfiability (3R3X), as a representative hard optimization problem. We first introduce a multiplexed architecture that emulates all-to-all network functionality while maintaining highly parallelized chromatic Gibbs sampling. We implement this architecture in single Field-Programmable Gate Arrays (FPGA) and show that running the adaptive parallel tempering algorithm demonstrates competitive algorithmic and prefactor advantages over alternative IMs by D-Wave, Toshiba, and Fujitsu. We also implement higher-order interactions that lead to better prefactors without changing algorithmic scaling for the XORSAT problem. Even though FPGA implementations of p-bits are still not quite as fast as the best possible greedy algorithms accelerated on Graphics Processing Units (GPU), scaled magnetic versions of p-bit IMs could lead to orders of magnitude improvements over the state of the art for generic optimization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_08748 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | All-to-all reconfigurability with sparse and higher-order Ising machines Nikhar, Srijan Kannan, Sidharth Aadit, Navid Anjum Chowdhury, Shuvro Camsari, Kerem Y. Distributed, Parallel, and Cluster Computing Emerging Technologies Neural and Evolutionary Computing Quantum Physics Domain-specific hardware to solve computationally hard optimization problems has generated tremendous excitement. Here, we evaluate probabilistic bit (p-bit) based Ising Machines (IM) on the 3-regular 3-Exclusive OR Satisfiability (3R3X), as a representative hard optimization problem. We first introduce a multiplexed architecture that emulates all-to-all network functionality while maintaining highly parallelized chromatic Gibbs sampling. We implement this architecture in single Field-Programmable Gate Arrays (FPGA) and show that running the adaptive parallel tempering algorithm demonstrates competitive algorithmic and prefactor advantages over alternative IMs by D-Wave, Toshiba, and Fujitsu. We also implement higher-order interactions that lead to better prefactors without changing algorithmic scaling for the XORSAT problem. Even though FPGA implementations of p-bits are still not quite as fast as the best possible greedy algorithms accelerated on Graphics Processing Units (GPU), scaled magnetic versions of p-bit IMs could lead to orders of magnitude improvements over the state of the art for generic optimization. |
| title | All-to-all reconfigurability with sparse and higher-order Ising machines |
| topic | Distributed, Parallel, and Cluster Computing Emerging Technologies Neural and Evolutionary Computing Quantum Physics |
| url | https://arxiv.org/abs/2312.08748 |