Event

Name: Mingju Liu

Committee:
Professor Cunxi Yu, Chair/Advisor
Professor Gang Qu
Professor Kaiqing Zhang
Professor Ang Li
Professor David Mount, Dean's Representative

Date/time: Wednesday, November 4 at 2:00 PM – 4:00 PM

Location:   AVW-1146

Title: Sampling-Opt: Bridging Differentiable Learning and Combinatorial Optimization For Next-Generation EDA

Abstract: Combinatorial optimization is central to Electronic Design Automation (EDA), including scheduling, technology mapping, and Boolean reasoning. Exact solvers can certify optimal solutions, but large instances often require substantial search. Practical design flows therefore need methods that find high-quality discrete decisions within limited computational budgets.

 

This dissertation develops Sampling-Opt, a sampling-based optimization methodology that combines direct differentiable search with reward-guided exploration. Differentiable combinatorial scheduling uses Gumbel--Softmax sampling and constraint-aware construction to optimize discrete schedules through gradient descent. A hybrid CPU--GPU extension extracts confidence-based partial assignments as nonbinding warm starts for exact integer linear programming solvers. DiffMaxSAT extends differentiable GPU guidance to weighted partial maximum satisfiability through a hierarchical hard/soft loss, phase initialization, and soft-clause guidance. These differentiable methods are training-free and dataset-free: categorical decision parameters are optimized for each problem instance without fitting a predictive model across instances.

 

MapTune addresses a complementary setting in which the evaluator is an existing synthesis tool. It uses reinforcement learning to guide standard-cell library selection from technology-mapping feedback. The integrated study covers multiple technologies, mapping objectives, commercial synthesis, and cell-utilization behavior, showing how library choices can improve mapped outcomes without modifying the mapper itself.

 

Two application case studies extend these ideas toward industrial design flows. Global-skew optimization adapts constrained differentiable sampling to reduce modeled peak current while preserving baseline setup-timing metrics. Across synthetic benchmarks from 200 to 20,000 sinks, approximately 94--98% of the eventual mean peak-current reduction is obtained within the first 10 seconds. The advantage is strongest on the larger instances: the differentiable method finds lower final peaks than the tested CPU HiGHS configuration on all six cases with 5,000 or 20,000 sinks. At 20,000 sinks, peak reductions reach 20.2--24.0% within the 300-second solve budget. Physical-aware library expansion adapts MapTune to selectively re-enable cells excluded by a preset flow. Using Cadence Genus with physical context from Cadence Innovus, bandit-guided exploration improves the recorded aggregate timing--power reward at all three sandbox effort levels. Together, these studies demonstrate how adaptive sampling can supply useful candidates to established solvers and EDA tools, with particular value for rapid exploration of large discrete search spaces.