FPGA-Based Annealing Processor with Time-Division Multiplexing

An annealing processor based on the Ising model is a remarkable candidate for combinatorial optimization problems and it is superior to general von Neumann computers. CMOS-based implementations of the annealing processor are efficient and feasible based on current semiconductor technology. However, critical problems with annealing processors remain. There are few simulated spins and inflexibility in terms of implementable graph topology due to hardware constraints. A prior approach to overcoming these problems is to emulate a complicated graph on a simple and high-density spin array with so-called minor embedding, a spin duplication method based on graph theory. When a complicated graph is embedded on such hardware, numerous spins are consumed to represent high-degree spins by combining multiple low-degree spins. In addition to the number of spins, the quality of solutions decreases as a result of dummy strong connections between the duplicated spins. Thus, the approach cannot handle large-scale practical problems. This paper proposes a flexible and scalable hardware architecture with time-division multiplexing for massive spins and high-degree topologies. A target graph is separated and mapped onto multiple virtual planes, and each plane is subject to interleaved simulation with time-division processing. Therefore, the behavior of high-degree spins is efficiently emulated over time, so that no dummy strong connections are required, and the solution quality is accordingly improved. We implemented a prototype hardware design for FPGAs, and we evaluated the proposed method in a software-based annealing processor simulator. The results indicate that the method increased the spins that can be deployed. In addition, our time-division multiplexing architecture improved the solution quality and convergence time with reasonable resource consumption. key words: ising model, annealing processor, simulated annealing

基于伊辛模型的退火处理器是解决组合优化问题的杰出候选方案，并且优于通用的冯·诺依曼计算机。基于当前的半导体技术，退火处理器的CMOS实现是高效且可行的。然而，退火处理器仍然存在关键问题。由于硬件限制，模拟的自旋数量很少，并且在可实现的图拓扑结构方面缺乏灵活性。克服这些问题的一种先前方法是通过所谓的小图嵌入（一种基于图论的自旋复制方法）在简单且高密度的自旋阵列上模拟复杂的图。当复杂的图嵌入到此类硬件中时，需要消耗大量自旋，通过组合多个低度数自旋来表示高度数自旋。除了自旋数量之外，由于复制的自旋之间存在虚拟的强连接，解决方案的质量会下降。因此，这种方法无法处理大规模的实际问题。本文提出了一种灵活且可扩展的硬件架构，该架构采用时分复用技术来处理大量自旋和高度拓扑结构。将目标图分离并映射到多个虚拟平面上，并且每个平面通过时分处理进行交错模拟。因此，可以随着时间有效地模拟高度数自旋的行为，从而不需要虚拟的强连接，并且相应地提高了解决方案的质量。我们为FPGA实现了一个原型硬件设计，并在基于软件的退火处理器模拟器中对所提出的方法进行了评估。结果表明，该方法增加了可部署的自旋数量。此外，我们的时分复用架构在合理的资源消耗情况下提高了解决方案质量和收敛时间。 关键词：伊辛模型，退火处理器，模拟退火