Formal methods are a promising alternative to simulation-based verification of mixed-signal systems. However, in practice, such methods fail to scale with heterogeneity and complexity of today's analog/mixed-signal systems. Furthermore, it is unclear how they can be integrated into existing verification flows. This paper shows a path to overcome these obstacles. The idea is to use a hierarchical verification flow, in which components can be verified by formal methods or by multirun simulation. To transport verification results across hierarchies, we represent parameters and properties by affine arithmetic decision diagrams. We study to which extent this approach fulfills the needs of practical application by the verification of a phase-locked loop of an IEEE 802.15.4 transceiver system.

The growing complexity of VLSI designs demands for continuous performance improvement of Electronic Design Automation (EDA) applications. Tradionally, part of this performance delta has been reached by leveraging the improvements in the single threaded performance of common processors. Unfortunately processor speeds have mostly plateaued in recent years. However, the advent of freely programmable GPUs allowed their use as highly parallel systems for a variety of computational use cases, making them an attractive device for reaching performance goals. In this paper, we introduce STP, a quadratic placement implementation, which leverages the computational power of GPUs as well as multicore CPUs in order to speed up execution.

We address the problem of formally verifying nonlinear analog circuits with an uncertain initial set by computing their reachable set. A reachable set contains the union of all possible system trajectories for a set of uncertain states and as such can be used to provably check whether undesired behavior is possible or not. Our method is based on local linearizations of the nonlinear circuit, which naturally results in a piecewise-linear system. To substantially limit the number of required locations, our approach computes linearized locations on-the-fly depending on which states are reachable. We can show that without the proposed on-the-fly technique, the conversion to piecewise-linear systems is infeasible even for a few nonlinear semiconductor devices (discrete state-space explosion problem). Our method is fully automatic and only requires a circuit netlist. Piecewise-linear systems have gained popularity not only for verification, but also for accelerated simulation of nonlinear circuits. Our method provides a guaranteed bound on the number of linearization locations that have to be explicitly computed for such a nonlinear circuit.

Reduction of interconnect length and thus reduction of power dissipation, and improvement of chip-performance is a key benefit of three-dimensional integrated circuits (3D ICs). However, to profit from 3D, carefully planning global interconnects (e.g. buses or wide IO) already at the floorplanning stage is very important. To this end, we present a new global interconnect driven 3D floorplanner which, different from previous work, simultaneously optimizes global interconnect routes, performs TSV placement, and accounts for fixed-outline floorplanning. For our 3D floorplanner, which is based on Simulated Annealing, we introduce an approach that efficiently guides the optimization process towards a valid and low-cost 3D floorplan solution. Experimental results on GSRC benchmarks demonstrate the efficiency of our tool.

Mission Profiles contain top-level stress information for the design of future systems. These profiles are refined and transformed to design constraints. We present methods to propagate the constraints between design domains like package and chip. We also introduce a cross-domain methodology for our corresponding constraint transformation system ConDUCT. The proposed methods are demonstrated on the basis of an automotive analog/mixed-signal application.

As fast non-simulation-based power estimation techniques, probabilistic simulation techniques were widely researched in the 1990s. Spatial and temporal correlations are commonly known as two fundamental challenges of these kinds of techniques. Previous work showed that spatial correlation could be coped with by means of bit-parallel simulation. For temporal correlation that has great impact on estimating glitches, previous work only showed that it could be considered by means of a glitch-filtering scheme which is an approximation algorithm, but did not answer the question whether temporal correlation could be overcome without any approximation. Our work extends conventional probabilistic simulation techniques and puts the essentials and extensions of probabilistic simulation into a theoretical framework. Based on the framework, this paper shows that modeling temporal correlation in probabilistic simulation without any approximation is only possible in theory. Therefore, an improved approximation of the exact method is proposed. Compared to the conventional probabilistic simulation, our prominently improved results prove the effectiveness of our approximation algorithm. At the end of this paper, the advantages and the bottlenecks of probabilistic simulation are concluded in general.

Analysis of mixed-signal circuits on system level demands for an accelerated simulation of analog blocks. We precompute state space representations that can be used to evaluate the circuit response and predict the occurrence of events triggered by analog components. Interfacing such models to SystemC digital simulation allows for very fast mixed-signal transient analysis. The key contribution of this paper is the dynamic generation of SystemC events from analog descriptions. We evaluate the performance of our approach using PWM (pulse width modulation) example circuits from the automotive domain which are interfaced to a SystemC microcontroller model. Accuracy and speed is compared to reference simulations utilizing traditional SPICE-like analog simulators. Our approach allows for a speedup of up to 70 for mixed-signal simulations compared to traditional analog and digital simulators.

