NOTE: Figures (below) link to Adobe Acrobat (PDF) files. To get the entire article in one PDF, click the button on the left.

September 11, 1998

Elegant yet simple tools unmask timing flaws

Static-timing analysis can assure that logic designs are free of timing problems, but modern timing-analysis software often obscures the technique’s underlying simplicity. Read on to understand what’s atthe heart of timing-analysis tools and how to make the most of them.

Mark S Fredrickson, IBM Corp

Static-timing analysis detects timing problems in digital electronic designs. Though conceptually simple, timing-analysis tools can appear daunting. The following pages strip the software to its essentials and point out the most effective ways to use the tools. An example shows how you can use path- and block-oriented timing analysis to find a design's timing problems. You'll see how static-timing analysis applies to combinatorial and sequential logic, and you'll learn about real-life complications. Finally, some guidelines will help you to get started successfully using static-timing programs.

First, look at the problem: You're the engineer; how would you solve it? Visualize this: You are a greenhorn electrical engineer fresh from the EE farm and eager to make a good impression at company X, where you are the new member of team Y designing chip Z. Your new team leader wants to see how much you know and, naturally, wants to get real work out of you without delay. He gives you a chunk of combinatorial logic (Figure 1) and says, "This piece of logic is from the whatchamacallit-thingamabob in Z. Take a look at it. We need to know right away whether it has any timing problems and, if so, where and what the problems are."

