A New Timing-Driven Placement Algorithm Based on Table-Lookup Delay Model

There have been extensive studies on timing-driven placement in recent years.Theapproaches toward this problem fall into two main categories:net-based and path-based.In a typical net-based one,potential critical paths and acceptable d...     

The hierarchical timing pair model for multirate DSP applications

The problem of representing timing information associated with functions in a dataflow graph is considered. This information is used for constraint analysis during behavioral synthesis of appropriate architectures for implementing the graph. Conventional models for timing suffer from shortcomings that make it difficult to represent timing information in a hierarchical manner for sequential and multirate systems. Some of these shortcomings are identified, and an alternate timing model that does not have these problems for hardware implementations is provided. We introduce the concept of timing pairs to model delay elements in sequential and multirate circuits and show how this allows us to derive hierarchical timing information for complex circuits. The resulting compact representation of the timing information can be used to streamline system performance analysis. In addition, several analytical results that previously applied only to single rate systems can now be extended to multirate systems. We present an algorithm to compute the timing parameters and have used this to compute timing parameters for a number of benchmark circuits. The results obtained on several ISCAS benchmark circuits as well as several multirate dataflow graphs corresponding to useful signal processing applications are presented. These results show that the new representation model can result in large reductions in the amount of information required to represent timing for hierarchical systems.     

Fast Interconnect and Gate Timing Analysis for Performance Optimization

Static timing analysis is a key step in the physical design optimization of VLSI designs. The lumped capacitance model for gate delay and the Elmore model for wire delay have been shown to be inadequate for wire-dominated designs. Using the effective capacitance model for the gate delay calculation and model-order reduction techniques for wire delay calculation is prohibitively expensive. In this paper, we present sufficiently accurate and highly efficient filtering algorithms for interconnect timing as well as gate timing analysis. The key idea is to partition the circuit into low and high complexity circuits, whereby low complexity circuits are handled with efficient algorithms such as total capacitance algorithm for gate delay and the Elmore metric for wire delay and high complexity circuits are handled with sign-off algorithms. Experimental results on microprocessor designs show accuracies that are quite comparable with sign-off delay calculators with more than of 65% reduction in the computation times     

Predicting Interconnect Delay for Physical Synthesis in a FPGA CAD Flow

This paper studies the prediction of interconnect delay in an industrial setting. Industrial circuits and two industrial field-programmable gate-array (FPGA) architectures were used in this paper. We show that there is a large amount of inherent randomness in a state-of-the-art FPGA placement algorithm. Thus, it is impossible to predict interconnect delay with a high degree of accuracy. Furthermore, we show that a simple timing model can be used to predict some aspects of interconnect timing with just as much accuracy as predictions obtained by running the placement tool itself. Using this simple timing model in a two-phase timing driven physical synthesis flow can both improve quality of results and decrease runtime. Next, we present a metric for predicting the accuracy of our interconnect delay model and show how this metric can be used to reduce the runtime of a timing driven physical synthesis flow. Finally, we examine the benefits of using the simple timing model in a timing driven physical synthesis flow, and attempt to establish an upper bound on these possible gains, given the difficulty of interconnect delay prediction.     

Dynamic Threshold Delay Characterization Model for Improved Static Timing Analysis

Transistors within a gate take a finite amount of time to switch and hence there is always a propagation delay associated with it. These delays are evaluated by standard cell characterization techniques using EDA tools. However, these standard measurement methods tend to fail when simulating the design with practical values of slope and load and gives rise to the problem of negative or non-monotonic delays. Negative/non-monotonic delays lead to false positives during static timing analysis, synthesis and simulation of circuits and are undesirable. Hence, there is a need to implement new methods for characterization of propagation delay that will lead to more realistic monotonic delay values, ultimately achieving early timing closures. One such method of delay measurement based on actual switching thresholds has been proposed in this work.     

基于神经网络的逻辑门NBTI退化建模与计算