The impact of parameter variations in integrated analog circuits is usually analyzed by Monte Carlo methods with a high number of simulation runs. Few approaches based on interval arithmetic were not successful due to tremendous overapproximations. In this paper, we describe an innovative approach computing transient and DC simulations of nonlinear analog circuits with symbolic range representations that keeps correlation information, and hence has a very limited overapproximation. The methods are based on affine and quadratic arithmetic. Ranges are represented by unique symbols so that linear correlation information is preserved. We demonstrate feasibility of the methods by simulation results using complex analog circuits.

This paper presents a novel arithmetic which allows calculations with fluctuating values. The arithmetic consists of a special representation of random variables and procedures for performing numerical operations between them. Given the distributions of initial random variables, the moments (such as expected value, variance and higher moments) of any calculated variable can be determined. Our approach is not limited to normal distributions and works with linear and nonlinear functions. Correlations between variables are taken into account automatically by the arithmetic. Examples show the accuracy and runtimes compared to Monte Carlo simulation.

The classification and quantification of a projected design's technical properties is essential for the prediction of success or failure of a microelectronic development project. The derived values have to mirror the design's capacity and thus allow for an estimation of the design complexity. This chapter depicts the PRODUKTIV+ solution approach to the ascertainment of a design artifact and the determination of equations in particular.

As design complexity increases, todaypsilas HDL-based design flows push the capabilities of designers and tools to the limit. In recent years, ambitious efforts at increasing the abstraction level of formal design languages have been presented in order to overcome these limitations. Nevertheless, certain parts of all systems still have to be described in detail. Unfortunately, even small analog parts can slow down a global system simulation significantly. It is therefore necessary to generate abstract models with reduced but adequate result accuracy for these ldquobottleneckrdquo components. This paper presents a novel approach to the automated generation and evaluation of abstract behavioural models for automotive applications. Our methodology aims at achieving a convincing speedup in global system verification by accelerating the transient simulation of the crucial analog and mixed-signal components. The speedup results not only from an increased level of abstraction but also from a fast generation of circuit equations without the need for numerical integration. The approach is able to handle nonlinear circuits by employing piecewise linear models. The use of a SystemC interface will allow effortless integration into manifold simulation environments.

Non-tree routing experiences an increasing interest as technology scales into the nanometer range. Via and wire opens have become the main yield detractors considering random spot defects due to the additive manufacturing process of copper wires. Wiring networks containing loops offer some robustness against open defects which increases functional yield. State-of-the-art delay calculation enables the treatment of loops but does not provide an adequate solution for timing analysis in the presence of an open. If the delay in the presence of an open is not properly analyzed, a functional fail will be masked and replaced by a parametric fail which is only detectable applying delay testing. In this paper we present a new method to rapidly calculate the maximum delay if an open occurs in the net. For topologies consisting of non-adjacent loops we provide proof that the worst delay considering the Elmore delay metric can be found in 2N+1 delay calculations, whereas N is the number of loops in the net.

Since the IC technology scales down the effect of voltage drop/ground bounce becomes increasingly significant. Voltage drop and ground bounce can compromise the gate driving capability and degrade the IC performance, and even can cause IC functional failures. Hence, it is crucial to capture this effect efficiently and accurately in order to improve circuit reliability. in this paper, we propose efficient modeling techniques for analyzing power distribution in deep sub micron (DSM) ASIC designs. Current Source-based Model (CSM) and Voltage Controlled Resistor (VCR) are the key concepts in our approach. A basic prerequisite for the new approach are CMOS standard libraries that are pre-characterized with respect to the corresponding modeling requirements. This paper also presents an approach for this characterization step. The proposed techniques can efficiently handle multiple-input-switching (MIS), including single-input-switching events (SIS) and provide good analysis results compared to the reference with two orders of magnitude speedup, although the cell library pre-characterization is based on SPICE simulations. Our model is independent of the power network context, which implies that different power distribution networks may be analyzed based on the same model and the same cell characterizations. The run-time, memory and accuracy efficiency of the proposed method are demonstrated on an industrial design.

