Delay calculation

Last updated

Delay calculation is the term used in integrated circuit design for the calculation of the gate delay of a single logic gate and the wires attached to it. By contrast, static timing analysis computes the delays of entire paths, using delay calculation to determine the delay of each gate and wire.

Contents

There are many methods used for delay calculation for the gate itself. The choice depends primarily on the speed and accuracy required:

  • Circuit simulators such as SPICE may be used. This is the most accurate, but slowest, method.
  • Two dimensional tables [1] are commonly used in applications such as logic synthesis, placement and routing. These tables take an output load and input slope and generate a circuit delay and output slope. The values of the tables are usually computed using circuit simulators in a procedure referred to as characterization or standard cell characterization. A common file format for storing the lookup tables is the Liberty [2] [3] format.
  • A very simple model called the K-factor model is sometimes used. This approximates the delay as a constant plus k times the load capacitance.
  • A more complex model called Delay Calculation Language, [4] or DCL, calls a user-defined program whenever a delay value is required. This allows arbitrarily complex models to be represented, but raises significant software engineering issues.
  • Logical effort provides a simple delay calculation that accounts for gate sizing and is analytically tractable.

Similarly, there are many ways to calculate the delay of a wire. The delay of a wire will normally be different for each destination. In order to increase accuracy (and decrease speed), the most common methods are:

  • Lumped C. The entire wire capacitance is applied to the gate output, and the delay through the wire itself is ignored.
  • Elmore delay [5] is a simple approximation, often used where speed of calculation is important but the delay through the wire itself cannot be ignored. It uses the R and C values of the wire segments in a simple calculation. The delay of each wire segment is the R of that segment times the downstream C. Then all delays are summed from the root. (This assumes the network is tree-structured, true of most nets in chips. In this case, the Elmore delay can be calculated in time O(N) with two tree traversals. If the network is not tree-structured the Elmore delay can still be computed, but involves matrix calculations. [6] )
  • Moment matching is a more sophisticated analytical method. It can be thought of as either matching multiple moments in the time domain or finding a good rational approximation (a Padé approximation) in the frequency domain. (These are very closely related - see Laplace transform.) It can also be considered a generalization of Elmore delay, which matches the first moment in the time domain (or computes a one-pole approximation in the frequency domain - they are equivalent). The first use of this technique, AWE, [7] used explicit moment matching. Newer methods such as PRIMA [8] and PVL use implicit moment matching, based on Krylov subspaces. These methods are slower than Elmore but more accurate. Compared to circuit simulation they are faster but less accurate.
  • Circuit simulators such as SPICE may be used. This is usually the most accurate, but slowest, method.
  • DCL, as defined above, can be used for interconnecting as well as gate delay.

Often, it makes sense to combine the calculation of a gate and all the wires connected to its output. This combination is often called the stage delay.

The delay of a wire or gate may also depend on the behaviour of the nearby components. This is one of the main effects that is analyzed during signal integrity checks.

Delay calculation in digital design

In the context of semi-custom digital design, pre-characterized digital information is often abstracted in the form of the above-mentioned 2-D look-up table (LUT). The idea behind the semi-custom design method is to use blocks of pre-built and tested components to build something larger, say, a chip.

In this context, the blocks are logic gates such as NAND, OR, AND, etc. Although, in reality, these gates will be composed of transistors, a semi-custom engineer will only be aware of the delay information from the input pin to the output pin, called a timing arc. The 2D table represents the variability of the gate's delay concerning the two independent variables, usually the rate of change of the signal at the input and the load at the output pin. These two variables are called slew and load in design parlance.

A static timing analysis engine will first calculate the delay of the individual cells and string them together to do further analysis.

Statistical delay calculation

As chip dimensions get smaller, the delays of both gates and wires may need to be treated as statistical estimates instead of deterministic quantities. For gates, this requires extensions to the library formats. For wires, this requires methods that can calculate the means and distributions of wire delays. In both cases, it is critical to capture the dependence on the underlying variables, such as threshold voltage and metal thickness, since these result in correlations among the delays of nearby components. See [9] for an early example.

See also

Related Research Articles

SPICE is a general-purpose, open-source analog electronic circuit simulator. It is a program used in integrated circuit and board-level design to check the integrity of circuit designs and to predict circuit behavior.

