IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 2011 · 12 citations · 14 references
EngineeringComputer EngineeringComputer ScienceDesign OptimizationOptimizationParallel ComputingHardware AccelerationLow-noise Circuit DesignLow-power Digital Circuit DesignPower ManagementEntropy-based OptimizationImportance SamplingLatin Hypercube SamplingOn-chip DecouplingPower Supply NoiseSolution Space DesignSolution Space ExplorationSupply Noise Reduction
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.
14
A Tutorial on the Cross-Entropy Method
Pieter-Tjerk de Boer, Dirk P. Kroese, Shie Mannor et al. · Annals of Operations Research · 2005 · 3K citations · Full text