As technology rapidly scales, performance variations (delay, power etc.) arising from process variation are becoming a significant problem. The use of linear models has been proven to be very critical in many today's applications. Even for well-behaved performance functions, linearising approaches as well as quadratic model provide serious errors in calculating expected value, variance and higher central moments. This paper presents a novel approach to analyse the impacts of process variations with low efforts and minimum assumption. Circuit performance was formulated as a function of the random parameters and approximated it by Taylor expansion up to 4th order. Taking advantage of the knowledge about higher moments, the Taylor series was converted to characteristics of performance distribution. The experiments show that this approach provides extremely exact results even in strongly non-linear problems with large process variations. Its simplicity, efficiency and accuracy make this approach a promising alternative to the Monte Carlo method in most practical applications

The fault coverage of tests for microelectronic circuits must be evaluated as part of the test generation process. Although much faster than fault simulation, fault-grading a large and complex design using fault emulation can still take up a considerable amount of time. This is especially true when considering that the whole process has to be repeated when test patterns have been modified. In this paper we propose methods to reduce the number of fault emulations for repeated fault-grading runs. We further introduce algorithms to shorten the tests after an initial complete fault-grading. The algorithms have been implemented into a modular fault emulation environment. We present results obtained on the emulation system Mercury+by Cadence.

In nanometer technologies the importance of opens as yield detractors considerably increases. This requires to reconsider traditional tree based routing approaches for signal wiring. We propose a Greedy Minimum Routing Tree Augmentation (GMRTA) algorithm that shows significantly better results than previous approaches. The algorithm adds links to routing trees, thus increases its robustness against open defects. By exploiting that edges in multiple loops can be removed the augmentation efficiency is further improved. As a special feature, our algorithm keeps timing constraints which have not been considered by previous GMRTA algorithms.

Algorithms for the length-compensation of bus geometries are presented. The algorithms are capable of automatically rerouting busses such that individual trace lengths are equalized, for an arbitrary number of traces, an arbitrary distribution of starting trace lengths, as well as arbitrary trace widths and intertrace spacings. Algorithms are also presented that allow the automatic adaptation to given space constraints and the observance of minimum structure sizes.

Fault emulation has become an important tool for test evaluation. However, until now fault models other than the stuck-at fault model have rarely been used in emulation. In this paper, we propose non-classical fault models for emulation and a generic fault emulation environment capable of supporting these and other fault models and different emulation modes in a common support framework. Although different in logical implementation and physical abstraction level, all fault models are administered and applied together and can even be mixed in a single fault grading campaign. The proposed fault emulation environment is not restricted in its use to a certain emulator. The modular approach proposed in this paper allows an easy adaption for different emulation systems and reuse of all key components including the fault models. Those may be applied during fault grading campaigns as well as in-circuit emulation. We will present results obtained on the emulation system Mercury+ by Cadence

Shrinking microelectronic circuits leads to increasing parameter variations. Verification by Monte Carlo and worst case analysis has a limited reliability or requires a very high number of simulation runs. In this paper we give an overview of the semi-symbolic simulation approach. Compared to Monte Carlo and worst case analysis, the semi-symbolic simulation needs only a single simulation run to compute all possible results for given stimuli and parameter variations. For semi-symbolic simulation we model parameter variations and tolerances by symbols. Then, we compute the transient analysis using affine arithmetic. As results of transient analysis we get the system quantities as affine expressions. The affine expressions describe the impact of the parameter variations to the quantities

This paper presents a new methodology for routing net bundles like busses and paired nets maintaining parasitic symmetry. It is mainly devoted to analog signal interconnect and can also be used for critical digital busses or clock signals. The PARasitic SYmmetric router (PARSY) is the first router that limits differential capacitances to a user defined value. Wirelength differences inside a net bundle are also equalized automatically. This routing methodology uses a novel module generator approach for wire implementation.

We present an extended method of automatic behavioral model generation for nonlinear analog circuits. The focus is on a decrease of simulation time. A procedural model formulation approach is introduced, together with a new simplification method based on the recognition of physical transistor properties of the element models. The simplification process is performed with respect to simulation time, and a hierarchical modeling approach is proposed. The result of these extensions are models with an obvious speed-up in simulation time compared to the simulation of the original netlists.

We propose a new placement model for global placement. This model uses probabilities to localize the cells. It enables arbitrary levels of placement abstraction. Wire-length estimations at any level can be derived from the model. We present a new placer, that uses a special variant of the proposed model. Examples show that the model properties improve placement quality.

