Enhancing K-Way Circuit Partitioning: A Deep Reinforcement Learning Methodology

Multiway circuit partitioning is a key combinatorial optimization problem that appears many times throughout the Very Large Scale Integration (VLSI) design workflow. However, as VLSI designs continue to grow in size and complexity in accordance with Moore’s law, current circuit-partitioning algorithms, which are mostly based on simple heuristics that become easily trapped in local minima, are increasingly hard-pressed to produce high-quality solutions in reasonable amounts of CPU runtime. To address this challenge, this paper proposes a novel circuit-partitioning algorithm that combines Deep Reinforcement Learning (DRL) with the popular Fiduccia-Mattheyses-Sanchis (FMS) circuit-partitioning heuristic. A DRL agent is trained to dynamically apply a perturbation function during the search in order to enable FMS escape local minima and to accelerate convergence towards higher-quality solutions. Experimental results obtained show significant improvements both in solution quality and CPU runtime.