This paper presents two simulation-based methods for the calculation of the feasible performance values of analog integrated circuits. The first method computes the Pareto-optimal tradeoffs of competing performances at full simulator accuracy. Additionally, it identifies and evaluates the technological and structural constraints that prevent further performance improvement. The second method computes linear approximations to the feasible performance regions of circuits with a large number of performances. Both techniques allow a comparison of different circuit topologies with respect to their performance capabilities and contribute to hierarchical circuit sizing. The presented methods are validated by experimental results of Pareto-front computation and feasible performance region computation of operational amplifiers and hierarchical sizing of filters.

Analog performance space exploration identifies the range of feasible performance values of a given circuit topology. It is an extremely challenging task of great importance to topology selection and hierarchical sizing. In this paper, a novel technique for the efficient simulation-based exploration of high-dimensional performance spaces is presented. To this end, fundamental circuit design knowledge is described by constraint functions. Based on a linearization of the latter and of the circuit performance functions, a description of the feasible performance range in the form of a polytope is derived. Moreover, the approach is integrated into a hierarchical sizing method, where it propagates topological and technological constraints bottom-up. Practical application results demonstrate the efficiency and usefulness of the new method.

We present a new technique to examine the trade-off regions of a circuit where its competing performances become "simultaneously optimal", i.e. Pareto optimal. It is based on circuit simulation, sizing rules, which capture elementary topological and technological constraints, and an advanced multicriteria optimization formulation called normal-boundary intersection. We are able to efficiently calculate a well-balanced discretization of a Pareto surface, identify the active constraints, which prevent a further improvement, and even rank these constraints in terms of stringency. Experimental results demonstrate the efficacy and efficiency of the method and its potential for topology selection and analog synthesis.

Symbolic simulation is a formal verification technique which combines the flexibility of conventional simulation with powerful symbolic methods. Some constructs, however, which are easy to handle in conventional simulation need special consideration in symbolic simulation. This paper discusses some special constructs that require unique treatment in symbolic simulation such as the symbolic representation of arrays, an efficient This paper discusses some special constructs that are unique to symbolic simulation such as the symbolic representation of arrays, an efficient symbolic method for storing arrayed instances and the handling of symbolic data-dependent delays. We present results which demonstrate the effectiveness of our symbolic array model in the simulation of highly regular structures like FPGAs, memories or cellular automata.

A unified approach to fault simulation for FGDs is introduced. Instead of a direct fault simulation, the proposed approach calculates indirectly from the simulator output the sets of undetectable values of the trapped charge on the floating gate transistor It covers all potential gate charges of an FGD at one or more transistors and allows the application of conventional circuit simulators for simulating DC, AC and transient test. Based on this fault simulation, a test design methodology is presented that can determine all test sets that detect all FGDs for all possible values of gate charge.

We present a new method for mismatch analysis and automatic yield optimization of analog integrated circuits with respect to global, local and operational tolerances. Effectiveness and efficiency of yield estimation and optimization are guaranteed by consideration of feasibility regions and by performance linearization at worst-case points. The proposed methods were successfully applied to two example circuits for an industrial fabrication process. 1.

Presents the sizing rules method for analog CMOS circuit design that consists of: first, the development of a hierarchical library of transistor pair groups as basic building blocks for analog CMOS circuits; second, the derivation of a hierarchical generic list of constraints that must be satisfied to guarantee the function of each block and its reliability with respect to physical effects; and third, the development of an automatic recognition of building blocks in a circuit schematic. The sizing rules method efficiently captures design knowledge on the technology-specific level of transistor pair groups. This reduces the preparatory modeling effort for analog circuit synthesis. Results of industrial applications to circuit sizing, design centering, response surface modeling and analog placement show the significance of the sizing rules method. Sizing rules especially make sure that automatic circuit sizing and design centering lead to technically meaningful and robust results.

In this paper a new method for analog circuit sizing with respect to manufacturing and operating tolerances is presented. Two types of robustness objectives are presented, i.e. parameter distances for the nominal design and worst case distances for the design centering. Moreover, the generalized boundary curve is presented as a method to determine a parameter correction within an iterative trust region algorithm. Results show that a significant reduction in computational costs is achieved using the presented robustness objectives and generalized boundary curve.

Implication, justification, and propagation are three important Boolean problems that have to be solved during many tasks in electronic design automation (EDA) for digital circuits. As they constitute the key components of automatic test pattern generation (ATPG) most algorithms that tackle these problems originate in ATPG research. Due to their fundamental nature these ATPG-based methods have successfully been adopted by logic synthesis and formal verification where they have helped advance the fields of netlist optimization and Boolean equivalence checking. Despite their high importance and wide applicability, the data structures and algorithms suggested so far have proven to be suboptimal and inflexible in several respects. Therefore, we propose IGRAINE, a fast and flexible engine for performing implication, justification, and propagation in combinational circuits that is specifically optimized with respect to these tasks. Due to its modular design, IGRAINE is easily included into new applications that require ATPG-based methods. Our approach is based on a new implication graph (IG) model which forms the core of IGRAINE. Contrary to other IG models, the proposed IG represents all information on the implemented logic function as well as the topology of a combinational circuit in a single graph model. In order to demonstrate the performance of the presented IG-based algorithms for implication, justification, and propagation, we provide experimental results for stuck-at and path delay fault ATPG as well as Boolean equivalence checking. They show that TIP outperforms the state-of-the-art in SAT-based and structure-based ATPG. A comparison with tools for Boolean equivalence checking demonstrates the high effectiveness of our approach.

