Computing architecture to perform approximated simulated annealing for Ising models
Computing architecture to perform approximated simulated annealing for Ising models
复制标题
对伊辛模型执行近似模拟退火的计算架构
DOI：
10.1109/icrc.2016.7738673
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
M. Yamaoka
中科院分区：
文献类型：
--
作者：
Takuya Okuyama;C. Yoshimura;Masato Hayashi;M. Yamaoka
在不久的将来，解决组合优化问题的技术将在各个领域变得重要，并且需要大量的计算能力。然而，由于半导体微缩的结束，冯·诺依曼架构的性能增长将会放缓。为了解决这个问题，提出了一种计算架构，将优化问题映射到伊辛模型的基态搜索。作者在 CMOS 电路中实现了该架构，该架构通过受 SA 启发的电路操作找到基态。该架构采用了使用多数函数的修改算法来简化电路。尽管功率效率估计比 CPU 高 1800 倍，但这种修改会降低解决方案的质量，因为它打破了详细的平衡条件。本文提出了一种对 Ising 模型进行近似 SA 的计算架构。该架构通过利用具有随机处理输入的多数投票电路的输出的行为近似符合格劳伯动力学这一事实来满足该条件。仿真表明，所提出的架构的解决方案质量与 SA 的解决方案质量一样好。我们的架构可以实现节能，因为晶体管数量的增长率低于 42%。
In the near future, the techniques to solve combinatorial optimization problems will become important in various fields and require large computing power. However, the performance growth of von Neumann architecture will slow down due to the end of semiconductor scaling. To resolve this problem, a computing architecture is proposed that maps the optimization problems to the ground state search of Ising models. The authors implemented the architecture, which finds the ground state by circuit operations inspired by SA, in CMOS circuits. The architecture adopts a modified algorithm using a majority function to simplify circuits. Though the power efficiency can be estimated to be 1800 times higher than that of a CPU, the modification deteriorates solution quality because it breaks the detailed balance condition. This paper presents a computing architecture that performs SA for Ising models approximately. The architecture satisfies the condition by utilizing the fact that the output of the majority voter circuit with stochastically processed inputs approximately behaves in accordance with the Glauber dynamics. Simulations demonstrate that solution quality of the proposed architecture is as good as that of SA. Our architecture can be power-efficient because the rate of increase in the number of transistors is less than 42%.
影响因子：
3.8
作者：
Utsunomiya, Shoko;Takata, Kenta;Yamamoto, Yoshihisa
通讯作者：
Yamamoto, Yoshihisa