Universal Pre-Calculating Structure: Reducing Complexity of Ising Chips with Arbitrary Connectivity

Combinatorial optimization problems widely exist in real-world application fields, such as intelligence computation. Solving combinatorial optimization problems is a great challenge for Von Neumann-architecture computers. Alternatively, the Ising chip is a promising solution for combinatorial optimization problems. However, the complexity of the next-spin calculation module greatly increase the hardware cost of the Ising chip. In this paper, we propose universal pre-calculating structures to simplify the next-spin calculating module for the Ising chip with arbitrary connectivity ranging from local to full connectivity. We establish a cost model to provide 1) fast and precise evaluation of hardware cost, and 2) guidelines to select the most suitable structure towards a certain design target. The hardware cost evaluation on FPGA agrees well with our cost model, and shows that our pre-calculating structure can reduce the total cost of Ising chips by 20%.