HO-FPIA: High-Order Field-Programmable Ising Arrays with In-Memory Computing
Tinish Bhattacharya, George Higgins Hutchinson, Giacomo Pedretti, Dmitri B. Strukov · 2024
High Order Ising Machines (HOIMs) are a generalization of the Ising Machine framework that can solve hard combinatorial optimization problems with higher order ($k> 2$) polynomial objective functions. The area cost of a dedicated High Order Ising Machine hardware using a single In-Memory Computing (IMC) crossbar array has been shown to scale linearly with the number of variables and monomials in the Ising Hamiltonian. However, an efficient hardware implementation for large-scale problems requiring multiple crossbar arrays is lacking and thanks to the inherent sparsity in such problems, there remains significant room for further area reduction. Here, we present a Field Programmable Gate Array (FPGA)-inspired architecture for implementing large-scale High Order Ising Machines where cluster-based logic blocks are replaced by IMC-cores that are present as “islands” in a “sea” of programmable routing fabric comprising of interconnects, switches, and connection blocks. Each IMC-core comprises of pair of locally interconnected crossbar arrays for computing high-order polynomial gradients crucial to the Ising Machine's operation. We adapted an open-source FPGA pack-place-route tool to optimize sparsity and fan-in-aware packing of large problems into multiple IMC-cores and model routing overhead. Modeling results of benchmark problems for the developed architecture show up to 116x area improvement and faster operation than a baseline approach and 43x area improvement over a similarly tiled Second Order Ising Machine implementation of the same problem. Crude estimates suggest at least an order of magnitude faster and more energy efficient operation compared to other architectures when the target optimization problems are natively high order.