In this contribution we present the first method for model checking on nonlinear analog systems. Based on digital CTL model checking algorithms and results in hybrid model checking, we have developed a concept to adapt these ideas to analog systems. Using an automatic state space subdivision method the continuous state space is transfered into a discrete model. In doing this, the most challenging task is to retain the essential nonlinear behavior of the analog system. To describe analog specification properties, an extension to the CTL language is needed. Two small examples show the properties and advantages of this new method and the capability of the implemented prototype tool.

Today's high capacity Field-programmable Gate Arrays (FPGAs) and the upcoming trend to System-On-Programmable-Chip (SOPC) require novel implementation strategies. These have to overcome long implementation times of traditional synthesis approaches. Here, a unique approach for technology mapping of both datapath modules and controller descriptions into Look-Up Table (LUT)-based FPGAs is presented The proposed method starts at Register-Transfer-Level (RTL) and follows the Library of Parameterized Modules (LPM) standard. The mapping environment includes an implicit state minimization algorithm for FSMs.

We present the first approach to model checking for nonlinear analog systems. Based on digital CTL model checking ideas, results in hybrid model checking and special needs in analog verification, a new model checking tool has been implemented Published model checking tools for hybrid systems require discrete or partly linear system descriptions. Our focus is on nonlinear analog behavior, therefore a new approach is necessary. There are mainly two aspects to be considered. Firstly, a discrete model retaining the essential nonlinear analog behavior has to be developed Secondly, model checking for analog systems requires extensions of the language to define analog system properties in a reasonable way.

In this paper we introduce an approach for parameter controlled symbolic analysis of nonlinear analog circuits. Based on a state-of-the-art algorithm, it enables the removal of specific circuit parameters from a symbolic circuit description, given as a set of nonlinear differential algebraic equations (DAEs). During the removal, singularities are considered, which includes structural changes of the set of DAEs. The feasibility of our approach is shown by several circuit examples.

We present a novel approach to optimization-based variation-tolerant analog circuit sizing. Using formal methods based on affine arithmetic, we calculate guaranteed bounds on the worst-case behavior and deterministically find the global optimum of the sizing problem by means of branch-and-bound optimization. To solve the nonlinear circuit equations with parameter variations, we define a novel affine-arithmetic Newton operator that gives a significant improvement in computational efficiency over an implementation using interval arithmetic. The calculation of guaranteed worst-case bounds and the global optimization are demonstrated by a prototype implementation.

In this paper, we present a new algorithm to partition netlists for logic emulation under consideration of the targeted emulator architecture. The proposed algorithm allows the flexible use for a wide variety of applications because the description of the architecture is part of the input data. It combines a new approach of finding and improving an initial solution with existing algorithms to cluster the netlist and optimize the number of cut nets between blocks. As a result, the algorithm ensures that the cut nets between the created blocks can be connected within the emulation system, even without a full interconnect structure. Experiments on a number of designs and architectures demonstrate that the algorithm is competitive for architectures with full interconnect and that it is unique for architectures with limited interconnect resources.

A new and efficient combination of signal tracing and block recognition techniques for circuit analysis is proposed. It utilizes the benefits of both approaches to solve problems such as signal flow or gate recognition. The analysis process is easily controlled by a user definable rule set where ports, nets and block are attributed with types. After structural investigation a hierarchical netlist is produced providing block information as subcircuits. As an important feature, the algorithm allows the handling of optional ports as well. Thus, this flexible approach is applicable to various circuit types and works on several abstraction levels.

We present a new methodology for current driven routing and layout verification for analog applications used to avoid defects due to electromigration.

We present the single layer router CDR (Current Driven Router) capable of routing analog multiterminal signal nets with current driven wire widths. The widths used during routing are determined by current properties per terminal gained by simulation or manually specified by circuit designers. The algorithm presented computes a Steiner tree layout satisfying all specified current constraints while obeying the maximum allowed current densities on all connections. CDR calculates the Steiner tree topology, computes the unknown currents of wires connecting two Steiner points and generates the final Steiner tree layout in a single step thus eliminating the need for a separate layout post-processing step common to power and ground routing algorithms. CDR uses a connection graph for layout representation and applies an advanced minimum detour algorithm in combination with a modified 'three-point steinerization' heuristic for Steiner tree based layout construction.

