A Fast Graph Minor Embedding Heuristic for Oscillator Based Ising Machines

The demand for high-efficient computing power is constantly increasing. While digital CMOS designs are dom-inating, more research is focusing on novel computing ar-chitectures. Recently, so-called Oscillator-based Ising Machines (OIMs) have become a promising computing approach, which can solve optimization problems using configurable coupling between oscillators. OIMs are based on well-established CMOS silicon technologies and can even be integrated with a processor as hard-ware accelerators. Similarly to quantum computing, OIMs solve graph problems by directly representing them in their hardware. Consequently, the nodes and edges of a problem graph must be mapped to the available hardware-specific network. Since such graph embedding is required before every computation, it has a crucial impact on performance. We propose a heuristic embedding algorithm to transform quickly and efficiently an input problem onto a target hardware. The heuristic is optimized for OIM systems and supports various hardware topologies including routing channels. Using the heuristic algorithm, we analyze different hardware topologies to further improve OIM designs.