Timing closure has taken center stage as the toughest challenge for today's deep-submicron designs. Subsequently, the problem of accurate timing verification has become more important than ever before. Designs have long been of the size and complexity that it's impractical to verify their timing prior to manufacturing using exhaustive circuit simulation. Instead, timing sign-off is based on static timing analysis (STA) which estimates the worst-case performance of the circuit independent of input patterns applied to it. STA does this by representing the circuit by a timing graph with nodes that represent the physical circuit nodes and weighted edges that represent the signal transmission between these nodes via signal delays weights. STA then finds the longest, or "critical" path in the circuit by computing the graph theoretical delay of the network.

The logical relationship between nodes is usually ignored, and the resultant delay is refered to as the topological delay of the network. In general we can afford to ignore the logic information because the topological delay gives a reasonably tight upper bound on the true maximum delay for well designed circuits. But the accuracy of this upper bound clearly depends on the accuracy of the models used in calculating the signal delays.

As close as we can get

In STA, transistor-level modeling is the closest we can get to device performance on silicon, and simulations performed with these models give the most accurate results. But these simulations are extremely time consuming and hence the behavior of devices is often abstracted to higher level logic gates or cells, especially for application specific integrated circuit (ASIC) design. The gates are pre-characterized by accurately simulating the gate behavior for different load scenarios and input combinations, and then storing the delays as a function of parameters like the load capacitance and the input transition time.

However, shrinking device geometries and dominant interconnect delays forced us to revisit this traditional approach in the early 90s. With the advent of deep-submicron technologies, gates were no longer driving purely capacitive loads in all cases, and long wires were characterized by distributed RC interconnect.

Since it's impossible to pre-characterize gates for all possible RC load combinations the gate delay had to be analyzed with an "effective capacitance" approximation of the load. In addition to the gate delay now being a function of an effective capacitance load, the long RC interconnect delays had to be represented separately in the timing graph. To compute the delay in an interconnect circuit comprised of hundreds of resistances and capacitances, model-order reduction techniques used dominant time-constant approximations to represent the associated transfer characteristics in simple analytic form. These changes brought on by long RC interconnect effects have had a significant impact on delay modeling and calculation, but the techniques and algorithms used for static timing analysis have continued to apply.

The coupling headache

Unfortunately, the impact of shrinking IC feature sizes doesn't end with large RC interconnect delays. As we pack ever-increasing processing power on a single chip, more and more gates have to be placed and interconnected within a smaller area. This leads to increased complexity of placement and routing, and in turn more routing congestion. In order to accommodate all these wires, the widths of the metal interconnect is continually being decreased, while more metal layers continue to be added. Since the resistance of the metal is inversely proportional to the width, to control the resistance (hence the RC interconnect delays within reasonable limits) there has been a trend toward changing the aspect ratios of the metal wire cross-sections.

Figure 1 - Troubling relationships.

As feature size decreases, coupling capacitance increases and ground capacitance decreases.

Basically, since width is shrinking, there has been a movement from thick and short wires to thin and tall wires to control resistance. This change in aspect ratio results in increased electrical interaction between adjacent wires. Electrically, this is modeled as a coupling capacitance between adjacent wires. In addition, with more metal interconnect layers on an IC, the distance from the higher metal layers to the substrate layers decreases, thereby decreasing the component of capacitance to ground (see Figure 1).

At first glance, this trend might seem relatively harmless, but a little analysis reveals the enormous problems that it can pose. During STA, we compute the delay of a particular path by starting from an input, traversing all the gates along the path until we reach a primary output, and summing up the delays. But when a driven interconnect path is strongly coupled to a neighboring line, is it possible to compute the gate delay as easily? We know that the charging and discharging of capacitances, either through transistors or metal resistances, is the primary contribution to delay in an integrated circuit. Computing this delay accurately is already challenging when a non-linear sourceýwhich is the electrical representation for a logic gateýis charging capacitances that are connected to ground through a network of resistances. With dominant capacitance coupling, however, the other end of the capacitances are now connected to interconnect lines for which the signals are varying unpredictably.

Clearly, it's naive to think that we can compute a fixed delay for a gate, and add the gate-delays to compute path-delay. This is what makes the problem of increasing coupling capacitance a challenging one to address in the context of static timing analysis. Now the delay-modeling problem and the algorithms for performing STA can no longer be independent of each other!

Knowing your neighbors

