waashk/dblp huggingface dataset:
stochastic analysis of interconnect performance in the presence of process variations. deformations in interconnect due to process variations can lead to significant performance degradation in deep sub-micron circuits. timing analyzers attempt to capture the effects of variation on delay with simplified models. the timing verification of rc or rlc networks requires the substitution of such simplified models with spatial stochastic processes that capture the random nature of process variations. the present work proposes a new and viable method to compute the stochastic response of interconnects. the technique models the stochastic response in an infinite dimensional hilbert space in terms of orthogonal polynomial expansions. a finite representation is obtained by using the galerkin approach of minimizing the hilbert space norm of the residual error. the key advance of the proposed method is that it provides a functional representation of the response of the system in terms of the random variables that represent the process variations. the proposed algorithm has been implemented in a procedure called opera, results from opera simulations on commercial design test cases match well with those from the classical monte carlo spice simulations and from perturbation methods. additionally opera shows good computational efficiency: speedup factor of 60 has been observed over monte carlo spice simulations.
noise margin analysis for dynamic logic circuits. we consider the problem of noise margin analysis for dynamic logic circuits. because such circuits operate in multiple phases, their noise immunity is also time varying. we formulate noise margin analysis as a non-linear optimization problem where we find the smallest disturbance waveform that results in a qualitative change in the behavior of the circuit. we present a practical method for solving these optimization problems based on deriving a sensitivity matrix for the small-signal response of the circuit. we use our approach to compare the robustness of static cmos gates, self-resetting domino, and output prediction logic.
the compositional far side of image computation. symbolic image computation is the most fundamental computationin bdd-based sequential system optimization and formal verification.in this paper, we explore the use of over-approximationand bdd minimization with donýt cares during image computation.our new method, based on the partitioned representation ofthe transition relation, consists of three phases: first, the model istreated as a set of loosely coupled components, and over-approximateimages are computed to minimize the transition relation ofeach component. a refined overall image is then computed usingthe simplified transition relation. finally, the exact image isobtained by a clipping operation that recovers all previous over-approximations.since bdd minimization employs constraints on thenext-state variables of the transition relation, instead of the customaryconstraints on the present-state variables, we call the resultingmethod far side image computation.the new method can be implemented on top of any image computationalgorithm that is based on the partitioned transition relation.(for example, iwls95, mlp, and fine-grain.)we demonstrate the effectiveness of our approach by experimentson models ranging from easy to hard: the new method wins significantlyover the best known algorithms so far in both cpu timeand memory usage, especially on the hard models.
rlc interconnect delay estimation via moments of amplitude and phase response. a new category of moments&mdash;amplitude and phase moments (ap moments) are introduced for rlc interconnect delay estimation. we show that there are tight relationships between ap moments, circuit moments and central moments. the first order ap moment represents the elmore delay while the higher order ap moments can be used to represent the error between the elmore delay and the exact 50% delay from the view of gain and phase-shift variation. with the help of the physical meaning revealed by the ap moments, a closed-form 50% delay model&mdash;ap delay model is proposed for rlc interconnect delay estimation in terms of the first four ap moments. we also propose a new two-pole model (ap two-pole model) by matching the first two phase moments of the transfer function. the ap two-pole model can be used for more generally timing parameters estimation. the input signal's impact on delay estimation can be incorporated into these two delay models by simply combining the input signal's ap moments with the transfer function's ap moments. in our experiments these two models show significant accuracy improvement over the elmore delay model.
the chebyshev expansion based passive model for distributed interconnect networks. a new chebyshev expansion based model for distributed interconnect networks is presented in this paper. unlike the moment methods, this new model is optimal and it does not require the knowledge of expansion points. an automatic order selection scheme is also included in the new model. by using the integrated congruence transform, we guarantee the passivity of the new model for distributed interconnect networks. because of the orthogonality of chebyshev polynomials, the modified gram-schmidt algorithm can be simplified. in the experimental examples, the new model is found to be accurate and efficient.
congestion reduction during placement based on integer programming. this paper presents a novel method to reduce routing congestion during placement stage. the proposed approach is used as a post-processing step in placement. congestion reduction is based on local improvement on the existing layout. however, the approach has a global view of the congestion over the entire design. it uses integer linear programming (ilp) to formulate the conflicts between multiple congested regions, and performs local improvement according to the solution of ilp. experiments show that the proposed approach can effectively reduce the total overflow of global routing result. the short running time of the algorithm indicates good scalability on large designs.
frosty: a fast hierarchy extractor for industrial cmos circuits. this paper presents frosty, a computer programfor automatically extracting the hierarchy of a large-scale digitalcmos circuit from its transistor-level netlist description and alibrary of subcircuits. to handle the complexity of industrialcircuits, frosty combines traditional structural recognition andpattern matching methods into a two-step extraction process.first, gate structures based on channel-connected-components arerecognized from a circuit netlist and library subcircuits. thenannotated graphs representing the connectivity and properties ofgate structures are constructed. comparing to transistor-levelnetlists, these graphs are much smaller in size, moredistinguishable in structure, and are thus more suitable forlabeling based pattern matching. an efficient pattern matchingalgorithm is applied to extract the circuit hierarchy from thesecondensed circuit graphs. frosty has been demonstrated to beorders of magnitude faster than the best known extractionprogram subgemini, capable of extracting the entire hierarchy ofindustrial designs with several hundred thousand transistors in afew minutes on a sun workstation. further frosty is scale withthe size of a circuit.
efficient network flow based min-cut balanced partitioning. we consider the problem of bipartitioning a circuit into two balanced components that minimizes the number of crossing nets. previously, the kernighan and lin type (k&l) heuristics, the simulated annealing approach, and the spectral method were given to solve the problem. however, network flow techniques were overlooked as a viable approach to min-cut balanced bipartition to due its high complexity. in this paper we propose a balanced bipartition heuristic based on repeated max-flow min-cut techniques, and give an efficient implementation that has the same asymptotic time complexity as that of one max-flow computation. we implemented our heuristic algorithm in a package called fbb. the experimental results demonstrate that fbb outperforms the k&l heuristics and the spectral method in terms of the number of crossing nets, and the efficient implementation makes it possible to partition large, circuit instances with reasonable runtime. for example, the average elapsed time for bipartitioning a circuit s35932 of almost 20k gates is less than 20 minutes.
redi: an efficient fault oriented procedure to identify redundant faults in combinational logic circuits. in this work, a new and effective procedure, called redi, to efficiently identify redundant single stuck-at faults in combinational logic circuits is proposed. the method is fault oriented and uses sensitizability of partial paths to determine redundant faults. it uses only implications and hence may not determine all the redundant faults of a circuit. however, experimental results presented on benchmark circuits show that the procedure identifies nearly all the redundant faults in most of the benchmark circuits. the key features of redi that make it efficient are: partial path sensitization, blockage learning, dynamic branch ordering and fault grouping. experimental results on benchmark circuits demonstrate the efficiency of the proposed procedure in identifying redundant faults in combinational logic circuits.
edge-map: optimal performance driven technology mapping for iterative lut based fpga designs. we consider the problem of performance driven lookup-table (lut) based technology mapping for fp-gas using a general delay model. in the general delay model, each interconnection edge has a weight representing the delay of the interconnection. this model is particularly useful when combined with an iterative re-technology mapping process where the actual delays of the placed and routed circuit are fed-back to the technology mapping phase to improve the mapping based on the more realistic delay estimation. well-known technology mappers such as flowmap and chortle-d only minimize the number of levels in the technology mapped circuit and hence are not suitable for such an iterative re-technology mapping process. recently, mather and liu in [ml94] studied the performance driven technology mapping problem using the general delay model and presented an effective heuristic algorithm for the problem. in this paper, we present an efficient technology mapping algorithm that achieves provably optimal delay in the technology mapped circuit using the general delay model. our algorithm is a non-trivial generalization of flowmap. a key problem in our algorithm is to compute a k-feasible network cut such that the circuit delay on every cut edge is upper-bounded by a specific value. we implemented our algorithm in a lut based fpga technology mapping package called edge-map, and tested edge-map on a set of benchmark circuits.
rtl power optimization with gate-level accuracy. traditional rtl power optimization techniques committransformations at the rtl based on the estimation of area, delayand power. however, because of inadequate power and delayinformation, the power optimization transformations applied atthe rtl may cause unexpected results after synthesis, such asworsened delay or increased power dissipation. our solution tothis problem is to divide rtl power optimization into two steps,namely rtl exploration and gate-level commitment. during rtlexploration phase potential candidates for applying some specificrtl transformation are identified where high level informationpermits faster and more effective analysis. these candidates aresimply "marked" on the netlist. then during the gate-levelcommitment phase when accurate power and delay information isavailable, the final decision of whether accepting or rejecting thecandidate is made to achieve the best power and delay trade-offs.
new algorithms for min-cut replication in partitioned circuits. abstract: hwang and el gamal (1992, 1995) formulated the min-cut replication problem, which is to determine min-cut replication sets for the components of a k-way partition such that the cut size of the partition is minimized after the replication. they gave an optimal algorithm for finding min-cut replication sets for a k-way partitioned digraph. however, their optimal min-cut replication algorithm does not guarantee min-cut replication sets of minimum sizes. furthermore, their algorithm is not optimal for hypergraphs. in this paper, we optimally solve the min-area min-cut replication problem on digraphs, which is to find min-cut replication sets with the minimum sizes. more importantly, we give an optimal solution to the hypergraph min-area min-cut replication problem using a much smaller flow network model. we implemented our algorithms in a package called hyper-mamc, and interfaced hyper-mamc to the tapir package. on average, hyper-mamc produces 57.3% fewer cut nets and runs much faster than mo-rep in the tapir package, on the same initial partitions of a set of mcnc partition93 benchmark circuits.
cosmos: a continuous optimization approach for maximum power estimation of cmos circuits. maximum instantaneous power in vlsi circuits has a great impact on circuit's reliability and the design of power and ground lines. to synthesize highly reliable systems, accurate estimates of maximum power must be obtained in various design phases. unfortunately, determining the input patterns to induce the maximum current (power) is essentially a combinatorial optimization problem. even for circuits with small number of primary inputs (pi's), it is cpu time intensive to conduct exhaustive search in the input vector space. the only feasible way is to find good upper and lower bounds of the maximum power, and to make the gap between these two bounds as narrow as possible. in this paper, we present a continuous optimization approach to efficiently generate tight lower bounds of the maximum instantaneous power for cmos circuits. in our approach, each primary input (pi) of the circuit is allowed to assume any real number between 0 and 1. maximum power estimation for cmos circuits is then transformed into a continuous optimization problem, in which a smooth function is maximized over a unit hypercube in the euclidean space. the continuous problem can be solved efficiently to generate good lower bounds of the maximum power. our experiments with iscas and mcnc benchmark circuits demonstrate the superiority of this approach. for all the circuits tested, the mean value of the ratio "cpu time of the continuous optimization approach divided by cpu time of the simulation-based technique" is equal to 0.41. for 60% of the circuits tested, our approach gives a better estimate (1.16 times larger, on an average) than the simulation-based technique does. compared to the atpg-based technique, the continuous optimization approach generates a tighter lower bound (1.19 times larger, on an average) of maximum power for 60% of all the circuits tested.
conflict driven techniques for improving deterministic test pattern generation. this work presents several new techniques for enhancing the performance of deterministic test pattern generation for vlsi circuits. the techniques introduced are called dynamic decision ordering, conflict driven recursive learning and conflict learning. an important feature shared by all these techniques is that they are triggered by the occurrence of a conflict in the generation of tests. hence, they are not active all the time nor for all the faults. this feature allows the atpg system that uses these techniques to resolve hard-to-resolve faults with far fewer backtracks and leaves the system as efficient as before in the absence of conflicts. we have incorporated these techniques into a commercial d-algorithm based atpg tool. the experimental results on full scan versions of itc'99 benchmark circuits demonstrate an improvement of the atpg system both in the number of aborted faults and in test generation time.
data path placement with regularity. as more data processing functions are integrated into systems-on-chip, data path is becoming a critical part of the whole vlsi design. however, traditional physical design methodology can not satisfy the data path performance requirement because it has no knowledge of the data path bit-sliced structure. in this paper, an abstract physical model (apm) is proposed to extract bit-slice regularity information from data flow graph (dfg) and it is used for interconnect and congestion planning. a two step heuristic algorithm is introduced to optimize the linear placement of apm to satisfy both the wire length and routing track budget.
thermal-induced leakage power optimization by redundant resource allocation. traditionally, at early design stages, leakage power is associated with the number of transistors in a design. hence, intuitively an implementation with minimum resource usage would be best for low leakage. such an allocation would generally be followed by switching optimal resource binding to achieve a low power design. this treatment of leakage power is unaware of operating conditions such as temperature. in this paper, we propose a technique to reduce the total leakage power of a design by identifying the optimal number of resources during allocation and binding. we demonstrate that, contrary to the general tendency to minimize the number of resources, the best solution can actually be achieved if a certain degree of redundancy is allowed. this is due to the fact that leakage is strongly dependent on the on-chip temperature profile. distributing activity over a higher number of resources can reduce power density, remove potential hotspots and subsequently minimize thermal induced leakage. on the other hand, using an arbitrarily high number of resources will not yield the best solution. in this paper, we show that there is a power density, hence, temperature, at which the total leakage power will reach its optimal value. such an optimal resource number can be a better starting point for the subsequent switching-driven low power binding. we also present a high-level power density-aware leakage model. based on the estimates by this model, we optimize the total leakage power by 53.8% on average compared to the minimum resource binding, and 35.7% on average compared to a temperature-aware resource binding technique.
on compacting test response data containing unknown values. the design of a test response compactor called a block compactoris given. block compactors belong to a new class of compactorscalled finite memory compactors. different from spacecompactors, finite memory compactors contain memory elements.also unlike time compactors, finite memory compactors havefinite impulse response. these properties give finite memorycompactors the ability to achieve higher compaction ratios thanspace compactors and still be able to tolerate unknown values intest responses. the proposed block compactors, as an instance offinite memory compactors generate a signature of response data inseveral scan cycles. results presented on several industrial designsshow that block compactors provide better test quality and higherdata compaction than earlier works on test response compactors.
a probabilistic multicommodity-flow solution to circuit clustering problems. circuit clustering, which plays a fundamental role in hierarchical designs, is discussed. identifying strongly connected components in the circuits can significantly reduce the complexity of the design and improve the performance of the design process. however, there has not been a clear objective function for circuit clustering. a clustering metric based on the random graph model and the ratio cust concept is presented. a probabilistic, multicommodity flow based algorithm is proposed and tested under the clustering metric. experimental results show that this algorithm generates promising results with respect to the proposed metric. extensions and directions for future work are also proposed
multi-million gate fpga physical design challenges. the recent past has seen a tremendous increase in the size ofdesign circuits that can be implemented in a single fpga. theselarge design sizes significantly impact cycle time due to designautomation software runtimes and an increased number ofperformance based iterations. new fpga physical designapproaches need to be utilized to alleviate some of theseproblems. hierarchical approaches to divide and conquer thedesign, early estimation tools for design exploration, andphysical optimizations are some of the key methodologies thathave to be introduced in the fpga physical design tools. thispaper will investigate the loss/benefit in quality of results due tohierarchical approaches and compare and contrast some of thedesign automation problem formulations and solutions neededfor fpgas versus known standard cell asic approaches.
minimum-area sequential budgeting for fpga. the constraint-based approach to timing-driven placementrequires delay budgeting to define the delay upper bounds for nets.while most of the previous delay-budgeting works have beenfocused on optimizing combinational circuits, the work in [delay budgeting in sequential circuit with application on fpga placement]introduces sequential budgeting, which combines budgeting andretiming to optimize sequential circuits better. however, theformulation in [delay budgeting in sequential circuit with application on fpga placement] does not consider flip-flop (ff) minimization,which is important in practical applications. here, we propose anew sequential budgeting algorithm, c-sbgt, that not onlycontrols the ff count, but also can be solved more efficientlycompared to [delay budgeting in sequential circuit with application on fpga placement]. our formulation has fewer constraints than [delay budgeting in sequential circuit with application on fpga placement] and the procedure to realize retiming is also simpler. ourexperiments show that our new min-area sequential budgetingalgorithm produces a good trade-off between the area andbudgeting optimization goals, as well as improving the timingof previous sequential budgeting method by 12%.
system-level power and thermal modeling and analysis by orthogonal polynomial based response surface approach (oprs). this paper proposes a new statistical response surface based power estimation technique. the new approach is able to include a number of parameters such as multiple vdd, multiple vth and gate sizing parameters. it has both deterministic ability and statistical ability. the deterministic ability allows the new model to provide optimal design parameters for power reduction. the statistical ability can be used to model the process variation impact on power.
timing-aware power noise reduction in layout. in this paper, we propose a timing-aware power-noise reduction technique. our approach consists of prediction and correction steps. before placement, we estimate the power noise of each cell considering switching frequency of cells which, after placement, will most likely be in the neighborhood. if a frequently switching cell has neighbors which switch infrequently, it is unlikely that this cell will suffer from a power noise problem. based on the cell power noise estimation, we add decap padding to each cell. then we invoke a standard cell placement tool and perform power grid analysis. we eliminate the power grid noise by gate sizing. our technique can reallocate decaps to improve power noise, power consumption, and timing. the gate sizing is based on the sequence of linear programs (slp) formulation, and it can be solved efficiently. experimental results show that our techniques can effectively reduce power noise and meet timing constraints.