waashk/dblp huggingface dataset:
formal verification coverage: computing the coverage gap between temporal specifications. existing methods for formal verification coverage compare a given specification with a given implementation, and evaluate the coverage gap in terms of quantitative metrics. we consider a new problem, namely to compare two formal temporal specifications and to find a set of additional temporal properties that close the coverage gap between the two specifications. in this paper we present: (1) the problem definition and motivation, (2) a methodology for computing the coverage gap between specifications, and (3) a methodology for representing the coverage gap as a collection of temporal properties that preserve the syntactic structure of the target specification.
a unified approach to topology generation and area optimization of general floorplans. in this paper, it is shown that for any rectangularly dualizable graph, a feasible topology can be obtained by using only either straight or z-cutlines recursively within a bounding rectangle. given an adjacency graph, a potential topology, which may be nonslicible and is likely to yield an optimally sized floorplan, is produced first in a top-down fashion using heuristic search in and-or graphs. the advantage of this technique is fourfold : (i) accelerates top-down search phase, (ii) generates a floorplan with minimal number of nonslice cores, (iii) ensures safe routing order without addition of pseudo-modules, and (iv) solves the bottom-up algorithm efficiently for optimal sizing of general floorplans in the second phase.
variability inspired implementation selection problem. given a directed acyclic graph and different possible implementations for each node, the implementation selection problem (isp) selects the appropriate implementation for each node such that a given global design objective is optimized, isp is a generic formulation that is explicitly or implicitly solved in several design automation problems like leakage optimization using dual v/sub th/, gate sizing, etc. an implementation of a node results in an associated delay and perhaps cost for the node. in the presence of different sources of uncertainty and fabrication variability, fixed estimates of delays and costs of a node are extremely erroneous. we investigate a probabilistic approach to solve isp by considering probability density functions for delays and costs of a node. we propose a dynamic-programming based approach in a probabilistic sense and introduce effective pruning criteria when dealing with probability distributions for identifying co-optimal solution at each stage. a case study of leakage optimization using dual v/sub th/ is presented where we show the effectiveness of a probabilistic approach considering v/sub th/ variability over a traditional deterministic one.
hybrid cmos/nanoelectronic digital circuits: devices, architectures, and design automation. physics offers several active devices with nanometer-scale footprint, that can be best used in combination with a cmos subsystem. such hybrid circuits offer the potential for high defect tolerance combined with unparalleled performance. in this tutorial, we highlight key issues and architectural alternatives for this promising technology and outline the challenges posed by the hybrid circuits pose for design automation.
propersyn: a portable parallel algorithm for logic synthesis. an algorithm based on the transduction method and implemented in the propercad environment is described. the parallel propersyn algorithm attempts to make the execution time manageably small. the algorithm uses an asynchronous message driven computing model with no synchronizing barriers, and hence it is scalable to a larger number of processors. also, the algorithm is portable across a wide variety parallel machines. experimental results on various parallel machines are presented. the algorithm is built around a well-defined sequential algorithm interface such that there can be benefits from future expansion of the sequential algorithm
efficient circuit partitioning to extend cycle simulation beyond synchronous circuits. cycle simulation techniques, such as levelized compiled code, can ordinarily be applied only to synchronous designs. they usually cannot be applied to designs containing circuit features like combinational paths, multiple clock domains, generated clocks, asynchronous resets, and transparent latches. this paper presents a novel partitioning algorithm that partitions a non-cycle-simulatable circuit containing these features into sub-circuits that can be cycle simulated. cycle simulation techniques can be applied to the individual sub-circuits, and the whole collection of sub-circuits can be simulated together using conventional co-simulation techniques. empirical results demonstrate that this approach brings the benefits of cycle simulation to circuits that were previously impossible to cycle simulate. the partitioning algorithm requires time and space linear in the size of the circuit, and in practice is very fast. we also discuss how the key ideas presented here can be applied to accelerate hdl simulation.
noise analysis for optical fiber communication systems. the optical fiber transmission links form the backbone of the communicationsinfrastructure. almost all of voice and data (internet) traffic is routed throughterrestrial and submarine optical fiber links, connecting the world together. invention of the optical amplifiers (oas) and wavelength-division multiplexing(wdm) technology enabled very high capacity optical fiber communicationlinks that run for thousands of kilometers without any electronic repeaters, butat the same time brought many design challenges. as electronic amplifiers do,oas add noise to the signal they amplify. in the design of an optical fibercommunication link, the prediction of the deterioration the information signalsexperience due to the nonlinearity of the optical fiber and the optical noise generated by the oas is essential. in this paper, we first present a short overviewof optical fiber communication systems and the challenges that faces one froma modeling, analysis and design perspective. then, we describe novel formulations and computational techniques for the analysis of the interplay between theinformation signals and the optical noise due to the fiber nonlinearity as theypropagate together along the fiber link. our formulations are similar, in spirit,to the linear(ized), time-varying formulations for noise analysis in analog/rfelectronic circuits. we then investigate signal-noise mixing due to optical fibernonlinearities using the techniques developed. finally, we discuss the use ofthe generated results in the performance evaluation of communication links,and comment on system design implications.
modelling and analysis of communication circuit performance using markov chains and efficient graph representations. in high-speed data networks, the bit-error-rate specification on the system can be very stringent, i.e., 10-14. at such error rates, it is not feasible to evaluate the performance of a design using straightforward, simulation based, approaches. nevertheless performance prediction before actual hardware is built is essential for the design process.this work introduces a stochastic model and an analysis-based, non-monte-carlo method for performance evaluation of digital data communication circuits. the analyzed circuit is modeled by a number of interacting finite state machines with inputs described as functions on a markov chain state-space. the composition of these elements results in a typically very large markov chain. system performance measures, such as probability of bit errors and rate of synchronization loss, can be evaluated by solving linear problems involving the large markov chain's transition probability matrix. this paper first describes a dedicated multi-grid method used to solve these very large linear problems. the principal bottleneck in such an approach is the size of the markov chain state-space, which grows exponentially with system complexity. the second part of this paper introduces a novel, graph based, data structure capable of efficiently storing and manipulating transition probability matrices for several million state markov chains. the methods are illustrated on a real industrial clock-recovery circuit design.
modeling and simulation of the interference due to digital switching in mixed-signal ics. the paper introduces a methodology for the evaluation of the interference noise, caused by digital switching activity, in sensitive circuits of a mixed-digital-analog chip. the digital switching activity is modeled stochastically as functions defined on markov chains. the actual interference signal is obtained through the modulation of this discrete stochastic signal with real current injection patterns stored a priori in a pre-characterized library. the interference noise results from the propagations of these continuous stochastic signals through the linear network that models the chip power grid, substrate and relevant package parasitics. the interference noise power spectral density is computed by linear frequency-domain analysis. the methodology is implemented using advanced numerical techniques capable of tackling very large problems.
computing phase noise eigenfunctions directly from steady-state jacobian matrices. the main effort in oscillator phase noise calculation lies in computing a vector function called the perturbation projection vector (ppv). current techniques for ppv calculation use time domain numerics to generate the system's monodromy matrix, followed by full or partial eigenanalysis. we present a superior method that finds the ppv using only a single linear solution of the oscillator's time- or frequency-domain steady-state jacobian matrix. the new method is better suited for existing tools with fast harmonic balance or shooting capabilities, and also more accurate than explicit eigenanalysis. a key advantage is that it dispenses with the need to select the correct one-eigenfunction from amongst a potentially large set of choices, an issue that explicit eigencalculation based methods have to face.
time-domain non-monte carlo noise simulation for nonlinear dynamic circuits with arbitrary excitations. a new, time-domain, non-monte carlo method for computer simulation of electrical noise in nonlinear dynamic circuits with arbitrary excitations is presented. this time-domain noise simulation method is based on the results from the theory of stochastic differential equations. the noise simulation method is general in the sense that any nonlinear dynamic circuit with any kind of excitation, which can be simulated by the transient analysis routine in a circuit simulator, can simulated by our noise simulator in time-domain to produce the noise variances and covariances of circuit variables as a function of time, provided that noise models for the devices in the circuit are available. noise correlations between circuit variables at different time points can also be calculated. previous work on computer simulation of noise in integrated circuits is reviewed with comparisons to our method. shot, thermal and flicker noise models for integrated-circuit devices, in the context of our time-domain noise simulation method, are described. the implementation of this noise simulation method in a circuit simulator (spice) is described. two examples of noise simulation (a cmos ring-oscillator and a bjt active mixer) are given.
buffer insertion under process variations for delay minimization. this paper considers the buffer insertion problem under process variations. with continued technology scaling, it is necessary to model the physical parameters to be random variables. one approach to the buffer insertion problem under variations is to use the mean values of these parameters and solve the problem using traditional buffer insertion techniques for delay minimization. another approach is to find a buffer insertion solution using a new method that can handle the probability distributions. thus, the performance can be optimized with some yield constraint. in this paper, we present both analytical and experimental results to show that the two approaches give almost identical solutions. in other words, the more expensive statistical methods are not needed for the buffer insertion in delay minimization problem.
an observability-based code coverage metric for functional simulation. functional simulation is the most widely used method for design verification. at various levels of abstraction, e.g., behavioral, register-transfer level and gate level, the designer simulates the design using a large number of vectors attempting to debug and verify the design. a major problem with functional simulation is the lack of good metrics and tools to evaluate the quality of a set of functional vectors. metrics used currently are based on instruction counts and are quite simplistic. designers are forced to use ad-hoc methods to terminate functional simulation, e.g. cpu time limitations. we propose a new metric for measuring the extent of design verification provided by a set of functional simulation vectors. this metric is universal, and can be used uniformly for all designs. our metric computes observability information to determine whether effects of errors that are activated by the program stimuli can be observed at the circuit outputs. we provide preliminary experimental evidence that supports the validity of the proposed metric. we believe that using this metric in design verification will result in higher-quality functional checking. tests and improved correctness
verification of asynchronous interface circuits with bounded wire delays. the problem of verifying that the gate-level implementation of an asynchronous circuit, with given or extracted bounds on wire and gate delays, is equivalent to a specification of the asynchronous circuit behavior described as a classical flow table, under the fundamental mode of operation, is considered. a procedure for extracting the complete set of possible flow tables from a gate-level description of an asynchronous circuit under the bounded wire delay model is given. given an extracted flow table and the initial flow table specification, procedures for constructing a product flow table so as to check for machine equivalence are discussed
analytical fault modeling and static test generation for analog ics. static tests are key in reducing the current high cost of testing analog and mixed-signal ics. a new dc test generation technique for detecting catastrophic failures in this class of circuits is presented. to include the effect of tolerance of parameters during testing, the test generation problem is formulated as a minimax optimization problem, and solved iteratively as successive linear programming problems. an analytical fault modeling technique, based on manufacturing defect statistics is used to derive the fault list for the test generation. using the technique presented here an efficient static test set for analog and mixed-signal ics can be constructed, reducing both the test time and the packaging cost.
dynamic test signal design for analog ics. in this paper we present an approach to construct dynamic test signals for analog circuits. using the integral measure for characterizing time-domain signals, we extend the minmax formulation of the static test problem to the dynamic case. a sub-optimal solution strategy, similar to dynamic programming methods is used to construct the test waveforms. the approach presented here may be used to construct input signals for an on-chip test scheme or for the selection of an external stimulus applied through an arbitrary waveform generator.
efficient and accurate transient simulation in charge-voltage plane. transient simulation has traditionally been performed in current- voltage plane (with current and voltage as variables) for verification of integrated circuits and systems. this paper introduces techniques for efficient and accurate transient simulation in charge-voltage plane (with charge and voltage as variables). for integrated circuits, both simulation cost and overhead to increase accuracy are drastically reduced by performing simulations in charge-voltage plane. adaptively controlled explicit simulation in charge-voltage plane is used to demonstrate the feasibility of the approach. solution of circuit equations in charge-voltage plane is 10-20 times more efficient than in current-voltage plane. furthermore, simulation accuracy can be increased at an incremental cost. as a result, aces in charge-voltage plane provides speedups of 300x-5000x or more over traditional circuit simulators with little or no loss in circuit timing accuracy.
efficient coupled noise estimation for on-chip interconnects. noise analysis and avoidance is an increasingly critical step in deep submicron design. ever increasing requirements on performance have led to widespread use of dynamic logic circuit families and its other derivatives. these aggressive circuit families trade off noise margin for timing performance making them more susceptible to noise failure and increasing the need for noise analysis. currently, noise analysis is performed either through circuit or timing simulation or through model order reduction. these techniques in use are still inefficient for analyzing massive amount of interconnect data found in present day integrated circuits. this paper presents efficient techniques for estimation of coupled noise in on-chip interconnects. this noise estimation metric is an upper bound for rc circuits, being similar in spirit to elmore delay in timing analysis. such an efficient noise metric is especially useful for noise criticality pruning and physical design based noise avoidance techniques.
how to efficiently capture on-chip inductance effects: introducing a new circuit element k. on-chip inductance extraction and analysis is becoming increasing critical. inductance extraction can be difficult, cumbersome and impractical on large designs as inductance depends on the current return path -- which is typically unknown prior to extracting and simulating the circuit model. in this paper, we propose a new circuit element, k, to model inductance effects, at the same time being easier to extract and analyze. k is defined as inverse of partial inductance matrix l, and has locality and sparsity normally associated with a capacitance matrix. we propose to capture inductance effects by directly extracting and simulating k, instead of partial inductance, leading to much more efficient procedure which is amenable to full chip extraction. this proposed approach has been verified through several simulation results.
block-based static timing analysis with uncertainty. static timing analysis is a critical step in design of any digitalintegrated circuit. technology and design trends have ledto significant increase in environmental and process variationswhich need to be incorporated in static timing analysis.this paper presents a new, efficient and accurate block-basedstatic timing analysis technique considering uncertainty.this new method is more efficient as its modelsarrival times as cumulative density functions (cdfs) anddelays as probability functions (pdfs). computationallysimple expression are presented for basic static timing operations.the techniques are valid for any form of the probabilitydistribution, though the use piecewise linear modelingof cdfs is highlighted in this paper. reconvergent fanoutsare handled using a new technique that avoids path tracing.variable accuracy timing analysis can be performed byvarying the modeling accuracy of the piecewise linearmodel. regular and statistical timing on different parts ofthe circuit can be incorporated into a single timing analysisrun. accuracy and efficiency of the proposed method is demonstratedfor various iscas benchmark circuits.
realizable reduction for rc interconnect circuits. interconnect reduction is an important step in the design and analysis of complex interconnects found in present-day integrated circuits. this paper presents techniques for obtaining realizable and accurate reduced models for two-port and multi-port rc circuits. the proposed method is also particularly suitable for interconnect reduction for nonlinear circuit simulation and for interconnect post-processing in a parasitic extractor. the method has two limitations. first, it only considers the first few moments of the transfer function; however, that is accurate enough for rc circuits. second, the amount of interconnect reduction is topology dependent. although, most on-chip interconnect topologies are well suited for the method proposed. accuracy and efficiency of the proposed method is demonstrated for various realistic examples.
performance analysis of a system of communicating processes. efficient exploration of the system design space necessitates fast and accurate performance estimation as opposed to the computationally prohibitive alternative of exhaustive simulation. the paper addresses the issue of worst case performance analysis of a system described as a set of concurrent communicating processes. we show that the synchronization overhead associated with inter process communication can contribute significantly to the overall system performance. application of existing performance analysis techniques, which target single process descriptions, lead to inaccurate performance estimates as the synchronization overhead is not accounted for. we present perc, a fast and accurate worst case performance analysis technique which analyzes inter process communication, and accounts for synchronization overhead while computing the worst case performance estimate of a given system implementation. application of perc to example systems described as multiple communicating processes shows the ability of the proposed method to accurately estimate the worst case performance of the system implementation.
a controller-based design-for-testability technique for controller-data path circuits. this paper investigates the effect of the controller on the testability of sequential circuits composed of controllers and data paths. it is shown that even when both the controller and the data path parts are individually 100\% testable, the composite circuit may not be easily testable by gate-level sequential atpg. analysis shows that a primary problem in test pattern generation of combined controller-data path circuits is the correlation of control signals due to implications imposed by the controller specification. a design-for-testability technique is developed to re-design the controller such that the implications which may produce conflicts during test pattern generation are eliminated. the dft technique involves adding extra control vectors to the controller. experimental results show the ability of the controller dft technique to produce highly testable controller-data path circuits, with nominal hardware overhead.
non-scan design-for-testability of rt-level data paths. this paper presents a non-scan design-for-testability technique applicable to register-transfer (rt) level data path circuits, which are usually very hard-to-test due to the presence of complex loop structures. we develop a new testability measure, and utilize the rt-level structure of the data path, for cost-effective re-design of the circuit to make it easily testable, without having to either scan any flip-flop or breakloops directly. the non-scan dft technique was applied to several data path circuits. experimental results demonstrate the feasibility of producing non-scan testable data paths, which can be tested at-speed. the hardware overhead and the test application time required for the non-scan designs is significantly lower than the corresponding partial scan designs.