Consider a logic gate driving an interconnect line which is coupled to a few neighboring lines. Since we are interested in how the delay of the gate/line is "affected" by its neighbors, we usually refer to it as a "victim." The question that needs to be addressed is: "How does the presence of these victim lines change the way I have been doing STA?" We know that a significant number of inter-related effects determine this impact, so one might be inclined to break up the problem and understand the various aspects independently.

First, you can observe how close the victim and its neighbors are and if it's going to cause any difference at all in how the victim behaves. This requires you to quantify the impact of this closeness. Fortunately, you have extraction tools that will compute (within some reasonable amount of error) the coupling capacitance between the victim and it's neighbors. For each neighbor, the magnitude of coupling capacitance as a fraction of the total capacitance gives you an idea of whether you need to worry about the neighbor or not. Next you need to find out what these neighbors, which control the other ends of these capacitances, are doing. If they are all just idle, then there is no problem at all. You can conclude that these coupling capacitances are no different than the ones that are connected to ground. This isn't quite accurate since coupling to an idle line is not exactly like coupling to a perfect ground, but because of the total neighboring line capacitance is significantly larger than your single coupling capacitance, to first order it appears like a ground node.

However, the victim's neighbors won't sit idle all the time, and in fact may be undergoing wild switching activity. You need to find out if any neighbors are switching while the line being analyzed is switching.

But this isn't the final step to solving the problem. It's possible that some neighbors are switching, but in a manner that is completely irrelevant to the victim.

This happens if the victim has finished all its transitions before its neighbors switch, or if the victim will only undergo switching much later. In either case, the neighbors can be considered idle for purposes of computing the victim's delay.

So when does a switching neighbor affect the victim's delay? When the neighboring lines are either pumping or drawing current through the coupling capacitances into or from the victim line while it's switching. If the neighbors switch in the opposite direction to that of the victim, then they absorb current and hence increase the delay of the victim (see Figure 2). Alternatively, if the neighbor switches in the same direction, then the delay of the victim is decreased. Since the current through a capacitance depends on the rate of change of voltage, how fast the neighbors are switching is crucial. The faster they switch, the more impact they will have on the victim's delay.

Figure 2 - Delaying the increase

The delay of an inverter increases when a coupled neighbor is switching in the opposite direction.

From the above discussion, we can conclude that to determine the delay of the victim, at a minimum, we need to answer the following questions: Is the neighbor switching when the victim is switching? If yes, how fast is it switching?

The chicken-egg problem

However, we are missing an important point amidst all this discussion. Since it's impossible to simulate the circuit for all possible patterns, STA is performed independent of input patterns to the circuit. This implies that we can't claim to find out exact information about which lines are switching and at what times. Instead, what we have available is a range of possible switching times for a particular signal. This range is denoted by the earliest and latest arrival times for the particular signal. Usually in STA we know this information at the input of the victim and would like to find this for the neighbors. In order to be able to confidently claim something like "the neighbor can switch anytime between 1.2ns and 1.5ns," we need to accurately compute the delays of gates that lead to the neighbor. But these gates could be coupled to other neighbors, and so we'll need to analyze their neighbors, find their arrival times, and so on. The question remains as to whther or not this process ends somewhere.

Unfortunately, it's quite possible that the arrival times of the victim's neighbors may depend on the delay of the victim itself. Coupling can cause a "feedback loop" in a circuit even when there is no physical combinational loop. This causes a chicken-egg problem and it becomes impossible to propagate the victim signal forward during STA. Therefore we can no longer guarantee that we have the longest path, hence timing signoff prior to manufacturing is now questionable.

A couple of points are worth mentioning though. While the problems due to capacitive coupling have become more pronounced recently, designers have had to deal with this issue for the past several years. During this time STA has been used for timing signoff, and chips have been fabricated that work and meet timing. So what's the problem?

In the past, the usual approach has been to model the coupling capacitance as a capacitance to ground, scaled by a "Miller factor". This scaled value effectively represents what the victim "sees" as the capacitance that it should charge or discharge. Suppose the victim is charging a particular coupling capacitance while switching from 0 to Vdd. If the neighbor is switching in the opposite direction and at the same rate, then we can easily conclude that effectively the victim is charging a capacitance of twice the value as if it were connected to ground. The reason such a Miller factor approach is popular is because it allows us to continue to do STA with little or no modifications. The increased capacitance implies that the delay of the victim increases and it appears that we have captured the impact on the victim. However, we can easily see that if the rate of switching of the neighbor isn't the same as the victim, then this approach could be prone to large errors.

More importantly, research has proven that this "2x" approach isn't even an upper bound on the delay of the victim. Apart from the switching rate, other important factors such as the driver (gate) resistance and interconnect resistance of the victim are neglected in this approach.