提出了基于神经网络的逻辑门退化延迟模型。根据逻辑门延迟数据特征,采用神经网络BP算法,对仿真样本数据进行训练,获得7种基本逻辑门延迟退化计算方法以及网络模型参数。基于45 nm CMOS工艺进行验证,模型计算值与Spice仿真数据的误差不超过5%。在此基础上,提出NBTI效应下的电路路径延迟退化计算流程,并编写计算程序,对基本逻辑门构成的任意组合逻辑电路(ISCAS85)进行NBTI退化分析,获得路径时序的NBTI退化量。采用该模型,可在电路设计阶段预测电路时序,为高性能、高可靠性数字集成电路的设计提供重要依据。     

Physical timing modeling for bipolar VLSI

An approach for the analytical timing modeling of bipolar VLSI circuits that is based on average branch current analysis and the parametric correction scheme is presented. The combination of these techniques permits complex delay-sensitive effects of bipolar digital circuits to be incorporated in the derivation of the bipolar delay models. The delay functions of two basic bipolar subcircuit configurations (the series-gated structure and the emitter follower) are derived using the proposed techniques. It is shown that accurate timing information for the high-speed bipolar digital circuit, such as ECL, CML, and BiCMOS, can be obtained by repeated processing of these subcircuit delay functions. The delay estimates obtained with these timing models have been shown to be accurate typically within 10% of SPICE estimates. Applications include switch-level timing simulation, timing analysis and verification cell optimization, and technology mapping     

Analysis of the switching speed of BiCMOS buffer under high current

A nonlinear analytical transient response model that is suitable for BiCMOS driver circuits operating under the Kirk and Van der Ziel effect is presented. The model accounts for both base vertical push-out and lateral stretching phenomena where the forward transit time τ _f has a square law dependence on the collector current. Based on the new transient model, a closed-form BiCMOS delay expression is derived that shows excellent agreement with measured gate delay from a 0.8-μm BiCMOS technology. The comparison is made for a wide range of circuit parameters. The delay model can be used to develop timing analyzers, timing simulators, and circuit optimization tools for ULSI circuit design. As an application of the delay model, a circuit design algorithm is derived to optimize the speed-area performance of the BiCMOS buffers     

Bounded delay timing analysis and power estimation using SAT

This paper presents a satisfiability based approach that can be used for accurate estimation of both the critical delay and dynamic transition power consumption of circuits using an event propagation model. The accuracy of the model depends on the accuracy of the gate delays. The speed and efficiency of modern Boolean SAT solvers permits us to model complicated delay models like the Bounded Delay Model, which is better able to capture realistic variations in gate delays due to process variations and changes in operating conditions. We show that timing analysis with bounded delays yields a more accurate critical delay for a circuit than with fixed gate delays. In spite of the high complexity due to unpredictable gate delays, our SAT based approach gives good performance on benchmark circuits, even with a Bounded Delay Model derived from a real industrial library.     

Seamless Pipelining of DSP Circuits

Pipelining is a popularly used technique to achieve higher frequency of operation of digital signal processing (DSP) applications, by reducing the critical path of circuits. But conventionally critical path is estimated by the discrete component timing model in terms of the times required for the computation of additions and multiplications, where arithmetic circuits are considered as discrete components. Pipeline registers are inserted in between arithmetic circuits to reduce the estimated critical path. In this paper, we show that very often the architecture-level pipelining, based on the discrete component timing model, does not result in significant reduction in critical path, but on the other hand increases the latency and register complexity. In order to derive greater advantage of pipelining, propagation delays of different combinational sections could be evaluated precisely at gate level or at least at the level of one-bit adders, and based on that, the critical path could be reduced by placing the pipeline registers seamlessly across the combinational datapath without restricting them to be placed only in between arithmetic circuits. In this paper, we present adequately precise evaluation of propagation delays across combinational path as a network of arithmetic circuits based on seamless view of signal propagation. Using the precise information of propagation delay of combinational sections, we identify the best possible locations of pipeline registers in order to reduce the critical path up to the desired limit. The proposed seamless pipelining approach is found to achieve the desired acceleration of DSP applications without significant pipeline overhead in terms of latency and register complexity.     

On gate level power optimization using dual-supply voltages

