AGD: Analytic Gradient Descent for Discrete Optimization in EDA and its Use to Gate Sizing

In electronic design automation (EDA), simulation models are often non-differentiable, and many design choices are discrete. As a result, greedy optimization methods based on numerical gradients are widely used, although they often lead to suboptimal solutions. In contrast, analytical methods may provide better solutions but require significant research effort. Reinforcement learning (RL) has been employed to address this problem; however, RL also suffers from notorious sample inefficiency, which is exaggerated in EDA because data sampling in EDA is very expensive due to slow simulations. This paper proposes an alternative to RL for EDA, namely analytic gradient descent (AGD). Our method starts with a differentiable performance model, which can be either a learned surrogate or a static model. It then applies transformations similar to Shannon decomposition for each design variable in the performance model. Finally, one design option for each variable is selected using a one-hot variable, which is trained via a straight-through estimator (STE) through gradient descent. We demonstrate AGD on the well-known gate sizing problem using both a learned surrogate and a static model across 20 industrial benchmark circuits. Our experimental results show that the proposed method can outperform a several-decade-old commercial tool in the gate sizing task for 19 out of the 20 circuits.