A solution

Before we attempt to arrive at a solution, we have to clearly define what we are after. We have repeatedly stressed that STA performs input-pattern independent analysis, and hence the range of arrival times computed for each signal is over all possible patterns. Specifically, we can only claim that a particular signal can switch "at the earliest, 1.2ns" and "at the latest, 1.5ns ", for example. It's only logical that we would want to find similar bounds on the signal arrival times in the presence of coupling too.

Specifically, we have to find the earliest and latest arrival times for each signal in the circuit over all possible input arrival times and over all possible coupling interactions. The range of signal switching times is also referred to as "arrival time window" in STA parlance. The earliest and latest arrival time, along with the rate of switching (or slew of the signal) comprise an arrival time window. An example of arrival time windows is depicted in Figure 3. If we know the arrival time window at a neighbor, then we can determine whether or not it overlaps with those of the victim. It's precisely in determining these windows that we detect the chicken-egg problem.

One possible solution that we propose is to start with the worst-case assumption. By worst-case we mean the following: if the neighbor's timing window isn't available, assume that the window is such that it can overlap with that of the victim. Since we don't know when this neighbor can switch, and will probably know that only later in the STA flow, we assume that this neighbor can cause maximum impact on the victim. Assuming that we have a way of computing this maximum impact, what does this mean to our STA? When we propagate our signal switching times (or arrival time windows, if you wish) forward, we are making pessimistic assumptions about the switching times. Going back to our statement about signal switching times, "the victim can switch between 1.2 ns and 1.5 ns" now means that no matter what neighbors switch at what time, these numbers are bounds on the actual switching times of the victim.

Perhaps the "actual" switching range is only between 1.3 ns and 1.4 ns.

Figure 3 - A window of opportunity.

Arrival time windows represent signal-switching times.

We should note that pessimistic assumptions can be used in the true sense of the phrase only for the late arrival times. We have observed earlier that neighbors can cause a decrease in victim delay if the switching is in the same direction. When we want to propagate the early arrival time, "pessimistic" would mean finding the earliest possible switching time, taking into account possible decrease in delays due to coupling. The early arrival times can have an impact of hold and race conditions for the circuit, and there STA bounds are just as important as those for the worst-case path delays in most cases.

In the nick of time

The arrival times calculated in this way might turn out to be overly pessimistic. Neighboring lines that we assumed can impact the victim delay, might in reality be temporally isolated from the victim. The solution we propose is to iteratively reduce this pessimism by performing additional runs of STA. During a second run, if we find that a neighbor doesn't overlap with the victim, then the delay of the victim reduces and hence the arrival time window at the victim output would "shrink." This is the central idea behind TACOýTiming Analysis with Coupling, an algorithm for capturing coupling effects within a static timing analysis tool.

We mentioned earlier that the solution we seek is to bound the arrival times. To find bounds on the early and late arrival times we need to first bound the delays of the victim in the case of a switching neighbor. In order to find the maximum impact that the neighbor's switching can have, we have to "align" the neighbor with respect to the victim. Thus, even if we know the timing window at the neighbor, it's important to fix the time when the neighbor has to switch so as to cause maximum impact on the victim. Without going into the details of the algorithms, we will simply note that these worst and best case switching delay calculations can be made with reasonable efficacy for RC coupled line problems.

Returning to the STA problem, since we started with worst-case assumptions (widest possible timing windows), we can guarantee that the timing windows can only shrink with subsequent runs of STA. Shrinking windows correspond to tighter bounds on the delays and arrival times that we seek. The advantage of such an approach is that if you feel your STA runs are sucking up a lot of run time, you can always stop at any stage and to produce bounds on the timing windows. In practice, we find that one never has to run STA more than twice, since it's the first iteration that incurs the majority of pessimism that is corrected in the second iteration.

So while the presence of dominant crosstalk capacitance is creating new design headaches, it remains business as usual for providing pre-manufacturing timing signoff using a modification of traditional static timing analysis.

Ravishankar Arunachalam is presently serving as a research assistant at Carnegie Mellon University working toward his PhD. His research interests include timing analysis, signal-integrity issues, delay modeling, and interconnect analysis.

Lawrence Pileggi is a professor of electrical and computer engineering at Carnegie Mellon University. Previously he taught at the University of Texas, Austin, and served as CTO at Monterey Design System. Prior to teaching, he worked for Westinghouse Research and Development, where he acquired two patents and was recognized with the company's engineering achievement award.

To voice an opinion on this or any other article in Integrated System Design, please e-mail your comments to sdean@cmp.com.