In this paper, we present an approach for applying two supply voltages to optimize power in CMOS digital circuits under the timing constraints. Given a technology-mapped network, we first analyze the power/delay model and the timing slack distribution in the network. Then a new strategy is developed for timing-constrained optimization issues by making full use of stacks. Based on this strategy, the power reduction is translated into the polynomial-time-solvable maximal-weighted-independent-set problem on transitive graphs. Since different supply voltages used in the circuit lead to totally different power consumption, we propose a fast heuristic approach to predict the optimum dual-supply voltages by looking at the lower bound of power consumption in the given circuit. To deal with the possible power penalty due to the level converters at the interface of different supply voltages, we use a “constrained F-M” algorithm to minimize the number of level converters. We have implemented our approach under an SIS environment. Experiment shows that the resulting lower bound of power is tight for most circuits and that the predicted “optimum” supply voltages are exactly or very close to the best choice of actual ones. The total power saving of up to 26% (average of about 20%) is achieved without degrading the circuit performance, compared to the average power improvement of about 7% by the gate sizing technique based on a standard cell library. Our technique provides the power-delay tradeoff by specifying different timing constraints in circuits for power optimization     

Statistical analysis of asynchronous pipelines in presence of process variation using formal models

Globally Asynchronous Locally Synchronous Network on Chip (GALS NoC) is one of the possible interconnect platforms in multiprocessor systems on a chip. Designing proper links and buffers in these circuits can improve their performance. An asynchronous pipeline is a key element in buffer designs. The type of pipeline and its size can influence the performance metrics such as power consumption and delay. However, asynchronous pipelines face some challenges such as performance evaluation, verification, and process variation. We consider a new formal model to overcome these challenges simultaneously. In this paper, a new statistical model for asynchronous pipelines based on Generalized Stochastic Petri Net (GSPN) has been developed. This model can be applied to different pipeline stages, in order to compare them based on the statistical analysis of performance metrics (power consumption and delay), and to analyze their performance and timing verification in presence of variation. We have explored various kinds of asynchronous pipelines, and their corresponding results show this model has reasonable accuracy in average (below 5%) and in variance, compared to the low level Monte Carlo Hspice simulation.     

Efficient logic-level timing analysis using constraint-guidedcritical path search

As the operating speed of digital circuits dramatically increases with the advance of VLSI technology, it is becoming more critical to ensure that the circuits are free from timing-related design errors. In a traditional static timing approach nonfunctional paths cannot be distinguished from functional ones since the functionality of a circuit is ignored. This often results in overestimation of circuit delay and can degrade the circuit performance. In today's design methodology where the use of automated logic synthesis and module-based design are popular, circuits with a very large number of nonfunctional (false) paths are common. This paper describes an efficient logic-level timing analysis approach that can provide an accurate delay estimate of a digital circuit which may have many long false paths. By using logic incompatibilities in a circuit as constraints for critical path search, the algorithm determines the longest sensitizable path without explicit path enumeration. Since the number of false paths that can be implicitly eliminated is potentially exponential to the number of path constraints, performance improvement is significant     

Test Vector Generation for Post-Silicon Delay Testing Using SAT-Based Decision Problems

Debugging and speed-binning a fabricated design requires a pattern-dependent timing model to generate patterns, which static timing analysis is incapable of providing. To address these issues, we propose a timing analysis tool that integrates a pattern-dependent delay model into its analysis. Our approach solves for the delay by using the concept of circuit unrolling and formulation of timing questions as decision problems for input into a satisfiability (SAT) solver. We generate a critical path and input vectors that stimulate it, taking into account pattern-dependent effects such as data-dependent gate delays and multiple-inputs switching. The effectiveness and validity of the proposed methodology is illustrated through experiments on various benchmark circuits and comparisons directly with SPICE.     

用RC网络作延迟模型的开关级定时模拟

