waashk/dblp huggingface dataset:
symbolic analysis of large analog circuits with determinant decision diagrams. symbolic analog-circuit analysis has many applications, and is especially useful for analog synthesis and testability analysis. in this paper, we present a new approach to exact and canonical symbolic analysis by exploiting the sparsity and sharing of product terms. it consists of representing the symbolic determinant of a circuit matrix by a graph---called determinant decision diagram (ddd)---and performing symbolic analysis by graph manipulations. we showed that ddd construction and ddd-based symbolic analysis can be performed in time complexity proportional to the number of ddd vertices. we described a vertex ordering heuristic, and showed that the number of ddd vertices can be quite small --- usually orders-of-magnitude less than the number of product terms. the algorithm has been implemented. an order-of-magnitude improvement in both cpu time and memory usages over existing symbolic analyzers isaac and maple-v has been observed for large analog circuits.
software synthesis through task decomposition by dependency analysis. latency tolerance is one of main problems of software synthesis in the design of hardware-software mixed systems. this paper presents a methodology for speeding up systems through latency tolerance which is obtained by decomposition of tasks and generation of an efficient scheduler. the task decomposition process focuses on the dependency analysis of system i/o operations. scheduling of the decomposed tasks is performed in a mixed static and dynamic fashion. experimental results show the significance of our approach.
power optimization of real-time embedded systems on variable speed processors. power efficient design of real-time embedded systems based on programmable processors becomes more important as system functionality is increasingly realized through software. this paper presents a power optimization method for real-time embedded applications on a variable speed processor. the method combines off-line and on-line components. the off-line component determines the lowest possible maximum processor speed while guaranteeing deadlines of all tasks. the on-line component dynamically varies the processor speed or bring a processor into a power-down mode according to the status of task set in order to exploit execution time variations and idle intervals. experimental results show that the proposed method obtains a significant power reduction across several kinds of applications.
decomposition methods for library binding of speed-independent asynchronous designs. we describe methods for decomposing gates within a speed-independent asynchronous design. the decomposition step is an essential part of the library binding process, and is used both to increase the granularity of the design for higher quality mapping and to ensure that the design can be implemented. we present algorithms for simple hazard-free gate decomposition, and show results which indicate that we can decompose most of the gates in our benchmark set by this simple method. we then extend these algorithms to work for those cases in which no simple decomposition exists.
a coordinate-transformed arnoldi algorithm for generating guaranteed stable reduced-order models of rlc circuits. since the first papers on asymptotic waveform evaluation (awe), pade-based reduced order models have become standard for improving coupled circuit-interconnect simulation efficiency. such models can be accurately computed using bi-orthogonalization algorithms like pade via lanczos (pvl), but the resulting pade approximates can still be unstable even when generated from stable rlc circuits. for certain classes of rc circuits it has been shown that congruence transforms, like the arnoldi algorithm, can generate guaranteed stable and passive reduced-order models. in this paper we present a computationally efficient model-order reduction technique, the coordinate-transformed arnoldi algorithm, and show that this method generates arbitrarily accurate and guaranteed stable reduced-order models for rlc circuits. examples are presented which demonstrates the enhanced stability and efficiency of the new method.
a novel scan architecture for power-efficient, rapid test. scan-based testing methodologies remedy the testability problem of sequential circuits; yet they suffer from prolonged test time and excessive test power due to numerous shift operations. the high density of the unspecified bits in test data enables the utilization of the test response data captured in the scan chain for the generation of the subsequent test stimulus, thus reducing both test time and test data volume. the proposed scan-based test scheme accesses only a subset of scan cells for loading the subsequent test stimulus while freezing the remaining scan cells with the response data captured, thus decreasing the scan chain transitions during shift operations. the experimental results confirm the significant reductions in test application time, test data volume and test power achieved by the proposed scan-based testing methodology.
partial core encryption for performance-efficient test of socs. the isolation of a core through full i/o scan helps ease soc test challenges;yet the performance of high-speed socs is significantly hampered.we propose a partial core encryption methodology wherein thecore vendor unveils only a small part of the core logic, successfully satisfyingcore ip protection requirements. once the partially encryptedcores are merged into an soc, the system integrator performs test generationon the visible soc logic only, greatly reducing the test generationeffort expended. by utilizing the test data provided by the core vendoras well, the soc integrator can test the soc with no performancedegradation. we present an efficient fault analysis based core encryptionalgorithm which is guided by judiciously computed testability measures.the experimental results confirm the significantly high encryption levelsattained by the proposed encryption algorithm.
interface specification for reconfigurable components. this paper presents a way of encoding some kinds of dynamic reconfiguration behaviour in the interface portion of circuit descriptions. this has many advantages. the user of a reconfigurable circuit has some knowledge about the reconfigurable interface of the circuit. static analysis tools can make better decisions about how to schedule virtual hardware. and most importantly the compiler can automatically synthesize the required interface between reconfigurable portions of the system and the regular portions of the design. several existing models of dynamic reconfiguration from the literature are captured using our type system extension based on sum types. this is especially important in system-on-chip (soc) contexts where a reconfigurable ip block may have to communicate over a non-trivial ip bus like coreconnect&trade;.
incremental placement for layout driven optimizations on fpgas. this paper presents an algorithm to update the placement of logic elements when given an incremental netlist change. specifically, these algorithms are targeted to incrementally place logic elements created by layout-driven circuit restructuring techniques. the incremental placement engine assumes that the restructuring algorithms provide a list of new logic elements along with preferred locations for each of these new elements. it then tries to shift non-critical logic elements in the original placement out of the way to satisfy the preferred location requests. our algorithm considers modern fpga architectures with clustered logic blocksthat have numerous architectural constraints. experiments indicate that our technique produces results of extremely highquality.
statistical technology mapping for parametric yield. the increasing variability of process parameters leads to substantial parametric yield losses due to timing and leakage power constraints. leakage power is especially affected by variability because of its exponential dependence on the highly varying transistor channel length and threshold voltage. this paper describes the new technology mapping algorithm that performs library binding to maximize parametric yield limited both by timing and power constraints. this is the first work that rigorously treats variability in circuit leakage power and delay within logic synthesis. experiments show that moving the concerns about variability into logic synthesis is justified. the results on industrial and public benchmarks indicate that, on avenge, the reduction in stand-by power can be up to 26% and can be as high as 50% for some benchmarks. the reduction is purely due to a more effective decision-making of the mapping algorithm, and is achieved without a timing parametric yield loss. alternatively, the algorithm leads to the delay reduction of up to 17%, with a 10% avenge possible reduction across the benchmarks, for stringent leakage constraints at a fixed yield level. parametric yield at a fixed leakage target can also be substantially increased. in some examples, the statistical mapper leads to a 80% yield at the leakage value for which the deterministic mapper guaranteed only a 50% yield.
interconnect resource-aware placement for hierarchical fpgas. in this paper, we utilize rent's rule as an empirical measure for efficient clustering and placement of circuits on hierarchical fpgas. we show that careful matching of design complexity and architecture resources of hierarchical fpgas can have a positive impact on the overall device area. we propose a circuit placement algorithm based on rent's parameter and show that our clustering and placement techniques can improve the overall device routing area by as much as 21% for the same array size, when compared to a state-of-art fpga placement and routing tool.
extracting rtl models from transistor netlists. this paper addresses the problem of deriving a register-transfer level (rtl) model from a transistor-level circuit. using existing techniques, the transistor-level circuit is converted into a relation that describes the evolution of the signals in the circuit with respect to the simulator clock. this simulation relation is then manipulated to derive the stable behavior of the circuit. given this stable behavior and information about the clocking scheme, we determine if the circuit is combinational, asynchronous or synchronous. for combinational and synchronous circuits we derive an equivalent register-transfer level model. this development enables full-custom circuit designers to use tools that were till now available only to designers working at the gate-level. the algorithm has been successfully used to characterize several custom designs, as well as the entire at&t standard-cell library.
path delay estimation using power supply transient signals: a comparative study using fourier and wavelet analysis. transient signal analysis (tsa) is a parametric device testingtechnique based on the analysis of dynamic (transient) current(i{ddt}) drawn by the core logic from the power supply pads in acmos digital circuit. in previous work, we develop a test procedurethat can be used both to detect signal variations caused bydefects and to obtain delay information in defect free chips. phasespectra of transient signals obtained using discrete fourier transformare shown to track path delays of defect-free chips under awide range of process variations. however, in recent work, wewere able to demonstrate through simulation experiments incorporatingdeep submicron transistor models, a circuit design andpath sensitization scenario in which our existing tsa method isnot able to yield accurate predictions of path delays. more specifically,a circuit composed of two inverter chains constructed withwidely varying transistor sizes was shown to produce path delaysthat were weakly correlated across a set of worst case processmodels. in this paper, an alternative wavelet-based analysis ofi{ddt} waveforms is shown to improve the accuracy of predictingmultiple path delays under these conditions.
fast timing closure by interconnect criticality driven delay relaxation. due to decreasing transistor sizes and increasing clock frequency, interconnect delay is a dominant factor in achieving timing closure in deep sub-micron designs. techniques like wire pipelining and retiming can manage delay of timing critical wires. the latency of the system, however, limits the total pipelining in the design. new techniques are, thus, needed at synthesis stage to consider the effect of critical wires in the design. in this work, we propose a novel intuitive algorithm, critical edge reduction (cer) algorithm, which produces a maximal delay budgeting solution under fixed latency while minimizing the number of critical wires. we also present an in-depth analysis of trade-off between maximum budgeting and critical edge minimization. we implemented our design flow using a set of mediabench data paths on xilinx virtexe fpga devices. using our algorithm, the xilinx place and route tool achieved timing closure, on average, 2.8 times faster than using maximum budgeting. the resulting average clock period using cer algorithm outperforms the one using maximum budgeting by 6%.
the case for retiming with explicit reset circuitry. retiming is often used to optimize synchronous sequential circuits for area or delay or both. if the latches that are retimed have a hardware reset value, the initial state of the circuit must also be retimed, i.e. an initial state must be derived for the retimed circuit. previously, it has been suggested that this can be avoided if the hardware reset signals are represented explicitly. however, it was thought that this adds unnecessary area and restricts the space of possible retimings. in this paper we demonstrate that this is not the case. in addition, we show that this methodology does not require the restriction that all reset signals be asserted at the beginning of circuit operation--- a restriction that was imposed by existing algorithms for determining the retimed initial state. finally we show how our explicit reset (er) framework enables us to retime when some latches may be driven by different hardware resets, and some others may not have any hardware resets. we also consider the case where the resets are asynchronous. we expect these solutions to the "retimed initial state" problem to help increase the practical applicability of retiming.
energy efficient real-time scheduling. real-time scheduling on processors that support dynamic voltage and frequency scaling is analyzed. the slacked earliest deadling first (sedf) algorithm is proposed and it is shown that the algorithm is optimal in minimizing processor energy consumption and maximum lateness. an upper bound on the processor energy savings is also derived. real-time scheduling of periodic tasks is also analyzed and optimal voltage and frequency allocation for a given task set is determined that guarantees schedulability and minimizes energy consumption.
validation and test generation for oscillatory noise in vlsi interconnects. inductance of on-chip interconnects gives rise to signal overshoots and undershoots that can cause logic errors. by considering technology trends, we show that in 0.13 &mgr;m technology such noise in local interconnects embedded in combinational logic can exceed the threshold voltage. we show the impact of such noise on different kinds of circuits. the magnitude of this noise can increase due to process variations. we present an algorithm for generating vectors for validation and manufacturing test to detect logic-value errors caused by inductance induced oscillation. to faciliate the vector generation method, we have derived analytical expressions, as functions of rise and fall times for (i) the magnitude of overshoots and undershoots, and (ii) the settling time, i.e., the time required for the circuit response to settle to a bound close to the final value.
sequential spfds. spfds are a mechanism to express flexibility in boolean networks. introduced by yamashita et al. in the context of fpga synthesis [4], they were extended later to general combinational networks [2]. we introduce the concept of sequential spfds and provide an algorithm to compute them based on a partition of the state bits. the spfds of each component in the partition are used to generate equivalence classes of states. we provide a formal relation between the resulting state classification and the equivalence classes produced by classical state minimization of completely specified machines [6]. the spfds associated with the state bits can be applied for re-encoding the state space. for this, we give an algorithm to re-synthesize the sequential circuit using sequential spfds and the new state re-encoding.
topologically constrained logic synthesis. spfds, a mechanism for expressing flexibility during logic synthesis, were first introduced for fpga synthesis. they were then extended to general, combinational boolean networks and later the concept of sequential spfds was introduced. in this paper, we explore the idea of using spfds for functional decomposition. a new type of functional decomposition called topologically constrained decomposition is introduced. an algorithm is provided for solving this problem using spfds. preliminary experimental results are encouraging and indicate the feasibility of the approach. a scheme is also presented for generating instances of the topologically constrained decomposition problem.
statistical gate sizing for timing yield optimization. variability in the chip design process has been relatively increasing with technology scaling to smaller dimensions. using worst case analysis for circuit optimization severely over-constrains the system and results in solutions with excessive penalties. statistical timing analysis and optimization have consequently emerged as a refinement of the traditional static timing approach for circuit design optimization. in this paper, we propose a statistical gate sizing methodology for timing yield improvement. we build statistical models for gate delays from library characterizations at multiple process corners and operating conditions. statistical timing analysis is performed, which drives gate sizing for timing yield optimization. experimental results are reported for the iscas and mcnc benchmarks. in addition, we provide insight into statistical properties of gate delays for a given technology library which intuitively explains when and why statistical optimization improves over static timing optimization.
gate sizing for crosstalk reduction under timing constraints by lagrangian relaxation. this work presents a post-route, timing-constrained gate-sizing algorithm for crosstalk reduction. gate-sizing has emerged as a practical and feasible method to reduce crosstalk in deep sub-micron vlsi circuits. it is however critical to ensure that the timing constraints of the circuit are not violated after sizing. we present an iterative gate-sizing algorithm for crosstalk reduction based on lagrangian relaxation that optimizes area and power while ensuring that the given timing constraints are met. experimental results demonstrating the effectiveness of the algorithm are reported for the iscas benchmarks and other large circuits with comparisons to an alternative design methodology.
a unified framework for statistical timing analysis with coupling and multiple input switching. as technology scales to smaller dimensions, increasing process variations, coupling induced delay variations and multiple input switching effects make timing verification extremely challenging. in this paper, we establish a theoretical framework for statistical timing analysis with coupling and multiple input switching. we prove the convergence of our proposed iterative approach and discuss implementation issues under the assumption of a gaussian distribution for the parameters of variation. a statistical timer based on our proposed approach is developed and experimental results are presented for the is-cas benchmarks. we juxtapose our timer with a single pass, non iterative statistical timer that does not consider the mutual dependence of coupling with timing and another statistical timer that handles coupling deterministically. monte carlo simulations reveal a distinct gain (up to 24%) in accuracy by our approach in comparison to the others mentioned.
implicit treatment of substrate and power-ground losses in return-limited inductance extraction. full-wave analysis, based on rigorous solution of the differential or integral form of maxwell's equations, is too slow for all but the smallest designs. traditional on-chip extraction engines are, therefore, being pushed to extract inductance and provide accurate high-frequency interconnect modelling while maintaining computational efficiency and capacity. this paper describes further accuracy-improving enhancements to the commecial full-chip rlck extraction engine, assura rlcx[1], based on the return-limited inductance formulation. specifically, we incorporate substrate losses due to eddy currents and power-ground losses while, based on design-driven assumptions, avoiding explicit extraction of the power-ground and substrate. results are validated on small testcases where comparison with full-wave solution is practical.
delay fault coverage: a realistic metric and an estimation technique for distributed path delay faults. in this paper, we propose a new and realistic definition of delay fault coverage, based on the percentage of fabricated faulty chips which can be detected as faulty by a given test set. this metric takes into account the probability distribution of delay fault sizes caused by fabrication process effects, as opposed to previously defined metrics which have been based primarily on the percentage of faults tested. in addition to proposing a realistic delay fault coverage metric, we also present a computationally viable scheme for using this metric to estimate the coverage of any given test set for a class of path delay faults caused by distributed fabrication process variations. we use the results for the iscas'89 benchmark circuits to demonstrate wide discrepancies between distributed path delay fault coverage estimates for robust test sets obtained using our realistic definition, and the ones obtained by using the traditional notion of coverage as the percentage of paths tested.
timing analysis based on primitive path delay fault identification. we present a novel timing analysis mechanism which is based on identifying primitive path delay faults (primitive pdfs) in a circuit. we show that this approach gives the exact maximum delay of the circuit under the floating mode of operation assumption. our timing analysis approach provides a framework where component delay correlations and signal correlations arising from fabrication process, signal propagation, and signal interaction effects can be handled very accurately. under these effects, timing analysis using previously reported floating mode timing analyzers, e.g., viability, trued-f etc., is very pessimistic. our timing analysis approach based on primitive pdf identification is also more efficient than conventional floating mode path sensitization analysis mechanisms in situations where critical paths need to be re-identified due to component delay speedup (e.g., post-layout delay optimization). we demonstrate the applicability of our timing analysis approach for a variety of benchmark circuits, and demonstrate the pessimism of conventional floating mode timing analysis approaches in accounting for signal propagation effects.