Enumerating the top-k aggressors set in Delay Noise Analysis


Primary Contact

Ravikishore Gandikota    gravkis@umich.edu

Current delay noise analysis methods consider the impact of an arbitrarily large number of aggressor on the circuit delay. While this results in a pessimistic analysis, it provides little information to the designer about those aggressor nets which are most important to fix, in order to alleviate the delay noise problem. However, information about the sets of aggressors that contribute most strongly to delay noise is necessary to guide designers while fixing delay noise problems. 

In this project, we present a new noise analysis algorithm that computes the “top-k” delay aggressors in a design. We first show that this set of k aggressor is non-trivial to compute, since we must not only consider the aggressors that directly coupled to a victim net, but must also consider the propagation of delay noise and the mutual impact of delay noise on the timing windows and vice versa. A brute-force enumeration has exponential runtime and can be only be applied to small designs. In this research effort, we proposed a novel algorithm which uses two key techniques to greatly reduce the runtime complexity: first, we modeled the propagation of delay noise from a victim net to its fanout net using a so-called “pseudo aggressor”, which significantly simplifying the problem formulation.  Second, we defined a dominance property for aggressor sets, which imposes a partial ordering on the aggressor sets and allows an effective pruning of the enumeration space. The proposed algorithm was implemented and its effectiveness was demonstrated on benchmark circuits in 130nm technology.


Top-k Aggressors Sets in Delay Noise Analysis

Ravikishore Gandikota, Kaviraj Chopra, David Blaauw, Dennis Sylvester, Murat Becer, “Top-k Aggressors Sets in Delay Noise Analysis,” ACM/IEEE Design Automation Conference (DAC), June 2007  ©IEEE