waashk/dblp huggingface dataset:
placement driven retiming with a coupled edge timing model. retiming is a widely investigated technique for performance optimization. it performs powerful modifications on a circuit netlist. however, often it is not clear, whether the predicted performance improvement will still be valid after placement has been performed. this paper presents a new retiming algorithm using a highly accurate timing model taking into account the effect of retiming on capacitive loads of single wires as well as fanout systems. we propose the integration of retiming into a timing-driven standard cell placement environment based on simulated annealing. retiming is used as an optimization technique throughout the whole placement process. the experimental results show the benefit of the proposed approach. in comparison with the conventional design flow based on standard feas our approach achieved an improvement in cycle time of up to 34% and 17% on the average.
cell replication and redundancy elimination during placement for cycle time optimization. this paper presents a new timing driven approach for cell replication tailored to the practical needs of standard cell layout design. cell replication methods have been studied extensively in the context of generic partitioning problems. however, until now it has remained unclear what practical benefit can be obtained from this concept in a realistic environment for timing driven layout synthesis. therefore, this paper presents a timing driven cell replication procedure, demonstrates its incorporation into a standard cell placement and routing tool and examines its benefit on the final circuit performance in comparison with conventional gate or transistor sizing techniques. furthermore, we demonstrate that cell replication can deteriorate the stuck-at fault testability of circuits and show that stuck-at redundancy elimination must be integrated into the placement procedure. experimental results demonstrate the usefulness of the proposed methodology and suggest that cell replication should be an integral part of the physical design flow complementing traditional gate sizing techniques.
state transformation in event driven explicit simulation. this paper presents a general method for incorporating state transformation in event driven explicit simulation. one inherent assumption in this type of simulation algorithm is the state independence, which allows the algorithm to process the states independently in an event driven manner at the transistor level. numerical problems arise when an inappropriate state representation of the circuit, in which the states are not truly independent, is chosen. in principle, any similarity transformation of the state equation can be employed to transform the circuit into a more convenient state space for numerical solution. this paper develops a systematic scheme to derive an appropriate state transformation, and to incorporate the state transformulation in such a way to maintain the efficiency of event driven explicit simulation algorithms.
transient sensitivity computation for transistor level analysis and tuning. this paper presents a general method for computing transient sensitivities using both the direct and adjoint methods in event driven controlled explicit simulation algorithms that employ piecewise linear device models. this transient sensitivity capability is intended to be used in a simulation environment for transistor level analysis and tuning. results demonstrate the efficiency and accuracy of the proposed techniques. examples are also presented to illustrate how the transient sensitivity capability is used in timing characterization and circuit tuning.
transition-by-transition fsm traversal for reachability analysis in bounded model checking. in bounded model checking (bmc)-based verification flows lack of reachability constraints often leads to false negatives. at present, it is daily practice of a verification engineer to identify the missing reachability constraints by manually inspecting the design code and by analyzing counterexamples. this, unfortunately, requires a lot of effort and is prone to errors. we propose an algorithm to determine reachability constraints automatically. the proposed approach applies to a design style where the operation of the design is controlled by a main fsm which can easily be extracted from the rtl description of the circuit. the algorithm decomposes and analyzes the state space of the circuit by considering transitions of the main fsm. experimental results show that the proposed method can considerably reduce the manual work of verification engineers.
dynamic data-bit memory built-in self- repair. in modern socs, embedded memories occupythe largest part of the chip area and include an evenlarger amount of active devices. as memories aredesigned very tightly to the limits of the technology theyare more prone to failures than logic. thus, theyconcentrate the large majority of defects and affect circuityield dramatically. thus, built-in self-repair is gainingsignificant importance. this work presents a dynamicmemory built-in self-repair schemer acting on the data-bitlevel. it allows reducing the size of the repairable units,or in other words, it allows using a single spare unit forrepairing faults affecting several regular units. as aconsequence, it repairs multiple faults by means of lowhardware cost.
robust automated synthesis methodology for integrated spiral inductors with variability. in order to synthesize spiral inductor designs to meet stringent design requirements, fundamental trade-offs in the design space must be analyzed and exploited. in this paper, we develop a robust automated synthesis methodology to efficiently generate spiral inductor designs using multi-objective optimization techniques and surrogate functions to approximate pareto surfaces in the design space. using our synthesis methodology, we also demonstrate how to reduce the impact of process variation and other sources of modeling error on spiral inductors. our results indicate that our synthesis methodology efficiently optimizes inductor designs based on the application's design requirements with an improvement of up to 51% in key inductor design constraints while reducing the impact of process and model variations.
high capacity and automatic functional extraction tool for industrial vlsi circuit designs. in this paper we present an advanced functional extraction tool for automatic generation of high-level rtl from switch-level circuit netlist representation. the tool is called fev-extract and is part of a comprehensive formal equivalence verification (fev) system developed at intel to verify modern microprocessor designs. fev-extract employs a powerful hierarchical analysis procedure, and advanced and generic algorithms for automatic recognition of logical primitives, to cope with variety of circuit design styles and their complexity. logic equations are then extracted to generate a behavioral rtl model described in industrial standard hdl languages, to be used in the formal equivalence verification, logic simulation, synthesis and testability flows.
exact two-level minimization of hazard-free logic with multiple-input changes. a method for exact hazard-free logic minimization of boolean functions is described. given an incompletely specified boolean function, the method produces a minimal sum-of-products implementation which is hazard-free for a given set of multiple-input changes, if such a solution exists. the method is a constrained version of the quine-mccluskey algorithm. it has been automated and applied to a number of examples. results are compared with results of a comparable non-hazard-free method (espresso-exact). overhead due to hazard elimination is shown to be negligible
prima: passive reduced-order interconnect macromodeling algorithm. this paper describes prima, an algorithm for generating provably passive reduced order n-port models for rlc interconnect circuits. it is demonstrated that, in addition to requiring macromodel stability, macromodel passivity is needed to guarantee the overall circuit stability once the active and passive driver/load models are connected. prima extends the block arnoldi technique to include guaranteed passivity. moreover, it is empirically observed that the accuracy is superior to existing block arnoldi methods. while the same passivity extension is not possible for mpvl, we observed comparable accuracy in the frequency domain for all examples considered. additionally a path tracing algorithm is used to calculate the reduced order macromodel with the utmost efficiency for generalized rlc interconnects.
practical considerations for passive reduction of rlc circuits. krylov space methods initiated a new era for rlc circuit model order reduction. although theoretically well-founded, these algorithms can fail to produce useful results for some types of circuits. in particular, controlling accuracy and ensuring passivity are required to fully utilize these algorithms in practice. in this paper we propose a methodology for passive reduction of rlc circuits based on extensions of prima, that is both broad and practical. this work is made possible by uncovering the algebraic connections between this passive model order reduction algorithm and other krylov space methods. in addition, a convergence criteria based on an error measure for prima is presented as a first step towards intelligent order selection schemes. with these extensions and error criterion, examples demonstrate that accurate approximations are possible well into the rf frequency range even with expansions about s=0.
application-specific network-on-chip architecture customization via long-range link insertion. networks-on-chip (nocs) represent a promising solution to complex on-chip communication problems. the noc communication architectures considered so far are based on either completely regular or fully customized topologies. in this paper, we present a methodology to automatically synthesize an architecture where a few application-specific long-range links are inserted on top of a regular mesh network. this way, we can better exploit the benefits of both complete regularity and partial customization. indeed, our experimental results show that inserting application-specific long-range links significantly increases the critical traffic workload at which the network state transits from a free to a congested regime. this, in turn, results in a significant reduction in the average packet latency and a major improvement in the network achievable throughput.
fast seed computation for reseeding shift register in test pattern compression. solving a system of linear equations has been widely used to compute seeds for lfsr reseeding to compress test patterns. however, as chip size is growing, solving linear equations requires a large number of computations that is proportional to n3. this paper proposes a new scan chain architecture and algorithm so that the order of computation is proportional to the number of scan cells in a chip. the new architecture is a methodology change that does not require complex design-for-testability (dft) as proposed in the previous techniques. instead of solving linear equations, the proposed new seed computation algorithm topologically determines seeds for test vectors. the compression ratio might be slightly lower than the other approaches, but the proposed approach can handle larger designs in a reasonable amount of time. computation analysis shows that, for 1 million scan cell design, if we assume it takes 1 msec for the proposed technique to compute seeds, it would take more than 14 minutes for other techniques that solve linear equations.
comprehensive lower bound estimation from behavioral descriptions. in this paper, we present a comprehensive technique for lower bound estimation (lbe) of resources from behavioral descriptions. previous work has focused on lbe techniques that use very simple cost models which primarily focus on the functional unit resources. our cost model accounts for storage resources in addition to functional resources. our timing model uses a finer granularity that permits the modeling of functional unit, register and interconnect delays. we tested our lbe technique for both functional unit and storage requirements on several high-level synthesis benchmarks and observed near-optimal results.
a statistical gate-delay model considering intra-gate variability. this paper proposes a model for calculating statistical gate-delayvariation caused by intra-chip and inter-chip variability. as thevariation of individual gate delays directly influences the circuit-delayvariation, it is important to characterize each gate-delay variationaccurately. furthermore, as every transistor in a gate affectsthe transient characteristics of the gate, it is also necessary to considerthe intra-gate variability in the model of gate-delay variation.this effect is not captured in existing statistical delay analyses. theproposed model considers the intra-gate variability through the introductionof sensitivity constants. the accuracy of the model isevaluated, and some simulation results for circuit delay variationare presented.
buffered steiner tree construction with wire sizing for interconnect layout optimization. this paper presents an efficient algorithm for buffered steiner tree construction with wire sizing. given a source and n sinks of a signal net, with given positions and a required arrival time associated with each sink, the algorithm finds a steiner tree with buffer insertion and wire sizing so that the required arrival time (or timing slack) at the source is maximized. the unique contribution of our algorithm is that it performs steiner tree construction, buffer insertion, and wire sizing simultaneously with consideration of both critical delay and total capacitance minimization by combining the performance-driven a-tree construction and dynamic programming based buffer insertion and wire sizing, while tree construction and the other delay minimization techniques were carried out independently in the past. experimental results show the effectiveness of our approach.
an exact gate assignment algorithm for tree circuits under rise and fall delays. in most libraries, gate parameters such as the pin-to-pin intrinsic delays, load-dependent coefficients, and input pin capacitances have different values for rising and falling signals. the performance optimization algorithms, however, assume a single value for each parameter.it is known that under the load-independent delay model, the gate assignment (or resizing) problem is solvable in time polynomial in the circuit size when a single value is assumed for each parameter [5]. in the presence of different rise and fall parameter values, this problem was recently shown to be np-complete even for chain and tree topology circuits under the simple load-independent delay model [8]. in this paper, we propose a dynamic programming algorithm for solving this problem exactly in pseudo-polynomial time for tree circuits. more specifically, we show that the problem can be solved in time proportional to the size of the tree circuit, the number of choices available in the library for each gate, and the delay of the circuit. to the best of our knowledge, this is the first pseudo-polynomial exact algorithm for the gate assignment problem for trees in the presence of different rise and fall delays. we present a straightforward way of extending this algorithm to general directed acyclic graphs. we present experimental results on a set of benchmark problems using a standard commercial library and show that our algorithm generates provably optimum delays for 72 out of 76 circuits. we also compare our technique with two approaches traditionally used to solve this problem in the industry & academia and show that it is slightly better than these two. interestingly, both traditional approaches also yield delays not far from the optimum.
a flexibility aware budgeting for hierarchical flow timing closure. we present a new block budgeting algorithm which speeds up timing closure in timing driven hierarchical flows. after a brief description of the addressed flow, block budgeting challenges are detailed. then, we explain why existing budgeting approaches are not adapted to fulfil these challenges. a new block budgeting algorithm is proposed. in order to derive relevant block constraints, this algorithm analyzes the design flexibility. this flexibility aware budgeting (fab) approach is then compared to some previous ones. experiments based on commercial eda tools and real designs show up to 55 % reduction in hierarchical flow run time and lead to a good flow timing closure.
impact of systematic spatial intra-chip gate length variability on performance of high-speed digital circuits. using data collected from an actual state-of-the-art fabrication facility, we conducted a comprehensive characterization of an advanced 0.18&mu;m cmos process. the measured data revealed significant systematic, rather than random, spatial intra-chip variability of mos gate length, leading to large circuit path delay variation. the critical path value of a combinational logic block varies by as much as 17%, and the global skew is increased by 8%. thus, a significant timing error (&sim;25%) and performance loss takes place if variability is not properly addressed. we derive a model, which allows estimating performance degradation for the given circuit and process parameters. analysis shows that the spatial, rather than proximity-dependent, systematic lgate variability is the main cause of large circuit speed degradation. the degradation is worse for the circuits with a larger number of critical paths and shorter average logic depth. we propose a location-dependent timing analysis methodology that allows to mitigate the detrimental effects of lgate variability, and developed a tool linking the layout-dependent spatial information to circuit analysis. we discuss the details of the practical implementation of the methodology, and provide the guidelines for managing the design complexity.
moment-based power estimation in very deep submicron technologies. the significant power optimization possibilities in the early stagesof the design flow advice the use of energy evaluation techniquesat high levels of abstraction. with this aim, the present work addressesthe estimation of the energy consumption in very deep submicrontechnologies. using the characterization of the probabilitydensity function with a projection in an orthogonal polynomialbase, and a symbolic propagation mechanism, a technique is presentedto estimate the dynamic and static power consumption indigital systems. the proposed approach has been validated withcircuits and excitations from realistic applications. comparisonswith reference transistor and bit level simulations are reported inorder to asses the the accuracy of the technique.
length-matching routing for high-speed printed circuit boards. as the clock frequencies used in industrial applications increase,the timing requirements imposed on routing problems becometighter. so, it becomes important to route the nets within tight minimumand maximum length bounds. although the problem of routingnets to satisfy maximum length constraints is a well-studiedproblem, there exists no sophisticated algorithm in the literaturethat ensures that minimum length constraints are also satisfied. inthis paper, we propose a novel algorithm that effectively incorporatesthe min-max length constraints into the routing problem. ourapproach is to use a lagrangian relaxation framework to allocateextra routing resources around nets simultaneously during routingthem. we also propose a graph model that ensures that all theallocated routing resources can be used effectively for extendinglengths. our routing algorithm automatically prioritizes resourceallocation for shorter nets, and length minimization for longer netsso that all nets can satisfy their min-max length constraints. ourexperiments demonstrate that this algorithm is effective even in thecases where length constraints are tight, and the layout is dense.
simultaneous escape routing and layer assignment for dense pcbs. as die sizes are shrinking, and circuit complexities are increasing, the pcb routing problem becomes more and more challenging. traditional routing algorithms can not handle these challenges effectively, and many high-end designs in the industry require manual routing efforts. in this paper, we propose a problem decomposition that distinguishes routing within dense components from routing in the intermediate area. in particular, we propose an effective methodology to find the escape routing solution for multiple components simultaneously such that the number of crossings in the intermediate area is minimized. for this, we model the problem as a longest path with forbidden pairs (lpfp) problem, and propose two algorithms for it. the first is an exact polynomial-time algorithm that is guaranteed to find the maximal planar routing solution on one layer. the second is a randomized algorithm that has good scalability characteristics for large circuits. then we use these algorithms to assign the maximal subset of planar nets to each layer, and then distribute the remaining nets at the end. we demonstrate the effectiveness of these algorithms through experiments on industrial circuits.
a provably good algorithm for high performance bus routing. as the clock frequencies used in industrial applications increase, the timing requirements on routing problems become tighter, and current routing tools can not successfully handle these constraints any more. we focus on the high-performance single-layer bus routing problem, where the objective is to match the lengths of all nets belonging to each bus. an effective approach to solve this problem is to allocate extra routing resources around short nets during routing; and use those resources for length extension afterwards. we first propose a provably optimal algorithm for routing nets with min-area max-length constraints. then, we extend this algorithm to the case where minimum constraints are given as exact length bounds. we also prove that this algorithm is optimal within a constant factor. both algorithms proposed are also shown to be scalable for large circuits, since the respective time complexities are o(a) and o(a log a), where a is the area of the intermediate region between chips.
an escape routing framework for dense boards with high-speed design constraints. shrinking transistor sizes, increasing circuit complexities, and high clock frequencies bring new board routing challenges that cannot be handled effectively by traditional routing algorithms. many high-end designs in the industry today require manual routing efforts, which increases the design cycle times considerably. in this paper, we propose an escape routing algorithm to route nets within multiple dense components simultaneously so that the number of crossings in the intermediate area is minimized. we also show how to handle high-speed design constraints within the framework of this algorithm. experimental comparisons with a recently proposed algorithm (ozdal and wong, 2004) show that our algorithm reduces the via requirements of industrial test cases on average by 39%.