Parallel hierarchical cross entropy optimization for on-chip decap budgeting

Xueqian Zhao, Yonghe Guo, Zhuo Feng, Shiyan Hu
Department of Electrical and Computer Engineering Michigan Technological University, Houghton, MI 49931
47th ACM/IEEE Design Automation Conference (DAC), 2010


   title={Parallel hierarchical cross entropy optimization for on-chip decap budgeting},

   author={Zhao, X. and Guo, Y. and Feng, Z. and Hu, S.},

   booktitle={Proceedings of the 47th Design Automation Conference},





Download Download (PDF)   View View   Source Source   



Decoupling capacitor (decap) placement has been widely adopted as an effective way to suppress dynamic power supply noise. Traditional decap budgeting algorithms usually explore the sensitivity-based nonlinear optimizations or conjugate gradient methods, which can be prohibitively expensive for large-scale decap budgeting problems. We present a hierarchical cross entropy (CE) optimization technique for solving the decap budgeting problem. CE is an advanced optimization framework which explores the power of rare-event probability theory and importance sampling. To achieve high efficiency, a sensitivity-guided cross entropy (SCE) algorithm is proposed which integrates CE with a partitioning-based sampling strategy to effectively reduce the dimensionality in solving the large scale decap budgeting problems. Extensive experiments on industrial power grid benchmarks show that the proposed SCE method converges 2X faster than the prior methods and 10X faster than the standard CE method, while gaining up to 25% improvement on power grid supply noise. Importantly, the proposed SCE algorithm is parallel-friendly since the simulation samples of each SCE iteration can be independently obtained in parallel. We obtain up to 1.9X speedup when running the SCE decap budgeting algorithm on a dual-core-dual-GPU system.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: