Uncertainty in circuit performance due to manufacturing and environmental variations is increasing with each new generation of technology. It is therefore important to predict the performance of a chip as a probabilistic quantity. This paper proposes three novel path-based algorithms for statistical timing analysis and parametric yield prediction of digital integrated circuits. The methods have been implemented in the context of the EinsTimer static timing analyzer. The three methods are complementary in that they are designed to target different process variation conditions that occur in practice. Numerical results are presented to study the strengths and weaknesses of these complementary approaches. Timing analysis results in the face of statistical temperature and Vddvariations are presented on an industrial ASIC part on which a bounded timing methodology leads to surprisingly wrong results

In this paper, we will develop an analytic approach to estimate the statistical properties (mean and variance) of the performance of a uniformly buffered global IC interconnect, based on the mean and (co)variance of the appropriate design and technology parameters. Compared to other approaches, such as Monte Carlo based approaches, our analytic approach would allow a much tighter design optimization loop and provide a better insight in the factors involved. The model that we use is generic, but in this paper we assume a set of synthetic (not based on actual process data) but realistically large values for the variability of the input parameters. Under these assumptions, it follows that solutions for the area/power/performance tradeoff that are optimal in a deterministic setting, might suffer from excessive variability, potentially leading to a yield problem.

Uncertainty in circuit performance due to manufacturing and environmental variations is increasing with each new generation of technology. It is therefore important to predict the performance of a chip as a probabilistic quantity. This paper proposes three novel algorithms for statistical timing analysis and parametric yield prediction of digital integrated circuits. The methods have been implemented in the context of the EinsTimer static timing analyzer. Numerical results are presented to study the strengths and weaknesses of these complementary approaches. Across-the-chip variability continues to be accommodated by EinsTimer's "Linear Combination of Delay (LCD)" mode. Timing analysis results in the face of statistical temperature and Vdd variations are presented on an industrial ASIC part on which a bounded timing methodology leads to surprisingly wrong results.

No abstract available.

We present a technology mapping procedure in which an area-delay trade-off curve is constructed at each node using matches found for different decompositions of the node. This information is used effectively to find implementations that meet delay constraints while reducing area. The procedure combines state-of-the-art mapping procedures, in which a graph covering is applied to a special graph structure which succinctly encodes many representations. Major challenges were avoiding memory explosion and finding good cost estimations. The combined procedure outperforms the best result among any of the procedures used separately.

Chip industry obeys a number of laws, various kinds of laws. Mathematical laws if accurate models can be formulated, physical laws, especially solid state physics, obtained by observation and induction, chemical laws pertinent for the manufacturing processes, economical and judicial laws that concern such industries. These laws still hold true, although technology has come a long way since they were formulated. Obviously, modern technologies require a completely different design flow. Homogeneous processors do not benefit much from parts of a traditional flow. The emphasis should be more on modeling applications as networks of communicating processes in a suitable specification language. Equally important is reuse of specification software, considering the short life spans of integrated circuits and the demand for short paths to the market. General multilayer designs require complete new layout synthesis tools. Placement is obsolete and even floorplan design for each layer is not adequate because of the strong geometrical constraints. Wire planning will be more of a must, but has to acquire a more precise meaning in this application. The challenges posed by the unavoidable escape routes, to break free from the confinements of conventional large scale integration methodologies, is the topic of this paper.

This paper surveys the more important oorplan models and their u s e in the backend of chip design.Floorplans are here considered as data structures that capture the relative p ositions o f o b je c t s i n a p lane.This is in correspondance with how they were introduced in design automation in the early eighties: as a generalization of placement, that is t h e m anipulation of geometrically xed objects in order to get an overlap-free arrangement of these objects in a plane region.The introduction of the oorplanning concept n o t o n ly liberated back-end design from its (manual) puzzle character and its intractable and sometimes even undecidable problems, but a l s o enabled hierarchical design, even taking a functional hierarchy a n d transforming it by stepwise re nement into a oorplan with a compatible representation.The elegance of that procedure was so overpowering that many identi ed oorplanning with hierarchical back-end design.That oorplanning proves to be a powerful notion by itself becomes once more apparent, since almost all modern effective \placement" procedures are in essence oorplanning followed by packing or some other \legalization" stage.

We propose a new VLSI layout methodology which addresses the main problems faced in Deep Sub-Micron (DSM) integrated circuit design. Our layout “fabric ” scheme eliminates the conventional no-tion of power and ground routing on the integrated circuit die. In-stead, power and ground are essentially “pre-routed ” all over the die. By a clever arrangement of power/ground and signal pins, we almost completely eliminate the capacitive effects between signal wires. Ad-ditionally, we get a power and ground distribution network with a very low resistance at any point on the die. Another advantage of our scheme is that the arrangement of conductors ensures that on-chip inductances are uniformly negligible. Finally, characterization of the circuit delays, capacitances and resistances becomes extremely simple in our scheme, and needs to be done only once for a design. We show how the uniform parasitics of our fabric give rise to a reliable and predictable design. We have implemented our scheme using public domain layout software. Preliminary results show that it holds much promise as the layout methodology of choice in DSM integrated circuit design. 1

A shift is proposed in the design of VLSI circuits. In conventional design, higher levels of synthesis produce a netlist, from which layout synthesis builds a mask specification for manufacturing. Timing analysis is built into a feedback loop to detect timing violations which are then used to update specifications to synthesis. Such iteration is undesirable, and for very high performance designs, infeasible. The problem is likely to become much worse with future generations of technology. To achieve a non-iterative design flow, we propose that early synthesis stages should use “wireplanning” to distribute delays over the functional elements and interconnect, and layout synthesis should use its degrees of freedom to realize those delays. In this paper we attempt to quantify this problem for future technologies and propose some solutions for a “constant delay” methodology.

An automated technique to narrow down the number of parameters for linear constraint transformation models of analog circuits is described. The sets of more important circuit parameters and specifications are confined in an efficient constraint transformation model. The method is based on least square approximation and principal component analysis of the sensitivity matrix of the transformation. The resulting model encompasses the constraints confined using designers' expertise for approximated circuit calculations.

In this paper a shift is proposed in the design of vlsi circuits. In conventional design higher levels of synthesis have to deliver a gate and net list, from which layout synthesis has to built a mask specification for manufacturing. Analysis, mainly timing analysis, is built in a feedback loop to catch violations of timing requirements before sign-off. These violations are used to hand an updated specification to synthesis. Such iteration is not desirable, and for really high performance not feasible. To come to a design flow, higher level synthesis should distribute delay over the functional elements and interconnect, and layout synthesis should use its degrees of freedom to realize those delays.

The effects of scaling down the MOSFET dimensions to the deep-submicron range lead to operating regions that may be modeled by locally linear equations. The piecewise linear simulator seems to be the obvious choice. Certain requirements must be satisfied by a PL simulator for the successful manipulation of the proposed MOSFET model. Simulation results demonstrate the efficiency in simulating large deep-submicron MOSFET circuits. Several levels of hierarchy can be simulated due to the uniform PL modeling technique.

Often, and certainly in the early stages of a design, the knowl-edge about delays is imprecise. Stochastic programming is not an adequate means to account for this imprecision. Not only is a probability distribution seldom a correct translation of the designer’s delay knowledge, it also leads to inefficient algo-rithms. In this paper possibilistic programming is proposed for handling the retiming problem where delays are modelled as (triangular) possibilistic numbers. Beside the capability of optimizing the most possible clock cycle time and generat-ing its possibility distribution, it allows for trade-offs between reducing clock cycle time and chances for obtaining worse solutions. It is shown that the computational complexity is the same as for retiming with exact circuit delays.

The number of decrements necessary if the changes in the equilibrium density are bounded is derived for a simulated annealing problem. This gives an expression for the CPU-time of the process when all chains have the same length. This expression can also be used for tuning the annealing schedule for a given total CPU-time, while keeping the disturbance of the equilibrium as small as possible. The expression is also valid for generic annealing processes that use a constant factor to obtain the next value of t (the commonly used schedule).>

To apply a standard channel router for the wiring between the blocks in a building-block layout, channels have to be defined and ordered. The ordering consists of determining a sequence for routing the channels. A conflict-free sequence exists only when the layout is sliceable. An algorithm that, on the basis of local preferences, finds the optimal slicing of a sliceable layout in polynomial time and space complexity is presented. The preferences are derived from data generated by a global routing routing that thus precedes the channel definition and ordering. Also included is a heuristic technique for modifying a nonsliceable placement so that a sliceable layout is obtained.>

The authors propose stopping criteria based on statistics collected during the annealing. In contrast to conventional stop criteria, the proposed criteria do not depend on the move set. Specifically, formulae are presented for detecting that an adequate final temperature has been reached. The arguments of the formulae are obtained by observing the behavior of the variance of the score for the instance at hand. The formulae are based on experience with several applications of simulated annealing as well as facts derived from the theory of homogeneous Markov chains.>

The problem of allocating area to modules at the highest level of a top-down decomposition is treated in this paper. A theorem of Schoenberg is applied to obtain a good embedding of the module space into the plane. The dutch metric is introduced to transform netlist information - if available - into a distance matrix. This metric is flexible enough to enable the user to steer the design in an interactive environment, and rigorous enough to yield results satisfying optimality criterions. The embedding is used to derive the topology of the floorplan in the form of the structure tree of a slicing structure. To store the partial structure tree during the construction a concise and convenient data structure, the shorthand tree, is introduced. For any aspect ratio of the chip a minimum area floorplan can be generated.

The concept of the genealogical approach to the layout problem is presented. The system pursues the idea of flexible modules and is capable of dealing with arbitrarily complex tasks.