Worst Case Noise Prediction With Nonzero Current Transition Times for Power Grid Planning

In this paper, we propose a novel method for power distribution network verification at early design stages. This approach predicts the worst case noise of on-chip power grids with multiple current sources subjected to a set of hierarchical constraints. The current constraints not only define bounds for current magnitudes, but also consider nonzero current transition times that makes the prediction of worst case noise more realistic. Under the novel current constraints, a dynamic programming algorithm is introduced to generate the worst case current sources based on the impulse responses of the power grid. The algorithm is accelerated by a modified Knuth-Yao quadrangle inequality speedup method, which reduces the time complexity from O(s²m) to O(smlogs), where s is the number of discretized current values and m is the total number of zero-crossing points of the current sources. Experimental results show that our approach not only efficiently predicts realistic worst case noise of on-chip power grids, but also correlates the frequency-domain resonance effects with the time-domain noise behavior.