Improved Mapping Strategies for Integrated Oscillator-Based Ising Machine Networks

Masterarbeit

Traditional CMOS based logic computation struggles to find good solutions for optimization problems. A promising alternative approach is to exploit coupling between CMOS oscillators used in so called oscillator based Ising Machines (OIMs). The coupling between oscillators within these systems can be configured according to the optimization problem and the solution is represented by the settled oscillator phases. While the CMOS oscillator approach is still fully compatible with modern well-established CMOS technologies, it could solve optimization problems in a fraction of time compared to its digital counterparts.

Software-based implementations can easily adapt to any problem size and structure. A hardware approach like the OIMs are limited by the manufactured physical instances. They support only a fixed number of nodes with restricted connections between those. Hence, a mapping of any arbitrary optimization problem to the topology of the integrated circuit is needed. The mapping process itself should be as efficient as possible to maintain the speed advantage of the oscillator-based integrated implementation. The mapping itself is used for two purposes: First, widely used benchmark problems should be mapped on our current existing OIM platform to evaluate its performance and compare it with competing technologies. Secondly, a suitable network topology for the next chip iteration should be found. The topology should balance flexibility for mapping while keeping the overhead in the hardware as small as possible.

Task of the thesis is to improve the current mapping algorithms of a previous master thesis. It should support larger graph sizes, increase the success rate of mapping and potentially reduce the runtime. The current mapping process itself is relying on heuristic techniques and graph simplifications, which can be greatly improved and extended. While it is currently implemented in Matlab, a more performance-oriented language like C++ could be beneficial. Based on the improved mapping algorithm different network topologies should be investigated and compared. Practical examples and common benchmarks should be considered to propose promising network topologies with a good tradeoff between hardware complexity and problem coverage.

Tasks

• Improving the existing mapping algorithm while maintaining the flexibility of possible networks
• Investigating practical application and common benchmarks (e.g. GSet) to evaluate hardware requirements
• Evaluating problem coverage/limits and suggesting hardware topologies

Requirements

• Experience with Matlab
• C++ (or similar)
• Fundamental knowledge in graph theory is a plus