October 21, 2015 at 12:28Static time analysis demystified
Many novice FPGA developers (and ASICs) do not fully understand the effect of time constraints (constraints - hereinafter referred to as constants) on the synthesis results; how constants are used in static time analysis. Most of the literature on this topic comes down to considering all kinds of constants, but says nothing about the internal “kitchen” and the algorithms used. A recent post on this topic on GT ( geektimes.ru/post/254932/ [1]) is also devoted to consideration of constants . Meanwhile, constraints are just the tip of the iceberg. Their use should be based on fundamental knowledge about static time analysis, which is given, for example, in American universities, but does not tell us anything. Therefore, in fact, let's talk about the foundation.
In modern design routes for synchronous circuits, two main types of analysis are used: temporal modeling, and static temporal analysis.
Temporal modeling is mainly used for functional verification, and relies on verilog models of logic elements using plug-in delays (files in sdf, tlf standards, etc.). The advantage of temporal modeling is accuracy, and the ability to simulate large circuits. The accuracy is certainly lower than when modeling at the level of transistors (spice-modeling), but at the same time it is quite acceptable, and most importantly, it is orders of magnitude faster. The disadvantage of temporary modeling is the enormous resource-intensiveness of checking the full coverage of circuit logic tests. And most often, 100% coverage of logic with tests cannot be achieved.
Static time analysis does not model the dynamics of the circuit, and does not use verilog models of elements. Also, static analysis does not deal with the functions of the circuit and its constituent elements. The main task of static analysis is to consider all (under 100% of the possible combinations) signal delays in the circuit, and to search for violations in accordance with the specified verification rules (constants). Static analysis is called because it is performed in statics, according to the connection graph constructed in accordance with the scheme. Or, more precisely, on an acyclic digraph.
Without getting into graph theory, it suffices to say that a digraph is a directed graph, i.e. the arcs of the graph have a direction (just as the signal in the wire “runs” in one direction - from the source to the receiver). Arcs of a graph are wires between elements, and “virtual” signal paths (arcs - arches) inside elements. For example, element 2 OR NOT has only two arches: from each of the entrances to the exit. The vertices of the graph are the inputs and outputs of the elements, as well as the inputs and outputs of the circuit. As a result, using the obtained graph, it is possible to construct signal paths passing through the arcs of the graph through its vertices. If all possible signal paths are finite, then the graph is called acyclic. Static time analysis only works with acyclic digraphs, and as a result, only with finite signal paths. For example, if a circuit contains feedback, some of the signal paths will be looped, and cannot be analyzed. A crutch is used to combat feedback - CAD can try to make the graph acyclic by throwing one or more arcs out of it (as a rule, these are arches inside elements). The result is a graph without feedbacks, but thrown out arcs no longer participate in the analysis - their delay is not taken into account in the calculations.
For a better understanding of what has been said, I will comment on selected slides from the lectures on static time analysis that are given to students of the University of Texas at Austin.
The upper left corner is a diagram consisting of a D-trigger (flop), a clock-gate shutdown element, and a logic element at the flop input. The upper right corner - the rules for constructing the graph:
• circles indicate the inputs and outputs of the elements, as well as the inputs and outputs of the circuit,
• arrows indicate the edges of the graph: connections by wires, and arches (inside the elements)
• double arrows with a dotted line indicate the so-called control arches: they do not contain a delay, and in static analysis they are used not for calculating signal delays, but for monitoring, for example, setting and holding signals (setup / hold).
The bottom of the figure shows the resulting graph. All vertices are signed (it is easy to find a match with the scheme). All arcs are marked as inverting or non-inverting: for example, “rr” and “ff” stands for rise-rise and fall-fall, and means that the shown arc does not carry signal inversions. If the arc (for example, the arch in the OR-NOT element) were inverting, then the mark would be “rf” and “fr”, which means rise-fall and fall-rise, or, in other words, a change in the positive edge of the signal during passage through the arc to negative, and vice versa. As already mentioned, the function of elements in a static analysis is not considered, only the isotonic (non-inverting) function of an element, or the antitone (inverting) function, is important.
What you should pay attention to. The starting point of the signal path (the essence is the transient process) in synchronous circuits is always either an interface signal or a clock pulse. If the circuit in the above example were larger, then a whole bunch of arcs on the graph would leave the clock input (clk). And the endpoint of the signal path in the synchronous circuit is again the interface, either the trigger data input, or the clock-gate resolution. In this case, the end point of the signal path ends with one or more control arches, which indicate what checks for the received signal should be carried out. In the given example, the setup and hold (setup and hold) of the signal at the trigger information input with respect to the clock input (FF1: D - FF1: clock), and a similar check of the enable signal for the clock-gate element are checked.
How constants are reflected in the graph. Constraints that affect interface latency ( set_input_delay, set_output_delay, set_drive, set_load , etc.) simply change the delay value of the external arcs of the graph. There are constants that change the graph, for example: set_disable_timing or set_false_path . Many constraints are taken automatically from the library of elements: for example, for control arches - checks for setup / hold. I don’t want to concentrate on constants, for their understanding it’s enough to read the description in the documentation of the same Synopsys DC [2], or educational articles on the Internet, for example - on edacafe or semiwiki .
Now about the algorithms for calculating delays. Static time analysis considers only the two extreme points of the delay spread in the elements and circuitry: the worst case used for checking the setup time limit of the signal with respect to the clock pulse, and the best case used for holding time checks. There is also the so-called statistical static time analysis (SSTA), which approaches the question more intellectually, but about it some other time (especially since FPGA developers do not have this type of analysis at all).
When calculating delays, two strategies are used: calculating the actual time of arrival of the signal (AT - Arrival Time), and calculating based on the required time of arrival of the signal (RAT - Required Arrival Time). For starters, what is considered AT:
For simplicity, we assume that the delays of the leading and trailing edges are the same (although a separate calculation is usually carried out for both options). And instead of the graph, we will draw delays directly on the diagram, since this is more visual. In total, in the above figure, the wire delays are taken into account in the delays of the elements, and are indicated by two digits, separated by a comma: the first digit indicates the earliest arrival of the signal, and the second digit indicates the latest moment of its arrival. For example, “1.2” at the input means that the signal will arrive no earlier than 1 ns, and no later than 2 ns, and “2.3” inside the logic element means its delay in the range from 2 to 3 ns. Where in the calculation could the delay on the input signal come from? For example, it can be set by set_input_delaywith the keys -min and -max. The element delay is taken from the element library (measured by the library developer). Green numbers indicate the calculation progress. For the upper left element - with a native delay of 2-3 ns, the output signal can be received at the moment of 2-4 ns (if the element is triggered by the first input), and 3-5 ns, if by the second. Both ranges simply add up (since the function of the elements is not taken into account), and the result is “2.5” or from 2 to 5 ns (that is, not earlier than 2 ns, and not later than 5 ns).
Next, the calculation of the required time:
Now the calculation is carried out in the opposite direction. Suppose that the arrival of output signals is limited in the range of “5.10” and “4.10”, respectively. These restrictions can be set using set_output_delaywith the -min and –max keys. Then the calculation is carried out in the opposite direction, for example, if the delay of the element 2-4 is subtracted from the range 4-10, this will mean that the signal can reach the inputs of the element not earlier than 2 ns and not later than 6 ns. In this case, the output of the inverter, which had a limit of 5-10, is automatically limited to a more rigid range of 5-6 (obtained by the intersection of 5-10 and 2-6).
In the end, when the required propagation time of the signals is received, and the actual one, it is possible to count the violations (slack).
Green indicates the actual time required in blue. The difference (slack) is calculated and shown in black on the diagram. At the same time, a negative value of the difference is considered a violation, a positive - a margin. In any report of static analysis results, you will see two tables - calculation of the actual time, calculation of the required time, calculation of the difference, and summing up - MET or NOT MET .
In conclusion, I would like to add that the successful results of a static temporal analysis are not at all a guarantee of the design's operability. This is indicated by the simple fact that the graph is built with the active participation of the developer (by means of constants), and can be built with an error. An error in the graph results in uncontrolled paths in the circuit, which can only be caught by temporary modeling with checks of time constraints (i.e., using delays on the interfaces). Violation of temporal modeling often indicates an error in the constants. Hence a simple conclusion - static time analysis does not replace functional modeling, but supplements it.
I hope that the material presented will allow us to better understand the static temporal analysis, see it “from the inside”, and write more meaningful constants for your design. For those who want to dig further, I can advise you to read the book “Static Timing Analysis for Nanometer Designs: A Practical Approach” [3] in English.
[1] geektimes.ru/post/254932/
[2] www.synopsys.com
[3] www.springer.com/us/book/9780387938196
In modern design routes for synchronous circuits, two main types of analysis are used: temporal modeling, and static temporal analysis.
Temporal modeling is mainly used for functional verification, and relies on verilog models of logic elements using plug-in delays (files in sdf, tlf standards, etc.). The advantage of temporal modeling is accuracy, and the ability to simulate large circuits. The accuracy is certainly lower than when modeling at the level of transistors (spice-modeling), but at the same time it is quite acceptable, and most importantly, it is orders of magnitude faster. The disadvantage of temporary modeling is the enormous resource-intensiveness of checking the full coverage of circuit logic tests. And most often, 100% coverage of logic with tests cannot be achieved.
Static time analysis does not model the dynamics of the circuit, and does not use verilog models of elements. Also, static analysis does not deal with the functions of the circuit and its constituent elements. The main task of static analysis is to consider all (under 100% of the possible combinations) signal delays in the circuit, and to search for violations in accordance with the specified verification rules (constants). Static analysis is called because it is performed in statics, according to the connection graph constructed in accordance with the scheme. Or, more precisely, on an acyclic digraph.
Without getting into graph theory, it suffices to say that a digraph is a directed graph, i.e. the arcs of the graph have a direction (just as the signal in the wire “runs” in one direction - from the source to the receiver). Arcs of a graph are wires between elements, and “virtual” signal paths (arcs - arches) inside elements. For example, element 2 OR NOT has only two arches: from each of the entrances to the exit. The vertices of the graph are the inputs and outputs of the elements, as well as the inputs and outputs of the circuit. As a result, using the obtained graph, it is possible to construct signal paths passing through the arcs of the graph through its vertices. If all possible signal paths are finite, then the graph is called acyclic. Static time analysis only works with acyclic digraphs, and as a result, only with finite signal paths. For example, if a circuit contains feedback, some of the signal paths will be looped, and cannot be analyzed. A crutch is used to combat feedback - CAD can try to make the graph acyclic by throwing one or more arcs out of it (as a rule, these are arches inside elements). The result is a graph without feedbacks, but thrown out arcs no longer participate in the analysis - their delay is not taken into account in the calculations.
For a better understanding of what has been said, I will comment on selected slides from the lectures on static time analysis that are given to students of the University of Texas at Austin.
The upper left corner is a diagram consisting of a D-trigger (flop), a clock-gate shutdown element, and a logic element at the flop input. The upper right corner - the rules for constructing the graph:
• circles indicate the inputs and outputs of the elements, as well as the inputs and outputs of the circuit,
• arrows indicate the edges of the graph: connections by wires, and arches (inside the elements)
• double arrows with a dotted line indicate the so-called control arches: they do not contain a delay, and in static analysis they are used not for calculating signal delays, but for monitoring, for example, setting and holding signals (setup / hold).
The bottom of the figure shows the resulting graph. All vertices are signed (it is easy to find a match with the scheme). All arcs are marked as inverting or non-inverting: for example, “rr” and “ff” stands for rise-rise and fall-fall, and means that the shown arc does not carry signal inversions. If the arc (for example, the arch in the OR-NOT element) were inverting, then the mark would be “rf” and “fr”, which means rise-fall and fall-rise, or, in other words, a change in the positive edge of the signal during passage through the arc to negative, and vice versa. As already mentioned, the function of elements in a static analysis is not considered, only the isotonic (non-inverting) function of an element, or the antitone (inverting) function, is important.
What you should pay attention to. The starting point of the signal path (the essence is the transient process) in synchronous circuits is always either an interface signal or a clock pulse. If the circuit in the above example were larger, then a whole bunch of arcs on the graph would leave the clock input (clk). And the endpoint of the signal path in the synchronous circuit is again the interface, either the trigger data input, or the clock-gate resolution. In this case, the end point of the signal path ends with one or more control arches, which indicate what checks for the received signal should be carried out. In the given example, the setup and hold (setup and hold) of the signal at the trigger information input with respect to the clock input (FF1: D - FF1: clock), and a similar check of the enable signal for the clock-gate element are checked.
How constants are reflected in the graph. Constraints that affect interface latency ( set_input_delay, set_output_delay, set_drive, set_load , etc.) simply change the delay value of the external arcs of the graph. There are constants that change the graph, for example: set_disable_timing or set_false_path . Many constraints are taken automatically from the library of elements: for example, for control arches - checks for setup / hold. I don’t want to concentrate on constants, for their understanding it’s enough to read the description in the documentation of the same Synopsys DC [2], or educational articles on the Internet, for example - on edacafe or semiwiki .
Now about the algorithms for calculating delays. Static time analysis considers only the two extreme points of the delay spread in the elements and circuitry: the worst case used for checking the setup time limit of the signal with respect to the clock pulse, and the best case used for holding time checks. There is also the so-called statistical static time analysis (SSTA), which approaches the question more intellectually, but about it some other time (especially since FPGA developers do not have this type of analysis at all).
When calculating delays, two strategies are used: calculating the actual time of arrival of the signal (AT - Arrival Time), and calculating based on the required time of arrival of the signal (RAT - Required Arrival Time). For starters, what is considered AT:
For simplicity, we assume that the delays of the leading and trailing edges are the same (although a separate calculation is usually carried out for both options). And instead of the graph, we will draw delays directly on the diagram, since this is more visual. In total, in the above figure, the wire delays are taken into account in the delays of the elements, and are indicated by two digits, separated by a comma: the first digit indicates the earliest arrival of the signal, and the second digit indicates the latest moment of its arrival. For example, “1.2” at the input means that the signal will arrive no earlier than 1 ns, and no later than 2 ns, and “2.3” inside the logic element means its delay in the range from 2 to 3 ns. Where in the calculation could the delay on the input signal come from? For example, it can be set by set_input_delaywith the keys -min and -max. The element delay is taken from the element library (measured by the library developer). Green numbers indicate the calculation progress. For the upper left element - with a native delay of 2-3 ns, the output signal can be received at the moment of 2-4 ns (if the element is triggered by the first input), and 3-5 ns, if by the second. Both ranges simply add up (since the function of the elements is not taken into account), and the result is “2.5” or from 2 to 5 ns (that is, not earlier than 2 ns, and not later than 5 ns).
Next, the calculation of the required time:
Now the calculation is carried out in the opposite direction. Suppose that the arrival of output signals is limited in the range of “5.10” and “4.10”, respectively. These restrictions can be set using set_output_delaywith the -min and –max keys. Then the calculation is carried out in the opposite direction, for example, if the delay of the element 2-4 is subtracted from the range 4-10, this will mean that the signal can reach the inputs of the element not earlier than 2 ns and not later than 6 ns. In this case, the output of the inverter, which had a limit of 5-10, is automatically limited to a more rigid range of 5-6 (obtained by the intersection of 5-10 and 2-6).
In the end, when the required propagation time of the signals is received, and the actual one, it is possible to count the violations (slack).
Green indicates the actual time required in blue. The difference (slack) is calculated and shown in black on the diagram. At the same time, a negative value of the difference is considered a violation, a positive - a margin. In any report of static analysis results, you will see two tables - calculation of the actual time, calculation of the required time, calculation of the difference, and summing up - MET or NOT MET .
In conclusion, I would like to add that the successful results of a static temporal analysis are not at all a guarantee of the design's operability. This is indicated by the simple fact that the graph is built with the active participation of the developer (by means of constants), and can be built with an error. An error in the graph results in uncontrolled paths in the circuit, which can only be caught by temporary modeling with checks of time constraints (i.e., using delays on the interfaces). Violation of temporal modeling often indicates an error in the constants. Hence a simple conclusion - static time analysis does not replace functional modeling, but supplements it.
I hope that the material presented will allow us to better understand the static temporal analysis, see it “from the inside”, and write more meaningful constants for your design. For those who want to dig further, I can advise you to read the book “Static Timing Analysis for Nanometer Designs: A Practical Approach” [3] in English.
[1] geektimes.ru/post/254932/
[2] www.synopsys.com
[3] www.springer.com/us/book/9780387938196