This paper is about overcoming the fundamental difficulty of sequential updating by combining algorithmic and architectural ideas to build a sparse Ising Machine (sIM) for solving combinatorial optimization and probabilistic sampling problems. The sIM in this paper is based on a Field Programmable Gate Array (FPGA) implementation however the architecture is general and it can have different implementations. The sIM achieves near-ideal parallelism for MCMC sampling as long as the interconnection matrix \(J\)  is sparse. A key feature of our framework is in its generality: we first show that any optimization function can be efficiently represented as a sparse (but irregular) graph through principles of invertible logic [1]}, [2]}. We then outline techniques for further sparsification using additional nodes without any approximation. Next, we develop a massively parallel architecture to implement Eq. (REF )-(REF ), exploiting the sparsity of the graph, where the graph is defined by \(J\) . This is achieved by using multiple phase shifted clocks
controlling the activation of probabilistic bits (p-bits) (Eq. (REF )). The p-bits are interconnected through a multiply-accumulate (MAC) unit (Eq. (REF )) (see Supplementary Fig. REF c for the architecture). This architecture can be considered to be a low level hardware-level implementation of chromatic Gibbs sampling [3]} where large blocks of conditionally independent nodes are updated in parallel. For this sampling to be exact, the MAC must finish its computation before the next color block is updated. An unexpected finding however is even when color blocks are updated before the MAC operation is completed, the network is often able to find exact ground states in model optimization problems. This inexact Gibbs sampling approach is reminiscent of the Hogwild!-Gibbs algorithm [4]} and we show how this overclocking idea can lead to further advantages.