Capacitance coupling can have a significant impact on gate delay in today's deep submicron circuits. In this paper we present a static timing analysis tool that calculates the longest path of synchronous circuits taking the impact of crosstalk on gate delays into account. We show that passive modeling of the coupling capacitance can significantly underestimate the delay and that an assumption of permanent worst-case coupling unnecessarily overestimates it. Our method is validated by comparison to Spice simulations.

A hardware based approach to Fault Emulation independent of the logic emulation system in use has been developed and is presented in this paper. Fault injection into a targeted circuit is made possible with the introduction of additional logic. The stuck-at-fault model is simulated with the method described here, which may also be used for multiple faults and bridging faults. This discussion will focus only on SSF. Using a commercial emulator, speeds for combinational circuits of several MHz were reached allowing for system testing at real time speed.

This paper presents an approach to formal verification of linear analog circuits with parameter tolerances. The method proves that an actual circuit fulfils a specification in a given frequency interval for all parameter variations. It is based on a curvature driven bound computation for value sets using interval arithmetic. Some examples demonstrate the feasibility of this approach.

The importance of identifying false paths in a combinational circuit cannot be overstated since they may mask the true delay. We present a fast algorithm based on Boolean satisfiability for solving this problem. We also present extensions to this per-path approach to find the critical path of a circuit in a reasonable time.

A new approach for partitioning VLSI digital integrated circuits is presented. In contrast to known approaches, which use only topological information, the presented method also exploits specific information about design modules and higher-level design structure. Based on this knowledge, the design-driven procedure creates a cluster structure that incorporates the inherent design relationships (e.g. signal flow, logic blocks) in the best way possible. Followed by standard iterative improvement algorithms, partitions are produced that outperform many partitioning approaches published before. Because of its linear time complexity, the presented clustering strategy is able to handle very large designs. Due to its modular structure, it can be easily extended to incorporate special design features or target architectures such as emulation systems.

A new approach to implement fast array multipliers of any word length in SRAM-based FPGAs is presented. The proposed method is based on a generic FPGA model and, therefore, suitable for most commercial FPGA devices. Taking the logical structure of the multiplier into account, technology mapping including adaptive structure generation as well as signal flow driven placement and automatic partitioning are efficiently performed yielding implementations of higher performance and better resource utilization than previously published.

A fully automatic method for generating behavioral models for nonlinear analog circuits is presented. This method is based on simplifications of the system of nonlinear differential equations which is derived from a transistor level netlist. Generated models include nonlinear dynamic behavior. They are composed of symbolic equations comprising circuit parameters. Accuracy and simulation speed-up are shown by several examples.

Partitioning of digital circuits has become a key problem area during the last five years. Benefits from new technologies like Multi-Chip-Modules or logic emulation strongly depend on partitioning results. Most published approaches are based on abstract graph models constructed from flat netlists, which consider only connectivity information. The approach presented in this paper uses information on design hierarchy in order to improve partitioning results and reduce problem complexity. Designs up to 150 k gates have been successfully partitioned by descending and ascending the hierarchy. Compared to. Standard k-way iterative improvement partitioning approach results are improved by up to 65% and runtimes are decreased by up to 99%.

This paper presents an approach to nonlinear dynamic analog circuit verification. The input-output behavior of two systems is analyzed to check whether they are functionally similar. The algorithm compares the implicit nonlinear state space descriptions of the two systems on the same or on different levels of abstraction by sampling the state spaces and by building a nonlinear one-to-one mapping of the state spaces. Some examples demonstrate the feasibility of our approach.

A comparison is made between various approximations of the line-to-ground capacitance problem in a VLSI environment. It is shown that with up-to-date dimensions, the simple parallel-plate model is no longer adequate. However, easy-to-use and fast-to-compute formulas exist that result in accurate and reliable capacitance values.>

Traditional methods for resistance calculation suffer from some unfavourable features, that make them uncomfortable to use. Although requiring a lot of manual processing, they are rather inaccurate and often claim for severe artwork restrictions (e.g. orthogonal geometry)which conflict with the desire for most dense layouts.

An algorithm is presented which compares the actual topology of an integrated circuit derived from its layout with a user-supplied description of the intended nominal circuit at the transistor level. Devices and nets in both circuits may be named arbitrarily. Using information about device types and pin types to weight the nodes of the corresponding graphs, isomorphism is tested and the names of devices and nets are matched. Differences are isolated and result in an error report for layout correction. The implemented program NEtwork COMparison (NECOM) has proven to be particularly efficient for analog bipolar circuits. It represents an essential part of a recently developed complete mask artwork analysis system called ALAS.