2025/10/30 by Ting-Hao Hsu, Himaddri Roy, Mayank Palaria +8 · 1 voice
Engineering · Computer Science · #VLSI and FPGA Design Techniques #Advancements in Photolithography Techniques #Embedded Systems Design Techniques
paper · doi:10.1116/6.0004876
openalex publication_date 2025/10/30 · openalex created_date 2025/10/30 · openalex updated_date 2026/06/26
This work presents a stochastic analog SAT solver to address the computational bottleneck in multiple patterning lithography layout decomposition. The decomposition task is modeled as a graph-coloring problem and transformed into a Boolean satisfiability (SAT) instance solvable by the analog solver that we invented. Leveraging the inherent parallelism of a programmable crossbar array and stochastic perturbations, the solver rapidly converges to valid solutions. The prototype achieves over 100-fold speedup compared to conventional digital SAT solvers and demonstrates near-linear scalability with increasing layout size. These results highlight the effectiveness of analog computing for solving NP-complete problems in very large-scale integrated design automation.