Preprint / Version 1

From Hopfield Networks to Million-Net Routing: An Energy-Based Hybrid Router for Large-Scale Gate Array Global Routing

##article.authors##

  • John Y. Lu Lucid Systems

DOI:

https://doi.org/10.31224/8835

Keywords:

VLSI / physical circuit design, Electronic Design Automation (EDA), Hopfield networks, gate array global routing, energy-based optimization, neural optimization, exponentiated gradient descent, mirror descent, rip-up-and-reroute

Abstract

This paper revisits the classical Hopfield approach to gate-array global routing and presents an evolutionary progression of three neural routing architectures: the Traditional Hopfield Router, the Legacy Router, and the Hybrid Router. The Traditional router—a faithful reproduction of Algorithm 1 from the seminal 1991 work by Lu and Thomborson [1], [2];  it follows the original Hopfield-Tank energy-minimization paradigm and provides a convergent Lyapunov-based routing framework. The Legacy router replaces classical neuron dynamics with a row-wise softmax update that can be interpreted as inspired by Exponentiated Gradient Descent (EGD) on the probability simplex, yielding great runtime improvements while preserving energy-guided optimization. The Hybrid router further integrates congestion aware path generation, overflow-sensitive penalties, annealed softmax updates, and Rip-Up-and-Reroute (RRR) refinement to overcome congestion-induced local minima.

Theoretical analysis shows that the Traditional router follows classical Hopfield Lyapunov descent, while the Legacy and Hy brid routers can be interpreted through the framework of Mirror Descent and Exponentiated Gradient optimization [3], [4], [5], [6]. All three are implemented in a unified simulation framework. Experimental evaluation on a Dell OptiPlex 7010 with an Intel® Core™ i5-3470 processor and 14 GB RAM demonstrates significant performance improvements over classical Hopfield routing. Across 100 independent trials per randomly generated benchmark, the Hybrid router achieved 100% valid routing solutions with zero violations on all benchmark instances from 10,240 to 25,000 nets. Additional scalability benchmarks from 100,000 to 500,000 nets achieved 100% Hybrid validity across 100 trials, and further extreme-scale experiments routed instances containing up to three million nets with 100% validity. The results demonstrate that modern energy-based optimization techniques can remarkably extend the practical scalability of Hopfield inspired routing algorithms while preserving their fundamental optimization principles.

Downloads

Download data is not yet available.

Downloads

Posted

2026-11-18