<span class="mw-page-title-main">Clock signal</span> Timing of electronic circuits

In electronics and especially synchronous digital circuits, a clock signal is an electronic logic signal which oscillates between a high and a low state at a constant frequency and is used like a metronome to synchronize actions of digital circuits. In a synchronous logic circuit, the most common type of digital circuit, the clock signal is applied to all storage devices, flip-flops and latches, and causes them all to change state simultaneously, preventing race conditions.

Standard Delay Format (SDF) is an IEEE standard for the representation and interpretation of timing data for use at any stage of an electronic design process. It finds wide applicability in design flows, and forms an efficient bridge between dynamic timing analysis and static timing analysis.

In computer science, a lookup table (LUT) is an array that replaces runtime computation with a simpler array indexing operation, in a process termed as direct addressing. The savings in processing time can be significant, because retrieving a value from memory is often faster than carrying out an "expensive" computation or input/output operation. The tables may be precalculated and stored in static program storage, calculated as part of a program's initialization phase (memoization), or even stored in hardware in application-specific platforms. Lookup tables are also used extensively to validate input values by matching against a list of valid items in an array and, in some programming languages, may include pointer functions to process the matching input. FPGAs also make extensive use of reconfigurable, hardware-implemented, lookup tables to provide programmable hardware functionality. LUTs differ from hash tables in a way that, to retrieve a value with key , a hash table would store the value in the slot where is a hash function i.e. is used to compute the slot, while in the case of LUT, the value is stored in slot , thus directly addressable.

The method of logical effort, a term coined by Ivan Sutherland and Bob Sproull in 1991, is a straightforward technique used to estimate delay in a CMOS circuit. Used properly, it can aid in selection of gates for a given function and sizing gates to achieve the minimum delay possible for a circuit.

In digital circuit design, register-transfer level (RTL) is a design abstraction which models a synchronous digital circuit in terms of the flow of digital signals (data) between hardware registers, and the logical operations performed on those signals.

Propagation delay is the time duration taken for a signal to reach its destination. It can relate to networking, electronics or physics.

Asynchronous circuit is a sequential digital logic circuit that does not use a global clock circuit or signal generator to synchronize its components. Instead, the components are driven by a handshaking circuit which indicates a completion of a set of instructions. Handshaking works by simple data transfer protocols. Many synchronous circuits were developed in early 1950s as part of bigger asynchronous systems. Asynchronous circuits and theory surrounding is a part of several steps in integrated circuit design, a field of digital electronics engineering.

Standard Parasitic Exchange Format (SPEF) is an IEEE standard for representing parasitic data of wires in a chip in ASCII format. Non-ideal wires have parasitic resistance and capacitance that are captured by SPEF. These wires also have inductance that is not included in SPEF. SPEF is used for delay calculation and ensuring signal integrity of a chip which eventually determines its speed of operation.

Static timing analysis (STA) is a simulation method of computing the expected timing of a synchronous digital circuit without requiring a simulation of the full circuit.

<span class="mw-page-title-main">Integrated circuit design</span> Engineering process for electronic hardware

Integrated circuit design, semiconductor design, chip design or IC design, is a sub-field of electronics engineering, encompassing the particular logic and circuit design techniques required to design integrated circuits, or ICs. ICs consist of miniaturized electronic components built into an electrical network on a monolithic semiconductor substrate by photolithography.

The electric circuit extraction or simply circuit extraction, also netlist extraction, is the translation of an integrated circuit layout back into the electrical circuit (netlist) it is intended to represent. This extracted circuit is needed for various purposes including circuit simulation, static timing analysis, signal integrity, power analysis and optimization, and logic to layout comparison. Each of these functions require a slightly different representation of the circuit, resulting in the need for multiple layout extractions. In addition, there may be a postprocessing step of converting the device-level circuit into a purely digital circuit, but this is not considered part of the extraction process.

<span class="mw-page-title-main">Signal integrity</span>

