Hierarchical Cross-Entropy Optimization for Fast On-Chip Decap Budgeting
Decoupling capacitor (decap) has been widely used to effectively reduce dynamic power supply noise. Traditional decap budgeting algorithms usually explore the sensitivity-based nonlinear optimizations or Conjugate Gradient (CG) methods, which can be prohibitively expensive for large-scale decap budgeting problems and cannot be easily parallelized. In this paper, the authors propose a hierarchical cross-entropy based optimization technique which is more efficient and parallel-friendly. Cross-Entropy (CE) is an advanced optimization framework which explores the power of rare event probability theory and importance sampling. To achieve the high efficiency, a Sensitivity-guided Cross-Entropy (SCE) algorithm is introduced which integrates CE with a partitioning-based sampling strategy to effectively reduce the solution space in solving the large-scale decap budgeting problems.