In this paper a method for the automatic sizing of analog integrated circuits is presented. Basic sizing rules, representing circuit knowledge, are set up before the sizing and are introduced as structural constraints into the sizing process. Systematic consideration of these structural constraints during the automatic sizing prevents pathologically sized circuits and speeds up the automatic sizing. The sizing is done with a sensitivity-based, iterative trust region method.

This paper presents a new approach to the test design of analog circuits, called characteristic observation inference (COI). The COI method considers parametric as well as catastrophic faults. A strict distinction between the operational environment, defined by the specifications of the circuit, and the test environment, defined by the test configuration and the test equipment, is introduced. A parametric fault model is developed that combines circuit specifications, statistical parameters reflecting parametric faults, and measurements of the circuit under test. These measurements are called characteristic observations. For each specification, a test inference criterion is computed using feature extraction and logistic discrimination analysis. From a set of such criteria the satisfaction or violation of the specifications can be inferred from characteristic observations. Based on these results, additional test criteria for catastrophic faults are determined using test set compaction. Moreover, measurement noise and parasitic effects, which crucially influence the test design, are systematically considered, and a physically interpretable sampling strategy is presented. The COI method applied to two different test designs yields very good results with respect to parametric faults as well as to catastrophic faults.

Functional decomposition is an important technique for technology mapping to look up table-based FPGA architectures. We present the theory of and a novel approach to functional disjoint decomposition of multiple-output functions, in which common subfunctions are extracted during technology mapping. While a Boolean function usually has a very large number of subfunctions, we show that not all of them are useful for multiple-output decomposition. We use a partition of the set of bound set vertices as the basis to computepreferabledecomposition functions, which are sufficient for an optimal multiple-output decomposition. We propose several new algorithms that deal with central issues of functional multiple-output decomposition. First, an efficient algorithm to solve the variable partitioning problem is described. Second, we show how to implicitly compute all preferable functions of a single-output function and how to identify all common preferable functions of a multiple-output function. Due to implicit computation in the crucial steps, the algorithm is very efficient. Experimental results show significant reductions in area.

In this paper, we present a novel method for topological delay optimization of combinational circuits.Unlike most previous techniques, optimization is performed after technology mapping.Therefore, exact gate delay information is known during optimization.Our method p erforms incremental network transformations, speci cally substitutions of gate input or output signals by new gates.We present new theory which relates incremental network transformations to combinations of global clauses, and show how to detect such valid clause combinations.Employing techniques which originated in the test area, our method i s c apable to globally optimize large circuits.Comprehensive experimental results show that our method reduces the delay of large standard c ell netlists by 23% on average.In contrast to most other delay optimization techniques, area r e ductions are achieved c oncurrently.

We present theory and a novel, implicit algorithm for functional disjoint decomposition of multiple-output functions.While a Boolean function usually has a huge number of decomposition functions, we show that not all of them are useful for multiple-output decomposition.We therefore introduce the concept of preferable decomposition functions, which are sucient for optimal multiple-output decomposition.W e describe how to implicitly compute all preferable decomposition functions of a single-output, and how to identify all common preferable decomposition functions of a multiple-output function.Due to the implicit computation in all steps, the algorithm is very ecient.Applied to FPGA synthesis, the method combines the typically separated steps of common subfunction extraction and technology mapping.Experimental results show signi cant reductions in area.

Various satisfiability problems in combinational logic blocks as, for example, test pattern generation, verification, and netlist optimization, can be solved efficiently by exploiting the fundamental concepts of propagation and justification. Therefore, fault effect propagation gains further importance. For the first time, we provide the theoretical background for a single path oriented fault effect propagation considering both single and multiple path sensitization. We call this approach SPOP. Furthermore, we formulate necessary and sufficient sensitization conditions for SPOP. From these conditions the best suited algebra for propagation can be derived. Experimental results for stuck-at test pattern generation demonstrate that the new approach is orthogonal to D-frontier based methods. We achieve substantial improvements with respect to test pattern generation time and quality.

In this paper, a new approach to analog test design based on the circuit design process, called Characteristic Observation Inference (COI), is presented. In many situations, it is prohibitive to directly verify the circuit specifications due to the test equipment costs. Our approach considers a given universal set of reasonable input stimuli and measurements that can be performed with the given test equipment. From this universal set, a minimal number of measurements is automatically selected that represent a set of observations characterizing the state of the circuit under test with respect to parametric faults. A parametric fault model is introduced which is related to the individual circuit specifications. For each given circuit specification, a corresponding test inference criterion is computed, based on logistic discrimination analysis. By applying these criteria, the satisfaction or violation of the given circuit specifications can be inferred from the observations of the circuit under test. The COI method applied to a complex operational amplifier yields very encouraging simulated results with respect to parametric faults as well as to catastrophic faults.