Signal integrity or SI is a set of measures of the quality of an electrical signal. In digital electronics, a stream of binary values is represented by a voltage waveform. However, digital signals are fundamentally analog in nature, and all signals are subject to effects such as noise, distortion, and loss. Over short distances and at low bit rates, a simple conductor can transmit this with sufficient fidelity. At high bit rates and over longer distances or through various mediums, various effects can degrade the electrical signal to the point where errors occur and the system or device fails. Signal integrity engineering is the task of analyzing and mitigating these effects. It is an important activity at all levels of electronics packaging and assembly, from internal connections of an integrated circuit (IC), through the package, the printed circuit board (PCB), the backplane, and inter-system connections. While there are some common themes at these various levels, there are also practical considerations, in particular the interconnect flight time versus the bit period, that cause substantial differences in the approach to signal integrity for on-chip connections versus chip-to-chip connections.

<span class="mw-page-title-main">Computational electromagnetics</span> Branch of physics

Computational electromagnetics (CEM), computational electrodynamics or electromagnetic modeling is the process of modeling the interaction of electromagnetic fields with physical objects and the environment using computers.

The Timing closure in VLSI design and electronics engineering is the process by which a logic design of a clocked synchronous circuit consisting of primitive elements such as combinatorial logic gates and sequential logic gates is modified to meet its timing requirements. Unlike in a computer program where there is no explicit delay to perform a calculation, logic circuits have intrinsic and well defined delays to propagate inputs to outputs.

Jingsheng Jason Cong is a Chinese-born American computer scientist, educator, and serial entrepreneur. He received his B.S. degree in computer science from Peking University in 1985, his M.S. and Ph. D. degrees in computer science from the University of Illinois at Urbana-Champaign in 1987 and 1990, respectively. He has been on the faculty in the Computer Science Department at the University of California, Los Angeles (UCLA) since 1990. Currently, he is a Distinguished Chancellor’s Professor and the director of Center for Domain-Specific Computing (CDSC).

Elmore delay is a simple approximation to the delay through an RC network in an electronic system. It is often used in applications such as logic synthesis, delay calculation, static timing analysis, placement and routing, since it is simple to compute and is reasonably accurate. Even where it is not accurate, it is usually faithful, in the sense that reducing the Elmore delay will almost always reduce the true delay, so it is still useful in optimization.

Conventional static timing analysis (STA) has been a stock analysis algorithm for the design of digital circuits for a long time. However the increased variation in semiconductor devices and interconnect has introduced a number of issues that cannot be handled by traditional (deterministic) STA. This has led to considerable research into statistical static timing analysis, which replaces the normal deterministic timing of gates and interconnects with probability distributions, and gives a distribution of possible circuit outcomes rather than a single outcome.

In electronic design automation, parasitic extraction is the calculation of the parasitic effects in both the designed devices and the required wiring interconnects of an electronic circuit: parasitic capacitances, parasitic resistances and parasitic inductances, commonly called parasitic devices, parasitic components, or simply parasitics.

Lawrence Pileggi is the Coraluppi Head and Tanoto Professor of Electrical and Computer Engineering at Carnegie Mellon University. He is a specialist in the automation of integrated circuits, and developing software tools for the optimization of power grids. Pileggi's research has been cited thousands of times in engineering papers.

References

  1. ↑ E.-Y. Chung, B.-H. Joo, Y.-K. Lee, K.-H. Kim and S.-H. Lee, “Advanced delay analysis method for submicron ASIC technology,” in Proc. IEEE 5th Int. ASIC Conf. 1992, pp. 471-474.
  2. ↑ "Liberty file format, lecture slides" (PDF). Retrieved 15 December 2022.
  3. ↑ "Liberty user guide and reference manual" (PDF). Archived from the original (PDF) on 2022-12-15. Retrieved 15 December 2022.
  4. ↑ IEEE standard including DCL
  5. ↑
  6. ↑ If each capacitor is replaced by a current source of the same value, and the root grounded, then the DC voltage at each node is numerically equal to the Elmore delay (first time domain moment). This formulation works whether or not the network is tree structured. See the paper on AWE below for more details.
  7. ↑
  8. ↑
  9. ↑ Ying Liu; Pileggi, L.T.; Strojwas, A.J., (1999) Model order-reduction of RC(L) interconnect including variational analysis, proceedings of the 36th Design Automation Conference, 21–25 June 1999, pp. 201 - 206
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.