Massively parallel probabilistic computing with sparse Ising machines
Massively parallel probabilistic computing with sparse Ising machines
复制标题
DOI：
10.1038/s41928-022-00774-2
复制
发表时间：
2022-06-02
影响因子：
34.3
通讯作者：
Camsari, Kerem Y.
中科院分区：
文献类型：
--
作者：
Aadit, Navid Anjum;Grimaldi, Andrea;Camsari, Kerem Y.
使用传统计算架构解决计算困难的问题通常速度缓慢且能源效率低下。量子计算可能有助于应对这些挑战，但它仍处于发展的早期阶段。一种受量子启发的替代方案是用经典硬件构建特定领域的架构。在此我们报道一种稀疏伊辛机，它实现了大规模并行性，其中每秒的翻转次数——关键的性能指标——与概率比特的数量呈线性比例关系。我们的稀疏伊辛机架构在现场可编程门阵列上进行了原型设计，比中央处理器上的标准吉布斯采样快多达六个数量级，并且与基于张量处理单元和图形处理单元的方法相比，采样速度提高了5 - 18倍。我们的稀疏伊辛机能够可靠地分解多达32位的半素数，并且在近似优化方面优于获奖的布尔可满足性求解器。此外，即使使用更快的时钟进行不精确采样，我们的架构也能找到正确的基态。我们的问题编码和稀疏化技术可应用于其他经典和量子伊辛机，并且我们的架构有可能使用模拟硅或纳米器件技术扩展到1000000个或更多的概率比特。稀疏化技术可用于创建在现场可编程门阵列上进行原型设计的伊辛机，这些伊辛机能够快速且高效地解决组合优化问题。
Solving computationally hard problems using conventional computing architectures is often slow and energetically inefficient. Quantum computing may help with these challenges, but it is still in the early stages of development. A quantum-inspired alternative is to build domain-specific architectures with classical hardware. Here we report a sparse Ising machine that achieves massive parallelism where the flips per second-the key figure of merit-scales linearly with the number of probabilistic bits. Our sparse Ising machine architecture, prototyped on a field-programmable gate array, is up to six orders of magnitude faster than standard Gibbs sampling on a central processing unit, and offers 5-18 times improvements in sampling speed compared with approaches based on tensor processing units and graphics processing units. Our sparse Ising machine can reliably factor semi-primes up to 32 bits and it outperforms competition-winning Boolean satisfiability solvers in approximate optimization. Moreover, our architecture can find the correct ground state, even when inexact sampling is made with faster clocks. Our problem encoding and sparsification techniques could be applied to other classical and quantum Ising machines, and our architecture could potentially be scaled to 1,000,000 or more p-bits using analogue silicon or nanodevice technologies.Sparsification techniques can be used to create Ising machines prototyped on field-programmable gate arrays that can quickly and efficiently solve combinatorial optimization problems.