So you take the schematic. You don't quite know where to start, but you don't want to risk looking dumb by asking questions. You go to your desk and ask yourself, "Hmmm…does this logic have any timing problems? What does it mean to have timing problems? Am I looking for glitch hazards or something else? Do timing problems mean signals are getting somewhere too late, or are they getting there too early? But what is too late? What is too early?" (It's OK to look dumb in front of yourself. Some really smart people do it all the time.)

You quickly realize that you need more information. For example, to determine if a signal is too late or too early, you need to know when the signal is supposed to arrive and when it actually arrives. With a little more thinking, you realize that to analyze the timing of the logic, you need at least the following additional information:

the arrival times of all signals at the inputs to the logic,
the required-arrival times of all signals at the outputs of the logic, and
the delays that gates impose on signals that they go through the logic.

The numbers are never exact

You go to your team leader and find out that the information you need is available, but the numbers are not exact. Your team leader tells you, "Well…the data signal on Input A should appear (either to rise or fall) sometime around 2.0 nsec. Specifically, a rising transition could occur between 2.1 and 2.4 nsec, and a falling transition could arrive between 2.0 and 2.2 nsec. The signal on Input B could be between…" and so on. You find out that the required-arrival times and even the gate delays are not single values but instead are ranges of possible values (Figure 2).

Armed with this new and vital information, you go back to your desk and start to analyze the logic for possible timing problems. Naturally, you begin by plugging in numbers. (That's what engineers do, right?) Let's say that Input A rises at 2.2 nsec, and S₀ rises at 1.5 nsec. What happens if we add NAND-gate delays of 0.7 nsec to signal A and 0.8 nsec to signal S₀? The NAND-gate output doesn't fall until the last input rises, so the first NAND gate output falls at maximum ((2.2+0.7), (1.5+0.8))=2.9 nsec. Now for the inverter, let's use a delay of 1 nsec….

Being a brilliant engineer, you quickly realize that plugging in numbers and simulating the behavior of the logic are not the way to go. There are so many possible combinations of arrival-time assertions and gate delays that it would be terribly tedious and slow to examine them all, even for a circuit of this size. But without looking at all of the possible sets of input conditions, how can you be sure that you've detected all of the timing problems?

You know there has to be an easier way. There may be thousands of combinations of assertions and gate delays, but there are only 11 paths through this logic. Is it possible to look at those paths one at a time and analyze them for timing problems? Starting with the simple path from Input A to Output X, you attempt to answer the question, "Could the signal on this path be too late?" To find out, you propagate the latest signal down that path and check at the output. During this analysis, you use the slowest possible gate delays and the latest possible input-arrival times to ensure that you are really analyzing the latest signal on the path:

Latest rise at A=2.4 nsec.
Latest fall at output of gate_2=2.4+0.9=3.3 nsec.
Latest rise at output of gate_4=3.3+0.9=4.2 nsec.
Latest rise at Output X=4.2 nsec.

You determine that the latest rising transition on Input A is not too late when it arrives at Output X. But how about the latest falling signal on Input A?

Latest fall at A=2.2 nsec.
Latest rise at output of gate_2=2.2+0.9=3.1 nsec.
Latest fall at output of gate_4=3.1+0.9=4.0 nsec.
Latest fall at Output X=4 nsec.

This transition also looks good. Now you want to know about the earliest rising transition on this path. For this analysis, you use the fastest possible gate delays and the earliest possible arrival times on the inputs.

Earliest rise at A=2.1 nsec.
Earliest fall at output of gate_2=2.1+0.5=2.6 nsec.
Earliest rise at output of gate_4=2.6+0.5=3.1 nsec.
Earliest rise at Output X=3.1 nsec.

Using this method, you can systematically analyze each path, checking to see whether the latest rising and falling signals are too late and checking to see if the earliest rising and falling signals are too early. This timing-analysis method is called "path enumeration," or "path-oriented static-timing analysis."

Analyze all paths at the same time

As you perform this analysis, you find that this approach works well. You are confident that you are catching any possible timing problems. But, as you analyze each path, you are also aware that many of the paths overlap parts of other paths, and you wonder if you could speed the process by analyzing all the paths at the same time. You grab the schematic and start doing a "late" analysis. You start by writing the latest rising and falling arrival times on each of the inputs. Then you propagate those arrival times from left to right, adding the slowest gate delays. The latest rising-arrival time at the output of each gate is the latest of all the rising-arrival times that come to that point. Similarly, the latest falling-arrival time at each gate output is the latest of all the falling-arrival times at that point. After propagating the latest-arrival times through the logic, you compare them against the expected-arrival times at the logic output (Figure 3).

This method of concurrently propagating all of the arrival times shows whether or not there are timing problems in the logic. Looking at the late-arrival times at Output Y, it is clear that there is at least one timing problem. The latest signal arrived at 6.6 nsec, but it was supposed to arrive at 6.0 nsec. You guess that the latest signal came from input S₀, but how can you be sure? Is there only one path that is too slow, or are there multiple slow paths? And which paths are they?

To identify the paths that are causing the late signal, it may help to determine which signals are late inside the logic, not just which ones are late at the outputs. If the latest signal must reach Output Y (the output of Gate 8) by 6.0 nsec, when must the latest signal reach the inputs of gate 8? By subtracting the slowest gate delays from the output required-arrival times, you see that the latest signal arriving on Input A of Gate 8 must arrive by 5.1 nsec, or the output will arrive late.

Using this idea, you can determine the required-arrival time at each point in the logic by propagating the required-arrival-time constraints backward through the logic and subtracting the slowest block delays. Whenever you have a choice of required-time constraints (that is, when multiple paths come together), you use the most restrictive (earliest) required-arrival time and further propagate it. This method works because a signal that meets the most restrictive of several required-arrival-time constraints meets all of the constraints. Figure 4 is an example of latest-required-arrival-time constraints propagated backwards through the logic.

I'm late; I'm late—for a very important date

Once you know the signal-arrival times and the required-arrival times at each point in the logic, you can easily determine which signals are late. Any signal that arrives after the required-arrival time is late. Naturally, signals that arrive before the required time are early. The amount by which a signal is early is called the "slack," or "margin." Slack is simply calculated as required-arrival time-arrival time. If the resulting slack is negative, the signal is late. Figure 5 shows the calculated late-slack values for the circuit in the example. Notice that the slack value is constant along the worst path through the logic.

This analysis shows that all of the timing problems caused by late signals are associated with the path from Input S₀ to Output Y. To correct these problems, you could make that path faster, speed the arrival of the data at Input S₀, or change the constraint on the output.

You can perform a similar analysis to determine if the logic has any problems with signals that arrive too early. You propagate the earliest arrival times forward and add them to the minimum gate delays. You then propagate the early required-time constraints backward, subtracting the minimum gate delays. Then you calculate the slack value as arrival time-required-arrival time. A negative slack value again indicates a timing problem. This approach is called "block-oriented static-timing analysis." It keeps the latest and earliest timing results with each block, regardless of the path they follow.

You take the results back to your team leader who is genuinely impressed. You have fixed the timing problem and saved the chip. You are rewarded with a big raise and a trip for two to Silicon Valley. (Whoa! Calm down! This is just visualization!)

Static-timing analysis—the basic idea

If you are like most EEs, you never even heard of static-timing analysis in school, even though the technique has been used for at least 15 years in industry to verify digital-chip designs (References 1 and 2). During those 15 years, the analysis programs have evolved in size and complexity, as have the designs on which engineers use the programs. However, the basic ideas of static-timing analysis have remained powerfully simple:

The goal: Simply stated, the goal of static-timing-analysis programs is to quickly find all of a design's possible timing problems (signals arriving too late or too early) or to prove that no such timing problems exist.

The basic premise: If the latest possible signal is not too late, none of the signals is too late; if the earliest possible signal is not too early, none of the signals is too early.

How it works: Static-timing-analysis programs analyze the latest and earliest possible signals on each logic path, regardless of what is happening on other paths. Given some logic gate, what is the latest that any signal can come out of this gate? Assume that you can set up the gating conditions so that the latest signal propagates through that gate. You do not attempt to simulate the gating conditions by stimulating the other gate inputs. Assuming that the latest signal can propagate through the block, the program can be completely independent of input patterns and the function of the logic gate. The program can quickly find all timing problems because it analyzes all paths. There is no risk of missing some paths because of missing input patterns, and time is not required to simulate all of the logic's possible behaviors.

Static-timing analysis versus delay simulation

Static-timing analysis differs from delay simulation, which uses input patterns to simulate the design's behavior. Delay simulation simulates the gating conditions on each gate and propagates signals through the gates based on the gate function. Delay simulation is also called dynamic-timing analysis.

Static-timing-analysis programs assume that the latest and earliest signals at each block can be propagated. Those signals are propagated without verifying that there is indeed some pattern of input stimuli that could activate those late or early signals. This assumption is the key to freeing static-timing analyzers from the need for input patterns. However, that freedom does not come without a cost.

By making this assumption, static-timing programs sometimes propagate a late or an early signal that, in reality, cannot exist in the real circuit because the gating conditions can't occur. Despite this shortcoming, the programs are more efficient than programs that simulate only those signals that can exist. If such an invalid signal arrives too late or too early at some downstream point, the program will report a timing problem. This well-known false-path problem is inherent in static-timing-analysis programs. In general, static-timing-analysis programs can report that certain signals are too late or too early, even if those signals can't really propagate through the logic.

Most static-analysis programs include some functions to help users get around the false-path problem by ignoring or "don't-caring" these paths. The program may leave it to the user to identify false paths, or the tool may use some form of Boolean reasoning or simulation to help the designer identify such paths. Usually, the tool ignores false paths unless the paths cause a false-timing problem. To quickly catch all timing problems, it's usually acceptable to report some problems that don't really exist. But missing a real timing problem is never acceptable. If you must err, do so on the side of safety .

As designs become larger and more complex, it is becoming impossible to use delay simulation to verify design timing. It is impractical to generate a set of input patterns that can completely simulate all of the design's possible timing relationships. Even if it were possible to get a complete pattern set, running such a simulation would take days, if not years. Using static-timing analysis and dealing with the false errors has proven to be much more efficient than delay simulation for the complete and safe analysis of the timing of complex electronic designs.

To perform static-timing analysis, you need at least a model of the logic, including:
all the points where the timing is of interest (inputs, outputs, latches, other gates) and
all the relationships between those points of interest (delays, setup constraints, hold constraints).

You also need the boundary conditions, including:

arrival-time and slew-rate assertions on logic inputs,
required-arrival-time constraints and capacitance loading on logic outputs, and
clock definition for sequential logic.

Combinatorial logic-analysis methods

Delay simulation: Delay simulation is not static-timing analysis; however, it is widely used for studying design timing and can be quite practical for small designs. Delay simulation stimulates an electronic design with input patterns and simulates the circuit's behavior. Because they model circuit delays, the programs let you check timing relationships, such as setup, hold, and pulse-width constraints. For delay simulation, you need a model of the logic and a set of input patterns. From the simulation, you get such information as an event trace (waveforms) and reports of timing errors.

Pros:

Can be used for both functional and timing verification.
More intuitive than static-timing analysis.

Cons:

Can miss timing and functional problems unless input-pattern set is complete. Generating a complete pattern set or determining the coverage that a pattern set offers can be difficult.
Impractical to use on large, complex designs because of the time required to generate and simulate the astronomical number of input patterns that complete coverage requires.

Path enumeration is static-timing analysis in which the latest and earliest signals propagate down each path separately, independent of all other paths. When the signals arrive at the end of the path, the software tests them against the constraints. A path can be from a primary input to a latch, from a latch to a latch, from a latch to a primary output, etc.

Pros:

Much faster than delay simulation, making the technique practical for large, complex designs.
Assures detection of all timing problems. Not dependent on input-pattern-set coverage.
Can be used to think about design timing in a path-oriented fashion, finding the worst paths, finding the fastest design frequency, etc. The slack value on each path is relative to the arrival time and constraints on that path.

Cons:

Subject to false-path problem.
Not optimal for integration with programs that need access to timing information about specific gates. Logic synthesis and tuning programs that operate on logic gates need to quickly retrieve the worst slack values at a given gate, without having to look through an analysis of all paths through that gate.

Block-oriented analysis is static-timing analysis in which you propagate the signal arrival times forward through the logic. You keep the latest- and earliest-possible arrival times on each gate input and output pin, regardless of which path propagated the times to that point. You always propagate the most restrictive required-arrival-time constraints backward through the logic. At each point in the logic, the timing-slack value is the difference between the required-arrival time and the actual-arrival time.

Pros:

Much faster than delay simulation, making the technique practical for large, complex designs.
Assures detection of all timing problems. Not dependent on input pattern-set coverage.
Can be used to reason about the timing of a design in a gate-oriented fashion, finding all gates that have negative slack, etc.
Well-suited for integration with logic synthesis and tuning programs that require gate-oriented slack values to perform operations on the logic gates.

Cons:

Subject to the false-path problem.
Block-oriented analysis produces less information about the design timing than path enumeration does. With block-oriented analysis, only the worst timing values are available for a given point in the logic. With path enumeration, information is available about each separate path through that point in the logic.

Sequential logic—divide and conquer

The preceding examples and discussion focus on the static analysis of combinatorial logic. This theory applies directly to the analysis of synchronous-sequential logic because most static-timing tools handle sequential logic by breaking it into chunks of combinatorial logic (or chunks that look like combinatorial logic for timing analysis). In other words, static-timing analysis of synchronous-sequential logic is performed by splitting the logic into combinatorial paths and applying static analysis to those paths.

To split sequential logic into combinatorial paths, divide the logic at latches, flip-flops, and other synchronizing elements. The resulting timing paths may extend from primary inputs to latches, from latches to latches, from latches to primary outputs, or directly from primary inputs to primary outputs. The programs analyze all of these combinatorial paths in parallel (Figure 6).

Remember that for static-timing analysis, arrival-times are needed at the beginning of each timing path, and required-arrival-time constraints are needed at the end of each path. For paths that begin or end at latches, the timing assertions and constraints come from the clocks.

Although the basic theory of static-timing analysis is simple, several complications arise when you apply the theory to real-life problems. Some timing-analysis programs deal with these challenges. Consider the following topics when you select a program.

Timing analyzers break sequential logic into combinatorial paths. The analyzers use the devices' clocks to automatically generate the timing assertions and constraints at the latches or flip-flops. The program must set up these path assertions so that all of the assertions on a path are in the same timing-reference frame.

For example, suppose you have a clock signal that rises at 0.0 nsec, launching a data signal from a flip-flop. And suppose that data signal follows some combinatorial path and gets clocked into another flip-flop by the same clock. It would not make sense to have a 0.0-nsec arrival time at the beginning of the path and also a 0.0-nsec required-arrival time at the end of the path. The timing program needs to know that at the end of the path, the data is captured one cycle after the launch. Both of the assertions on the path—the arrival time at the beginning of the path and the required-arrival time at the end of the path—need to be in the right time frame for the path timing.

By always defining the required-arrival time as the clock arrival-time+one cycle, a timing program can handle this simple example, which uses only one clock. The general case, in which there are multiple clocks and even clocks running at different frequencies, is not that simple. To correctly put the arrival times and required-arrival times into the same time frame, the timing program needs to know which clock launches the signal, which clock is captures the signal, and what the relationship is between those clocks.

Modeling process variation

The amount of delay for a specific logic gate is a function of many things, most notably the capacitance the gate is driving, the slew rates of the incoming signals, the voltage, the temperature, and the process parameters. Some of the factors that influence the delay can vary across the chip. The temperature at one spot on the chip may differ from that at some other spot. For that reason, the delay of two AND gates on the same chip can differ slightly. Trying to exactly model these delay differences can be complicated and expensive. Some analysis programs allow arrival times to include a bit of uncertainty. The uncertainty depends on the delay models and accumulates as a signal propagates along a path through the logic. A long logic path typically has more uncertainty than a shorter path. When signals from different paths come together and one signal is tested against the other, as in the clock and data signals at a latch, the uncertainty of those signals is taken into account, making the tests a little safer.

Timing programs that attempt to model process variations are subject to another complication. Typically, when signals from two paths come together and one is tested against the other, any uncertainty in those signals is used to make the test more pessimistic (safer). If, however, those two signals have part of their paths in common, the program should reduce or eliminate the modeled uncertainty for the common portion of the path. Determining what portion of the path is common to two signals and reducing the uncertainty for the common part can be complicated.

Splitting sequential logic apart at latches or storage elements automatically removes many loops. Sometimes, however, you may purposely model latches as transparent latches so that signals propagate through them as they would through combinatorial logic. (This approach can help in analyzing slack-stealing effects, for example.) At other times, loops may exist in combinatorial logic. Timing programs that cannot detect and break timing loops can get caught in infinite loops as arrival and required-arrival times propagate through the logic. Finding the best place to break timing loops and testing to assure that breaking the loops doesn't mask timing problems can be quite complex.

Much digital logic is designed so that data arrives at latches that are already transparent; thus, the signals do not have to wait for a clock. Such logic may also have feedback paths in which signals can feed back to latches that were formerly in the path, creating loops. When slack stealing occurs, just breaking a loop and analyzing it with a conservative test may be inadequate. You may have to analyze the loop and the input and output signals so that you can model the slack-stealing effect.

Guidelines for starting timing analysis

Before attempting to run the program, gather all the pertinent information—model, timing assertions, etc.
Make doubly sure that you have properly defined the clock signals. If the model does not properly describe the clock transitions, the bulk of the analysis may be incorrect or, worse yet, misleading. The clock signals are important because the timing analyzer uses them to generate the arrival and required-arrival times at the latches or other storage elements.
Make sure that you specify all input-arrival times, output required-arrival times, and clock-signal definitions to the same reference time (time zero).
When you assert signal-arrival times, make sure that minimum or early-arrival time values are less than (come before) maximum or late-time values.
As a general rule, do not mix clock and data signals or assertions on the same net. Clock signals should exist only in the clock tree. The program should allow modeling of clock-gating logic to keep gating-data signals from flowing into the clock tree.
When possible, avoid using "don't-care" directives. "Don't-cares" mask timing problems by causing timing analyses to ignore parts of the logic.
When the results of a timing analysis are available, first look at some latches or flip-flops to ensure that the clock signals are getting to those gates at the expected times. If the clocks are working incorrectly, you should probably discard the rest of the analysis.
Next, look at a histogram of the slack values for the design. See if any slack values are outside the expected range. (Slack values should generally be within ±1 cycle time of the time-zero value.) If any slack values are outside this range, the timing assertions, clock definitions, or other program controls are probably erroneous. Eliminate these problems before using the timing-analysis results to look for real timing problems.
When the analysis seems to be running properly and the analysis results are in the expected range, use the information from the analysis to find and eliminate design-timing problems. Design teams usually start by investigating the worst slack values.
Eliminate or justify all negative-slack values before you send the chip to be built.

Because of the pressure of rapidly increasing design complexity, submicron device dimensions, higher clock frequencies, ever-shorter design cycles, and a renewed focus on quality, design verification is a hot topic for chip designers and EDA providers. One of the hottest segments of this hot topic is static-timing analysis. In addition to filling traditional roles in stand-alone timing debugging, verification, and design sign-off, static-timing-analysis programs are quickly moving into additional parts of the design effort, in which they contribute to correct-by-construction electronic design.

Static-timing analysis programs are proving to be an essential part of the design-automation tool set for digital-chip design. Fast timing analyzers enable logic-synthesis and floorplanning tools to avoid timing problems and optimize results for performance. Timing analyzers are being integrated with place-and-route tools to produce competitive sub-micron designs that meet increasingly stringent timing constraints. Timing analyzers are also determining delays for logic simulation and ac-test-generation tools and providing input to a variety of power-analysis- and device-power-level-optimization programs, and electromigration-analysis routines. Timing-driven design is indeed becoming a reality.

References

Kamikawai, R, M Yamada, T Chiba, K Furumaya, Y Tsuchiya, "A Critical Path Delay Check System," Proceedings of the 18th Design Automation Conference, 1981, pg 118.
Hitchcock, R, G Smith, D Cheng, "Timing Analysis of Computer Hardware," IBM Journal of Research and Development, Volume 26, No. 1, 1982, pg 100.
Hitchcock, R, "Timing Verification and the Timing Analysis Program," Proceedings of the 19th Design Automation Conference, 1982, pg 594.
Gening, L, T Lane, C Alexander, J Smith, "Developments in Logic Network Path Delay Analysis," Proceedings of the 19th Design Automation Conference, 1982, pg 605.
Toyoshima, R, Y Takiguchi, K Matsumoto, H Hongou, M Hashimoto, R Kamikawai, K Takizawa, "An Effective Delay Analysis System for a Large Scale Computer Design," Proceedings of the 23rd Design Automation Conference, 1986, pg 398.
Yen, H, S Ghanta, H Du, "A Path-Selection Algorithm for Timing Analysis," Proceedings of the 25th Design Automation Conference, 1988, pg 720.
Cherry, J, "Pearl: A CMOS Timing Analyzer," Proceedings of the 25th Design Automation Conference, 1988, pg 148.
Wallace, D, and C Sequin, "ATV: An Abstract Timing Verifier," Proceedings of the 25th Design Automation Conference, 1988, pg 154.

Author's biography

Mark S Fredrickson is an advisory electrical engineer at IBM Corp's Server Development Division (Rochester, MN), where he supports and develops timing-analysis software and leads the timing-tool team. He holds a BSEE from Brigham Young University (Provo, UT) and an MSEE from the University of Santa Clara (Santa Clara, CA). He is a registered professional engineer in Minnesota and has worked for IBM for more than 13 years. He enjoys camping, fishing, hunting, woodcarving, playing bass-guitar, and church activities.

| EDN Access | Feedback | Table of Contents |