waashk/dblp huggingface dataset:
combinational equivalence checking through function transformation. circuits can be simplified for combinational equivalence checking by transforming internal functions, while preserving their ranges. in this paper, we investigate how to effiectively apply the idea to improve equivalence checking. we propose new heuristics to identify groups of nets in a cut, and elaborate detailed aspects of the new equivalence checking method. with a given miter, we identify a group of nets in a cut and transform the function of each net into a more compact representation with less variables. these new compact parametric representations preserve the range of nets as well as of the cut. this transformation significantly reduces the size of intermediate bdds and enables the verification to be conclusive for many designs which state-of-the-art equivalence checkers fail to verify. iterative groupings and transformations are performed until no grouping is possible for a cut. then we proceed to the next cut and continue until the compare point is reached. our experimental results show the effiectiveness of our strategy and new grouping heuristics on the new method.
asymptotic probability extraction for non-normal distributions of circuit performance. while process variations are becoming more significant with each new ic technology generation, they are often modeled via linear regression models so that the resulting performance variations can be captured via normal distributions. nonlinear (e.g. quadratic) response surface models can be utilized to capture larger scale process variations; however, such models result in non-normal distributions for circuit performance which are difficult to capture since the distribution model is unknown. in this paper we propose an asymptotic probability extraction method, apex, for estimating the unknown random distribution when using nonlinear response surface modeling. apex first uses a binomial moment evaluation to efficiently compute the high order moments of the unknown distribution, and then applies moment matching to approximate the characteristic function of the random circuit performance by an efficient rational function. a simple statistical timing example and an analog circuit example demonstrate that apex can provide better accuracy than monte carlo simulation with 10 samples and achieve orders of magnitude more efficiency. we also show the error incurred by the popular normal modeling assumption using standard ic technologies.
formulae and applications of interconnect estimation considering shield insertion and net ordering. it has been shown recently that simultaneous shield insertion and net ordering (called sino/r as only random shields are used) provides an area-efficient solution to reduce the rlc noise. in this paper, we first develop simple formulae with errors less than 10% to estimate the number of shields in the min-area sino/r solution. in order to accommodate pre-routed p/g wires that also serve as shields, we then formulate two new sino problems: sino/spr and sino/upg, and propose effective and efficient two-phase algorithms to solve them. compared to the existing dense wiring fabric scheme, the resulting sino/spr and sino/upg schemes maintain the regularity of the p/g structure, have negligible penalty on noise and delay variation, and reduce the total routing area by up to 42% and 36%, respectively. further, we develop various pre-layout estimation formulae for shielding areas and optimal p/g structures under different routing styles. these formulae can be readily used to guide global routing and high-level design decisions.
performance estimation of embedded software with instruction cache modeling. embedded systems generally interact with the outside world. thus, some real-time constraints may be imposed on the system design. verification of these constraints requires computing a tight upper bound on the worst case execution time (wcet) of a hardware/software system. the problem of bounding wcet is particularly difficult on modern processors, which use cache-based memory systems that vary memory access time significantly. this must be accurately modeled in order to tightly bound wcet. existing approaches either search all possible program paths, an intractable problem, or they use pessimistic assumptions to limit the search space. in this paper we present a far more effective and accurate method for modeling instruction cache activity and computing a tight bound on wcet. it is implemented in the program \texttt{cinderella}. we present some preliminary results of using this tool on sample embedded programs.
efficient full-chip thermal modeling and analysis. the ever-increasing power consumption and packaging density of integrated systems creates on-chip temperatures and gradients that can have a substantial impact on performance and reliability. while it is conceptually understood that a thermal equivalent circuit can be constructed to characterize the temperature gradients across the chip, direct and iterative solutions of the corresponding 3d equations are often intractable for a full-chip analysis. multigrid accelerated iterative methods can be applied to solve the equivalent circuit problem that is provably symmetric positive definite; however, explicitly building the matrix problem is intractable for most full-chip problems. in this work we present a multigrid iterative approach for the full-chip thermal analysis which does not require explicit construction of the equivalent circuit matrix. we propose specific multigrid treatments to cope with the strong anisotropy of the full-chip thermal problem that is created by the vast difference in material thermal properties and chip geometries. importantly, we demonstrate that only with careful thermal modeling assumptions and appropriate choices for grid hierarchy, multigrid operators and smoothing steps across grid points, can we accurately and efficiently analyze a full-chip thermal problem. experimental results demonstrate the efficacy of the proposed multigrid methodology. our prototyped thermal simulator is able to solve a steady-state problem with more than 10 million unknowns in 125 cpu seconds with a peak memory usage of 231 mega bytes.
a probabilistic timing approach to hot-carrier effect estimation. an approach for estimating hot-carrier induced degradation in mos transistor circuits is presented. the approach uses probabilistic timing simulation techniques to estimate the cumulative effects of all possible inputs on hot-carrier effect (hce) degradation in each transistor in the circuit in a single run rather than using exhaustive or monte carlo simulations. the approach has been implemented in a general-purpose simulator and tested on a number of typical examples and benchmarks
managing power and performance for system-on-chip designs using voltage islands. this paper discusses voltage islands, a system architecture and chip implementation methodology, that can be used to dramatically reduce active and static power consumption for system-on-chip (soc) designs. as technology scales for increased circuit density and performance, the need to reduce power consumption increases in significance as designers strive to utilize the advancing silicon capabilities. the consumer product market further drives the need to minimize chip power consumption.effective use of voltage islands for meeting soc power and performance requirements, while meeting time to market (tat) demands, requires novel approaches throughout the design flow as well as special circuit components and chip powering structures. this paper outlines methods being used today to design voltage islands in a rapid-tat product development environment, and discusses the need for industry eda advances to create an industry-wide voltage island design capability.
efficient exploration of the soc communication architecture design space. in this paper, we present a methodology and efficient algorithms for the design of high-performance system-on-chip communication architectures. our methodology automatically and optimally maps the various communications between system components onto a target communication architecture template that can consist of an arbitrary interconnection of shared or dedicated channels. in addition, our techniques simultaneously configure the communication protocols of each channel in the architecture in order to optimize system performance.we motivate the need for systematic exploration of the communication architecture design space, and highlight the issues involved through illustrative examples. we present a methodology and algorithms that address these issues, including the size and complexity of the design space. we present experimental results on example systems, including a cell forwarding unit of an atm switch, that demonstrate the benefits of using the proposed techniques. experimental results indicate that our techniques are successful in achieving significant improvements in system performance over conventional communication architectures (observed speedups over typical architectures such as single shared buses averaged 53%). moreover, we demonstrate that our design space exploration methodology and optimization algorithms are efficient (low cpu times), underlining their usefulness as part of any system design flow.
adapative error protection for energy efficiency. with dramatic scaling in feature sizes, noise resilience is becomingone of the most important design parameters, similar to performanceand energy efficiency. noise resilience is particularly problematicin long on-chip buses of complex single chip systems suchas on-chip multiprocessors. while one might opt to employ a verypowerful error protection scheme, this may not be very energy efficientas noise behavior typically varies over time. in this paper, wepropose an adaptive error protection scheme for energy efficiency,where the type of the coding scheme is modulated dynamically.the idea behind this strategy is to monitor the dynamic variationsin noise behavior and use the least powerful (and hence the mostenergy efficient) error protection scheme required to maintain theerror rates below a pre-set threshold. our detailed experimental resultsobtained through simulation show that this adaptive strategyachieves the same level of error protection as the most powerfulstrategy experimented, without experiencing the latter's energy inefficiency.based on our results, we recommend system designersto adopt adaptive protection schemes in environments where bothenergy and reliability are important.
fast performance analysis of bus-based system-on-chip communication architectures. this paper addresses the problem of efficient and accurate performance analysis to drive the exploration and design of bus-based system-on-chip (soc) communication architectures. our technique fills a gap in existing techniques for system-level performance analysis, which are either too slow to use in an iterative communication architecture design framework (e.g., simulation of the complete system), or are not accurate enough to drive the design of the communication architecture (e.g., techniques that perform a &ldquo;static&rdquo; analysis of the system performance). the proposed system-level performance analysis technique consists of (i) initial co-simulation performed after iiw/sw partitioning and mapping, with the communication between components modeled in an abstract manner (e.g., as events or data transfers), (ii) extraction of abstracted symbolic traces, represented as a bus and synchronization event (bse) graph, that captures the activity of the various system components and their communication over time, and (iii) manipulation of the bse graph using the bus parameters, to derive the behavior of the system accounting for effects of the bus architecture. we present experimental results on several example systems, including a tcp/ip network interface card sub-system. the results indicate that our performance estimation technique is over two orders of magnitude faster than performing a complete system simulation, while being very accurate (within 2.2% of performance estimates derived from accurate hw/sw co-simulation).
efficient model reduction of interconnect via approximate system gramians. krylov-subspace based methods for generating low-order models of complicated interconnect are extremely effective, but there is no optimality theory for the resulting models. alternatively, methods based on truncating a balanced realization (tbr), in which the observability and controllability gramians have been diagonalized, do have an optimality property but are too computationally expensive to use on complicated problems. in this paper we present a method for computing reduced-order models of interconnect by projection via the orthogonalized union of the approximate dominant eigenspaces of the system's controllability and observability gramians. the approximate dominant eigenspaces are obtained efficiently using an iterative lyapunov equation solver, vector adi, which requires only linear matrix-vector solves. a spiral inductor and a transmission line example are used to demonstrate that the new method accurately approximates the tbr results and gives much more accurate wideband models than krylov subspace-based moment matching methods.
interval-valued reduced order statistical interconnect modeling. we show how recent advances in the handling of correlated interval representations of range uncertainty can be used to predict the impact of statistical manufacturing variations on linear interconnect. we represent correlated statistical variations in rlc parameters as sets of correlated intervals, and show how classical model order reduction methods - awe and prima - can be re-targeted to compute interval-valued, rather than scalar-valued reductions. by applying a statistical interpretation and sampling to the resulting compact interval-valued model, we can efficiently estimate the impact of variations on the original circuit. results show the technique can predict mean delay with errors between 5-10%, for correlated rlc parameter variations up to 35%.
performance-centering optimization for system-level analog design exploration. in this paper we propose a novel analog design optimization methodology to address two key aspects of top-down system-level design: (1) how to optimally compare and select analog system architectures in the early phases of design; and (2) how to hierarchically propagate performance specifications from system level to circuit level to enable independent circuit block design. importantly, due to the inaccuracy of early-stage system-level models, and the increasing magnitude of process and environmental variations, the system-level exploration must leave sufficient design margin to ensure a successful late-stage implementation. therefore, instead of minimizing a design objective function, and thereby converging on a constraint boundary, we apply a novel performance centering optimization. our proposed methodology centers the analog design in the performance space, and maximizes the distance to all constraint boundaries. we demonstrate that this early-stage design margin, which is measured by the volume of the inscribed ellipsoid lying inside the performance constraints, provides an excellent quality measure for comparing different system architectures. the efficacy of our performance centering approach is shown for analog design examples, including a complete clock data recovery system design and implementation.
routability-driven placement and white space allocation. we present a congestion-driven placement flow. first, we consider in the global placement stage the routing demand to replace cells in order to avoid congested regions. then we allocate appropriate amounts of white space into different regions of the chip according to the congestion map. finally, a detailed placer is applied to legalize placements while preserving the distributions of white space. experimental results show that our placement flow can achieve the best routability with the shortest routed wirelength among all publicly available placement tools. moreover, our white space allocation approach can significantly improve the routabilities of placements generated by other placement tools.
power-optimal simultaneous buffer insertion/sizing and wire sizing. this paper studies the problems of minimizing power dissipationof an interconnect wire by simultaneously considering buffer insertion/sizing and wire sizing (bisws). we consider two cases, namely minimizing power dissipation with optimal delay constraints, and minimizing power dissipation with a given delay penalty.we derive closed form optimal solutions for both cases. theseclosed form solutions can be used to efficiently estimate the powerdissipation in the early stages of the vlsi designs. we observe thatthe power dissipation can be much different even with the sameoptimal delay.
automated oscillator macromodelling techniques for capturing amplitude variations and injection locking. we present a method for extracting comprehensive amplitude and phase macromodels of oscillators from their circuit descriptions. the macromodels are based on combining a scalar, nonlinear phase equation with a small linear time-varying system to capture slowly-dying amplitude variations. the comprehensive macromodels are able to correctly predict oscillator response in the presence of interference at far lower computational cost than that of full spice-level simulation. we also present an efficient numerical method for capturing injection locking in oscillators, thereby improving on the classic technique of adler (1946) in terms of accuracy and applicability to any kind of oscillator. we demonstrate the proposed techniques on lc and ring oscillators, comparing results from the macromodels against full spice-like simulation. numerical experiments demonstrate speed tips of orders of magnitude, while retaining excellent accuracy.
vdd programmability to reduce fpga interconnect power. power is an increasingly important design constraint for fpgas in nanometer technologies. because interconnect power is dominant in fpgas, we design vdd-programmable interconnect fabric to reduce fpga interconnect power. there are three vdd states for interconnect switches: high vdd, low vdd and power-gating. we develop a simple design flow to apply high vdd to critical paths and low vdd to non-critical paths and to power gate unused interconnect switches. we carry out a highly quantitative study by placing and routing benchmark circuits in 100 nm technology to illustrate the power saving. compared to single-vdd fpgas with optimized but nonprogrammable vdd level for the same target clock frequency, our new fpga fabric on average reduces interconnect power by 56.51% and total fpga power by 50.55%. due to the highly low utilization rate of routing switches, majority of the power reduction is achieved by power gating unused routing buffers. in contrast, recent work that considers vdd programmability only for logic fabric reduces total fpga power merely by 14.29%. to the best of our knowledge, it is the first in-depth study on vdd programmability for fpga interconnect power reduction.
whirlpool plas: a regular logic structure and their synthesis. a regular circuit structure called a whirlpool pla (wpla) is proposed. it is suitable for the implementation of finite state machines as well as combinational logic. a wpla is logically a four-level boolean nor network. by arranging the four logic arrays in a cycle, a compact layout is achieved. doppio-espresso, a four-level logic minimization algorithm is developed for wpla synthesis. no technology mapping, placement or routing is necessary for the wpla. area and delay trade-off is absent, because these two goals are usually compatible in wpla synthesis.
wavesched: a novel scheduling technique for control-flow intensive behavioral descriptions. in this paper, we present a novel scheduling algorithm targeted towards minimizing the average execution time of control-flow intensive behavioral descriptions. our algorithm uses a cdfg model, which preserves the parallelism inherent in the application. it explores previously unexplored regions of the solution space by its ability to overlap the schedules of independent iterative constructs, whose bodies share resources. it also incorporates well known optimization techniques like loop unrolling in a natural fashion. this is made possible by a general loop-handling technique, which we have devised. application of the algorithm to several common benchmarks demonstrates up to 4.8-fold improvement in expected schedule length over existing scheduling algorithms, without paying a price in terms of the best- and worst-case schedule lengths required to execute the behavioral description (in fact, frequently, the best/worst-case schedule lengths are also better for our algorithm).
parameterized interconnect order reduction with explicit-and-implicit multi-parameter moment matching for inter/intra-die variations. in this paper we propose a novel parameterized interconnect order reduction algorithm, core, to efficiently capture both inter-die and intra-die variations. core applies a two-step explicit-and-implicit scheme for multiparameter moment matching. as such, core can match significantly more moments than other traditional techniques using the same model size. in addition, a recursive arnoldi algorithm is proposed to quickly construct the krylov subspace that is required for parameterized order reduction. applying the recursive arnoldi algorithm significantly reduces the computation cost for model generation. several rc and rlc interconnect examples demonstrate that core can provide up to 10/spl times/ better modeling accuracy than other traditional techniques, while achieving smaller model complexity (i.e. size). it follows that these interconnect models generated by core can provide more accurate simulation result with cheaper simulation cost, when they are utilized for gate-interconnect co-simulation.
selecting partial scan flip-flops for circuit partitioning. this paper presents a new method of selecting scan flip-flops (ffs) in partial scan designs of sequential circuits. scan ffs are chosen so that the whole circuit can be partitioned into many small subcircuits which can be dealt with separately by a test pattern generator. this permits easy automatic test pattern generation for arbitrarily large sequential circuits. algorithms of selecting scan ffs to allow such partitioning and of scheduling tests for subcircuits are given. experimental results show that the proposed method makes it possible to generate test patterns for extra large sequential circuits which previous approaches cannot deal with.
behavioral modeling of analog circuits by wavelet collocation method. in this paper, we develop a wavelet collocation method with nonlinear companding for behavioral modeling of analog circuits. to construct the behavioral models, the circuit is first partitioned into building blocks and the input-output function of each block is then approximated by wavelets. as the blocks are mathematically represented by sets of simple wavelet basis functions, the computation cost for the behavioral simulation is significantly reduced. the proposed method presents several merits compared with those conventional techniques. first, the algorithm for expanding input-output functions by wavelets is a general-purpose approach, which can be applied in automatically modeling of different analog circuit blocks with different structures. second, both the small signal effect and the large signal effect are modeled in a unified formulation, which eases the process of modeling and simulation. third, a nonlinear companding method is developed to control the modeling error distribution. to demonstrate the promising features of the proposed method, a 4th order switched-current filter is employed to build the behavioral model.