Scalable Parallel Logic Resubstitution with Advanced Don’t Care Optimization

Resubstitution is a powerful logic optimization technique that restructures And-Inverter Graphs (AIGs) to achieve significant reductions in circuit area and delay. In this paper, we present a comprehensive, massively parallel algorithm for window-based k-resubstitution that exploits the computational power of GPUs while integrating advanced support for satisfiability and observability don’t cares (SDCs and ODCs). Our approach introduces adaptive, parallelized procedures for divisor collection, candidate evaluation, and network updates. To support don’t cares, we develop efficient, parallel-compatible algorithms for computing SDCs and ODCs, designed specifically for scalability. Experimental results on large benchmarks demonstrate that our GPU-based resubstitution achieves up to 63.7× speedup over state-of-the-art CPU-based tools, with comparable or improved area and delay. When integrating our resubstitution into a GPU-based optimization sequence resyn2rs, we observe a 43.0× speedup over ABC with a 0.9% reduction in area. Notably, our implicit exploitation of SDCs further improves optimization quality with minimal runtime overhead, maintaining a 35.0× speedup. Finally, our fully parallel ODC computation and incremental window expansion techniques significantly enhance scalability and performance for large circuits.