Hierarchical cross-entropy optimization for fast on-chip decap budgeting

Xueqian Zhao, Yonghe Guo, Xiaodao Chen, Zhuo Feng, Shiyan Hu

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

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, we 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. Compared to improved CG method and conventional CE method, SCE with Latin hypercube sampling method (SCE-LHS) can provide 2 × speedups, while achieving up to 25% improvement on power supply noise. To further improve decap optimization solution quality, SCE with sequential importance sampling (SCE-SIS) method is also studied and implemented. Compared to SCE-LHS, in similar runtime, SCE-SIS can lead to 16.8% further reduction on the total power supply noise.

Original languageEnglish
Article number6046169
Pages (from-to)1610-1620
Number of pages11
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume30
Issue number11
DOIs
StatePublished - Nov 2011

Keywords

  • Adjoint sensitivity analysis
  • cross-entropy optimization
  • decoupling capacitor budgeting
  • power grid design
  • power supply noise

Fingerprint

Dive into the research topics of 'Hierarchical cross-entropy optimization for fast on-chip decap budgeting'. Together they form a unique fingerprint.

Cite this