This paper presents an ecient approach to path delay fault simulation.We ac celerate fault simulation by more than one order of magnitude with a new speed u p t e chnique called path hashing.An intelligent path identi cation method allows to deal with circuits containing two orders of magnitude more p aths than state-of-the-art tools.Using these techniques larger circuits can be handled with a reasonable amount of time and memory.

The routing of modern sea-of-gates circuits is a very hard to solve combinatorial problem. The use of three or more layers of metal allows for channelless designs, where area routers are used to connect the pins of a net. In this paper, we present a new router that aims at combining the good quality of the traditional global/final routing approach with the high efficiency of strictly hierarchical routers. This is achieved by reducing the routing problem until its complexity is manageable. The reduced problem is then solved hierarchically by well-known maze-running algorithms using the divide-and-conquer paradigm. In addition to the ability to handle big circuits efficiently, this approach allows the parallel solution of subproblems, yielding significant speedups even when using workstation networks.>

In this paper, a new methodology for integrated circuit design considering the inevitable manufacturing and operating tolerances is presented. It is based on a new concept for specification analysis that provides exact worst-case transistor model parameters and exact worst-case operating conditions. Corresponding worst-case distances provide a key measure for the performance, the yield, and the robustness of a circuit. A new deterministic method for parametric circuit design that is based on worst-case distances is presented. It comprises nominal design, worst-case analysis, yield optimization, and design centering. In contrast to current approaches, it uses standard circuit simulators and at the same time considers deterministic design parameters of integrated circuits at reasonable computational costs. The most serious disadvantage of geometric approaches to design centering is eliminated, as the method's complexity increases only linearly with the number of design variables.>

We describe an efficient iterative improvement procedure for row-based cell placement with special emphasis on the objective function used to model net lengths. Two new net models are introduced and we prove theoretically that the net models are accurate approximations of the widely used half perimeter of a rectangle enclosing all pins of a net. In addition, unlike the half perimeter model, our net models allow us to compute costs for assigning cells to locations independently for all cells to be placed simultaneously. This offers our algorithm an important advantage compared to other iterative improvement techniques: many cells can be placed simultaneously by formulating placement as a network flow problem. This makes our algorithm more independent from a processing sequence than standard iterative improvement techniques. Finally, we compare our method to some existing algorithms including TimberWolfSC 5.4. We ran all of the algorithms on the SIGDA Benchmark Suite. We found that our method produced solutions with up to 23% less layout area while using an order of magnitude less running time compared to TimberWolfSC 5.4.>

Worst-case analysis is commonly used in integrated circuit design to verify a satisfactory circuit performance with regard to changes in the manufacturing conditions. However, worst-case analysis is often carried out using approximate worst-case parameter sets, that do not consider fluctuations in the operating conditions. This paper presents a new approach to the worst-case design of integrated circuits that takes account of fluctuations in the operating conditions. It provides unique and realistic worst-case manufacturing conditions and worst-case operating conditions for given circuit specifications. These specifications may be either, minimum yield requirements or, lower and upper performance bounds. A software package for worst-case analysis and optimization is presented and illustrated by two examples.

A novel method for circuit optimization in the face of manufacturing process variations is presented. It is based on the characterization of the feasible design space by worst-case points and related gradients. The expense for this characterization is linear with the number of circuit performances. A deterministic optimization procedure based on the so-called worst-case distances is introduced, combining nominal and tolerance design in a single design objective. The entire optimization process with regard to performance, yield, and robustness uses sensitivity analyses and requires a much smaller number of simulations than the Monte-Carlo-based approaches. Moreover, the proposed method takes into account the partitioning of the parameter space into deterministic and statistical parameters which is an inherent property of integrated circuit design.>

The authors present a placement method for cell-based layout styles. It is composed of alternating and interacting global optimization and partitioning steps that are followed by an optimization of the area utilization. Methods using the divide-and-conquer paradigm usually lose the global view by generating smaller and smaller subproblems. In contrast, GORDIAN maintains the simultaneous treatment of all cells over all global optimization steps, thereby considering constraints that reflect the current dissection of the circuit. The global optimizations are performed by solving quadratic programming problems that possess unique global minima. Improved partitioning schemes for the stepwise refinement of the placement are introduced. The area utilization is optimized by an exhaustive slicing procedure. The placement method is applied to real-world problems, and excellent results in terms of placement quality and computation time are obtained.>

The principles of fault simulation and fault grading are introduced by a general description of the problem. Based upon the well-known concept of restricting fault simulation to the fanout stems and of combining it with a backward traversal inside the fanout-free regions of the circuit, proposals are presented to further accelerate fault simulation and fault grading. These proposals aim at parallel processing of patterns at all stages of the calculation procedure, at reducing the number of fanout stems for which a fault simulation has to be carried out, and at taking advantage of structural characteristics of the circuit. An experiment with a set of benchmark circuits demonstrates the efficiency of the proposed approaches.