Graber, Markus Sebastian (2024)
Coupled Oscillator Networks for Solving Combinatorial Optimization Problems in CMOS Technology.
Technische Universität Darmstadt
doi: 10.26083/tuprints-00028812
Dissertation, Erstveröffentlichung, Verlagsversion

Kurzbeschreibung (Abstract)

Solving optimization problems is important across various domains but can be time-consuming and energy-intensive. For example, optimization is essential to find an optimal schedule for an airline or to manage resources in a complex supply chain. Unfortunately, many combinatorial optimization problems can be NP-complete, which causes the runtime to increase exponentially with the problem size. A new approach to compute such problems are Ising machines, which are specialized physical implementations dedicated to solving optimization problems in an Ising model form. Instead of classical processors based on digital logic circuits, they exploit other physical mechanisms for potentially more efficient computation. Coupled oscillator networks are a promising approach, because they naturally strive towards a state, which corresponds to the ground state of the Ising model. Therefore, they can solve optimization problems within their underlying phase dynamics.

This work focuses on implementing such coupled oscillator networks using complementary metal-oxide-semiconductor (CMOS) technology. The goal is to find near-optimal solutions for optimization problems, while being fast, energy-efficient, and compact. First, a behavioral model and a simulation approach for such large oscillator networks are proposed, which provides insight into the design and reduces the simulation time. Secondly, the design is discussed, which is based on 4-stage differential ring oscillators. The interaction between the oscillators is established by an active coupler circuit consisting of two differential stages. The coupling strength is determined by its bias current, which is provided by a 4-bit digital-to-analog converter. Additional circuits for the sub-harmonic injection locking, phase measurement, and frequency calibration are also considered. The assignment of the variables and coefficients of the optimization problems to the physical oscillators and couplers in the hardware is a time-consuming task. Hence, a flexible routing network is introduced, which can connect any oscillators across the chip on demand. Two chip generations were fabricated. The second generation has a total of 1,440 oscillators and 11,724 couplers with 4-bit weight resolution and is implemented on 4.6 mm² using a 28 nm technology node.

Thirdly, a comprehensive experimental analysis of the presented chips shows that selecting the right coupling strength and sub-harmonic injection strength is important to achieve the best performance. Optimization problems are solved by the chip within 950 ns and reach on average more than 94% of the optimal solution, while consuming 320 μW per oscillator node. However, random manufacturing mismatch is one of the main challenges of such an analog implementation. While a calibration scheme compensates for the frequency variations of the oscillators, the individual variations in the coupling strength slightly alter the hardwarerepresented optimization problem.

Overall, the results highlight the fast and efficient computing capabilities of coupled oscillator networks. These networks tend to find solutions near the global optimum, but the analog computing principle limits the possible weight resolution that can be represented in hardware. They are particularly well-suited for applications that require rapid computations and can tolerate non-optimal solutions. Based on the presented design, such systems can be further scaled up to address even more challenging optimization problems.

Frage zum Eintrag

Redaktionelle Details anzeigen