本文提出一种用RC网络作延迟模型进行开关级定时模拟的方案.此方案把开关级定时模拟划分为求解将来状态和计算状态变化的延迟两个步骤来进行.文中讨论了延迟模型的建立及延迟计算中的有关问题.按照所述方案,开发了一个适用于MOS VLSI逻辑模拟及延迟估算的计算机程序LOMOS.实践表明,LOMOS模拟出的信号延迟时间同电路模拟程序SPICEII相比误差通常在30％以内,模拟速度要快近三个数量级.     

The effect of propagation delay uncertainty on the speed oftime-of-flight digital optoelectronic circuits

Time-of-flight synchronization is a new digital design methodology for optoelectronics that eliminates latches, allowing higher clock rates than alternative timing schemes. Synchronization is accomplished by precisely balancing connection delays. Circuits use pulse-mode signaling and clock gates to restore pulse timing. Many effective pipeline stages are created within combinational logic without extra hardware bounding the stages. Time-of-flight design principles are applicable to packet routing and sorting processors for optical interconnection networks. Circuits are unique because the clock rate is limited primarily by imprecision in propagation delay rather than absolute delay, as in circuits with latches. We develop a general model of delay uncertainty and focus on the effect that static and dynamic uncertainty accumulated over circuit paths has on the minimum feasible clock period. We present a method for traversing the circuit graph representation of a time-of-flight circuit to compute arrival time uncertainty at each pulse interaction point. Arrival time uncertainties give rise to pulse width and overlap constraints. From these constraints we formulate a constrained minimization to find the minimum clock period. We demonstrate our method on circuits implemented with 2×2 electro-optic switches and optical waveguides and find the electronic component of path uncertainty frequently limits speed     

优化时延与拥挤度的增量式布局算法

提出了一种优化时延的增量式布局算法,该算法根据时延分析的结果在迭代求解的过程中动态调整线网权值.在此基础上,提出了三种同时优化时延和拥挤度的多目标优化的布局算法,在满足时延和拥挤度约束的前提下对关键路径上的单元进行位置调整.实验结果表明该算法能够有效地提高芯片速度并降低走线拥挤.对于优化线长得到的布局方案,最长路径上的时延值在增量式布局之后能够降低10 % .     

Discrete-Dopant-Induced Timing Fluctuation and Suppression in Nanoscale CMOS Circuit

As the dimensions of semiconductor devices continue to be reduced, device fluctuations have become critical to determining the accuracy of timing in circuits and systems. This brief studies the discrete-dopant-induced timing characteristic fluctuations in 16-nm-gate complementary metal–oxide–semiconductor (CMOS) circuits using a 3-D “atomistic” coupled device–circuit simulation. The accuracy of the simulation has been confirmed by using the experimentally calibrated transistor physical model. For a 16-nm-gate CMOS inverter, 3.5%, 2.4%, 18.3%, and 13.2% normalized fluctuations in the rise time, fall time, high-to-low delay time, and low-to-high delay time, respectively, are found. Random dopants may cause significant timing fluctuations in the studied circuits. Suppression approaches that are based on the circuit and device design viewpoints are implemented to examine the associated characteristic fluctuations. The use of shunted transistors in the circuit provides similar suppression to the use of a device with doubled width. However, both approaches increase the chip area. To eliminate the need to increase the chip area, channel engineering approaches (vertical and lateral) are proposed, and their effectiveness in reducing the timing fluctuation is demonstrated.      

优化时延与拥挤度的增量式布局算法

提出了一种优化时延的增量式布局算法,该算法根据时延分析的结果在迭代求解的过程中动态调整线网权值.在此基础上,提出了三种同时优化时延和拥挤度的多目标优化的布局算法,在满足时延和拥挤度约束的前提下对关键路径上的单元进行位置调整.实验结果表明该算法能够有效地提高芯片速度并降低走线拥挤.对于优化线长得到的布局方案,最长路径上的时延值在增量式布局之后能够降低10%.     

Timing verification of dynamic circuits

A complete set of rules is presented for timing verification of domino-style dynamic circuits. These rules include identification of dynamic nodes, generation of accurate timing constraints based on the operating environment of the gate and verification as an enhanced part of a complete timing verification process. This methodology has been implemented in a new static timing verifier and used to verify microprocessor circuits