.png){kind=icon}
.png){kind=icon}
Return
Accelerating multiple patterning lithography layout decomposition with a stochastic analog Boolean satisfiability solver
.png){kind=icon}
PRE
AI
DOI：10.1116/6.0004876.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
stochastic analog SAT solver
multiple patterning lithography
layout decomposition
graph-coloring problem
Boolean satisfiability
Journal
J
IF:
1.2
Papers:
103
Citations:
0