waashk/dblp huggingface dataset:
adaptive cut line selection in min-cut placement for large scale sea-of-gates arrays. we present a new min-cut based placement algorithm for large scale sea-of-gates arrays. in the past all such algorithms used a fixed cut line sequence that is determined before min-cut partitioning is performed. in our approach, we adaptively select a next partitioning pattern based on the current parameter value; we then perform the corresponding min-cut partitionings and measure a new parameter value. we repeat this process until all cut lines are processed. as a parameter, we introduce a new global objective function based on wire congestions on cut lines. we establish a close relation between this function and cut line sequences. this relation is used to develop an innovative method of adaptively determining a cut line sequence so as to minimize this global function. with this adaptive selection of cut lines along with a new cluster-based min-cut partitioning technique, our algorithm can produce, in a short time and at a low cost, final placement results that achieve the 100% completion of wiring on chips of fixed sizes. this has led to its successful production use, having generated more than 400 cmos sea-of-gates array chips.
worst-case analysis to obtain stable read/write dc margin of high density 6t-sram-array with local vth variability. 6t-sram cells in the sub-100 nm cmos generation are now being exposed to a fatal risk that originates from large local vth variability (/spl sigma//sub v/spl i.bar/local/). to achieve high-yield sram arrays in presence of random /spl sigma//sub v/spl i.bar/local/ component, we propose worst-case analysis that determines the boundary of the stable vth region for the sram read/write dc margin (vth curve). applying this to our original 65 nm spice model, we demonstrate typical behavior of the vth curve and show new criteria for discussing sram array stability with vth variability.
performance optimization using separator sets. in this paper, we propose a new method to optimize a performance of a very large circuit. we find the best set of local transformations to be applied to the circuit, by inserting &ldquo;padding nodes&rdquo; on non-critical edges of the circuit, and calculating separator sets of the circuit using separator sets. our method is robust for very large circuits, because its memory usage and calculation time are linear and polynomial order with the size of the circuit.according to our experimental results, our method has accomplished all circuits, while k. j. singh's selection function method has aborted with three large circuits because of memory overflow. the results also shows our method has a comparable capability in delay optimization to singh's method.
switching activity analysis using boolean approximation method. this paper presents a novel algorithm to estimate the signal probability and switching activity at all nodes in a combinational logic circuit under a zero-delay model without constructing global bdds. by using taylor expansion technique, the first-order signal correlation effects due to reconvergent fan-out nodes are taken into account. high accuracy is achieved by considering the dependency of the signal probability and switching activity on each primary input. high speed is also achieved by using the incremental approach for probability calculation. our approach is able to handle large circuits, since it does not need to construct global bdds for the probability calculation. the analysis of the time complexity and the experimental results show the running time of our approach to be about 100 times shorter than that of the most accurate approach previously proposed and that our approach has comparable accuracy. the error of the total power estimation is about 0.5% on average.
lp based cell selection with constraints of timing, area, and power consumption. this paper presents a new lp based optimal cell selection method. optimal cell selection is a useful tool for final tuning of lsi designs. it replaces drivabilities of cells, adjusting timing, area, and power constraints. using the latest and earliest arrival times, it can handle both setup and hold time constraints. we also make an efficient initial basis, which speeds up a simplex lp solver by 5 times without any relaxations nor approximations. from experimental results, it reduces the clock cycle of a manual designed 13k-transistor chip by 17% without any increase of area.
layout-driven resource sharing in high-level synthesis. in deep submicron (dsm) technology, the interconnects are equally as or more important than the logic gates. in particular, to achieve timing closure in dsm technology, it is very necessary and critical to consider the interconnect delay at an early stage of the synthesis process. it has been known that resource sharing in high-level synthesis is one of the major synthesis tasks which greatly affect the final synthesis/layout results. in this paper, we propose a new layout-driven resource sharing approach to overcome some of the limitations of the previous works in which the effects of layout on the synthesis have never been taken into account or considered in local and limited ways, or whose computation time is excessively large. the proposed approach consists of two steps: (step 1) we relax the integrated resource sharing and placement into an efficient linear programming (lp) formulation based on the concept of discretizing placement space; (step 2) we derive a feasible solution from the solution obtained in step 1. then, we employ an iterative mechanism based on the two steps to tightly integrate resource sharing and placement tasks so that the slack time violation due to interconnect delay (determined by placement) as well as logic delay (determined by resource sharing) should be minimized. from experiments using a set of benchmark designs, it is shown that the approach is effective, and efficient, completely removing the slack time violation produced by conventional methods.
optimal allocation of carry-save-adders in arithmetic optimization. carry-save-adder(csa) is one of the most widely used schemes for fast arithmetic in industry. this paper provides a solution to the problem of finding an optimal-timing allocation of csas. specifically, we present a polynomial time algorithm which finds an optimal-timing csa allocation for a given arithmetic expression. in addition, we extend our result for csa allocation to the problem of optimizing arithmetic expressions across the boundary of design hierarchy by introducing a new concept, called auxiliary ports. our algorithm can be used to carry out the csa allocation step optimally and automatically, and this can be done within the context of a standard hdl synthesis environment.
a new algorithm for routing tree construction with buffer insertion and wire sizing under obstacle constraints. buffer insertion and wire sizing are critical in deep submicron vlsi design. this paper studies the problem of constructing routing trees with simultaneous buffer insertion and wire sizing in the presence of routing and buffer obstacles. no previous algorithms consider all these factors simultaneously. previous dynamic programming based algorithm is first extended to solve the problem. however, with the size of routing graph increasing and with wire sizing taken into account, the time and space requirement increases enormously. then a new approach is proposed to formulate the problem as a series of graph problems. the routing tree solution is obtained by finding shortest paths in a series of graphs. in the new approach, wire sizing can be handled almost without any additional time and space requirement. moreover, the time and space requirement is only polynomial in terms of the size of routing graph. our algorithm differs from traditional dynamic programming, and is capable of addressing the problem of inverter insertion and sink polarity. both theoretical and experimental results show that the graph-based algorithm outperforms the dp-based algorithm by a large margin. we also propose a hierarchical approach to construct routing tree for a large number of sinks.
dynamic compilation for energy adaptation. while previous compiler research indicates that significant improvements in energy efficiency may be possible if properly optimized code is used, the energy constraints under which a given application code should be optimized may not always be available at compile-time. more importantly, these constraints may change dynamically during the course of execution. in this work, we present a dynamic recompilation/linking framework using which the energy behavior of a given application can be optimized while the application is being executed. our preliminary experiments indicate that large energy gains are possible through dynamic code recompilation/linking at the expense of a relatively small increase in execution time.
a simulation-based method for the verification of shared memory in multiprocessor systems. as processor architectural complexity increases, greater effort must be focused on functional verification of the chip as a component of the system. multiprocessor verification presents a particular challenge in terms of both difficulty and importance. while formal methods have made significant progress in the validation of coherence protocols, these methods are not always practical to apply to the structural implementation of a complex microprocessor. this paper describes a simulation-based approach to modeling and checking the shared-memory properties of the alpha architecture by using a directed acyclic graph to represent memory-access orderings. the resulting tool is integrated with a simulation model of an alpha implementation, allowing the user to verify aspects of the implementation with respect to the overall architectural specification. both an implementation-independent and an implementation-specific version of the tool are discussed.
delay optimal partitioning targeting low power vlsi circuits. abstract: in this paper, a delay optimal clustering/partitioning algorithm for minimizing the power dissipation of a circuit is proposed. traditional approaches for delay optimal partitioning are based on lawler's clustering algorithm that makes no attempt to explore alternative partitioning solutions that have the same delay but better power implementations. our algorithm provides a formal mechanism which implicitly enumerates alternate partitionings and selects a partitioning that has the same delay but less power dissipation. for tree circuits, the proposed algorithm produces delay and power optimal partitioning whereas for non-tree circuits it produces delay optimal partitioning with significantly improved power dissipation.
test generation for primitive path delay faults in combinational circuits. this paper presents a method of identifying primitive path-delay faults in combinational circuits, and deriving robust tests for all robustly testable primitive faults. it uses the concept of sensitizing cubes to reduce the search space. this approach helps identify faults that cannot be part of any primitive fault, and avoids attempting test generation for them. sensitization conditions determined for primitive fault identification are also used in test generation, reducing test generation effort. experimental results on some of the iscas'85 and mcnc'91 benchmark circuits indicate that they contain a fair number of primitive multiple path delay faults which must be tested.
on the difference between two widely publicized methods for analyzing oscillator phase behavior. this paper describes the similarities and differences between two widely publicized methods for analyzing oscillator phase behavior. the methods were presented in [3] and [6]. it is pointed out that both methods are almost alike. while the one in [3] can be shown to be, mathematically, more exact, the approximate method in [6] is somewhat simpler, facilitating its use for purposes of analysis and design. in this paper, we show that, for stationary input noise sources, both methods produce equal results for the oscillator's phase noise behavior. however, when considering injection locking, it is shown that both methods yield different results, with the approximation in [6] being unable to predict the locking behavior. in general, when the input signal causing the oscillator phase perturbations is non-stationary, the exact model produces the correct results while results obtained using approximate model break down.
a generalized method for computing oscillator phase noise spectra. this paper presents a generalized semi-analytic method for computingoscillator phase noise spectra, including the details veryclose to the oscillation frequency. the starting point is a generalrelation between an oscillator's output power spectral density andthe characteristics of the input noise processes. for weak inputnoise processes that vary sufficiently fast over time, this relation reducesto an analytic expression. for cases that do not satisfy theseconditions, the relation is, in part, evaluated numerically. this isaccomplished using techniques for exponential data fitting. the resultingmethod is able to compute oscillator phase noise spectra fora wide range of input noise characteristics.
activity-driven clock design for low power circuits. in this paper we investigate activity-driven clock trees to reduce the dynamic power consumption of synchronous digital cmos circuits. sections of an activity-driven clock tree can be turned on/off by gating the clock signals during the active/idle times of the clocked elements. we propose a method of obtaining the switching activity patterns of the clocked circuits during the high level design process. we formulate three novel activity-driven problems. the objective of these problems is to minimize system's dynamic power consumption. we propose an approximation algorithm based on recursive matching to solve the clock tree construction problem. we solve the gate insertion problems with an exact algorithm employing the dynamic programming paradigm. finally, we present experimental results that verify the effectiveness of our approach. our work in this paper is a step in understanding how high level decisions (e.g. behavioral design) can affect a low level design (e.g. clock design).
clock period constrained minimal buffer insertion in clock trees. in this paper we investigate the problem of computing a lower bound on the number of buffers required when given a maximum clock frequency and a predefined clock tree. using generalized properties of published cmos timing models, we formulate a novel non-linear and a simplified linear buffer insertion problem. we solve the latter optimally with an o(n) algorithm. the basic formulation and algorithm are extended to include a skew upper bound constraint. using these algorithms we propose further algorithmic extensions that allow area and phase delay tradeoffs. our results are verified using spice3e2 simulations with mcnc mosis 2.0&mgr; models and parameters. experiments show our buffer insertion algorithms can be used effectively for high-speed clock designs.
estimation of maximum transition counts at internal nodes in cmos vlsi circuits. in combinational logic circuits, a single switching event on the primary inputs may give rise to multiple switchings at the internal nodes. this glitching effect is caused primarily by unequal delay paths and results in increased power consumption and decreased device reliability. in this paper, we present a new algorithm to estimate the maximum number of transitions at internal nodes in combinational cmos vlsi circuits. unlike exhaustive simulation, our algorithm is based on the technique of propagating uncertainty waveforms throughout the circuit and using these waveforms to count the maximum switching activity at every node. our approach guarantees a tight upper bound on the number of transitions which is necessary to assess the minimum circuit reliability lifetime and maximum power dissipation.
optimization of a fully integrated low power cmos gps receiver. this paper describes an optimization technique able to optimize a complete wireless receiver architecture in a reasonable amount of time. the optimizer alternates between spice level optimizations of simple building blocks and a full architecture optimization of the whole based on accurate models of the building blocks. the models of the building blocks are interpolated over the data points acquired in the spice level simulations. the optimizer technique has been applied to the optimization of an architecture for a gps receiver. the optimal design has been implemented in a standard 0.25&mu;m cmos process.
gate sizing using lagrangian relaxation combined with a fast gradient-based pre-processing step. in this paper, we present forge, an optimal algorithm for gate sizing using the elmore delay model. the algorithm utilizes lagrangian relaxation with a fast gradient-based pre-processing step that provides an effective set of initial lagrange multipliers. compared to the previous lagrangian-based approach, forge is considerably faster and does not have the inefficiencies due to difficult-to-determine initial conditions and constant factors. we compared the two algorithms on 30 benchmark designs, on a sun ultrasparc-60 workstation. on average forge is 200 times faster than the previously published algorithm. we then improved forge by incorporating a slew-rate-based convex delay model, which handles distinct rise and fall gate delays. we show that forge is 15 times faster, on average, than the amps transistor-sizing tool from synopsys, while achieving the same delay targets and using similar total transistor area.
a layout-aware synthesis methodology for rf circuits. in this paper a layout-aware rf synthesis methodology is presented. the methodology combines the power of a differential evolution algorithm with cost function response modeling and integrated layout generation to synthesize rf circuits efficiently, taking into account all layout parasitics during the circuit optimization. the proposed approach has successfully been applied to the design of a high-performance downconverter mixer circuit, proving the effectiveness of the implemented design methodology.
optimal wire and transistor sizing for circuits with non-tree topology. conventional methods for optimal sizing of wires and transistors use linear rc circuit models and the elmore delay as a measure of signal delay. if the rc circuit has a tree topology the sizing problem reduces to a convex optimization problem which can be solved using geometric programming. the tree topology restriction precludes the use of these methods in several sizing problems of significant importance to high-performance deep submicron design including, for example, circuits with loops of resistors, e.g., clock distribution meshes, and circuits with coupling capacitors, e.g., buses with crosstalk between the lines. the paper proposes a new optimization method which can be used to address these problems. the method uses the dominant time constant as a measure of signal propagation delay in an rc circuit, instead of elmore delay. using this measure, sizing of any rc circuit can be cast as a convex optimization problem which can be solved using the recently developed efficient interior-point methods for semidefinite programming. the method is applied to two important sizing problems --- sizing of clock meshes, and sizing of buses in the presence of crosstalk.
hermes: lut fpga technology mapping algorithm for area minimization with optimum depth. this work presents hermes, a depth-optimal lut based fpga mapping algorithm. the presented algorithm is based on a new strategy for finding luts allowing to find a good lut in a significantly shorter time compared to the previous methods. the quality of results is improved by enabling lut re-implementation and by introducing a cost function which encourages input sharing among luts. the experimental results show that, on average, the presented algorithm computes 15.5% and 3.5% smaller lut mappings compared to the ones obtained by flowmap and cutmap, respectively, using two orders of magnitude less cpu time. the speed of hermes makes it suitable for running in an incremental manner during logic synthesis.
folding a stack of equal width components. we consider two versions of the problem of folding a stack of equal width components. in both versions, when a stack is folded, a routing penalty is incurred at the fold. in one version, the height of the folded layout is given and we are to minimize width. in the other, the width of the folded layout is given and its height is to be minimized.
hero: hierarchical emc-constrained routing. the authors point out that, in order to perform the design of printed circuit boards as time- and cost-efficiently as possible, electromagnetic compatability (emc) phenomena have to be taken into account during layout synthesis. the emc router hero offers a robust framework for incorporating emc constraints and cost criteria into routing. using hero, it will not be possible to obtain a completely failsafe layout, in general. however, experimental results for typical boards prove that a great number of emc problems can be avoided during layout synthesis and that the effects of emc phenomena can be reduced substantially. detailed reports of emc design rule violations provide effective input to the succeeding emc verification phase. violations of emc design rules are mainly caused by an inappropriate placement. therefore, it seems to be of great promise to combine hierarchical placement methods with this approach for hierarchical routing
cloning techniques for hierarchical compaction. a method for efficiently performing hierarchical compaction in the presence of over the cell routing (otcr) is described. by treating the otcr objects as part of the cells they overlap, the amount of interaction between cells in the hierarchy is reduced. this method eliminates the need to make all objects within a cell that interact with otcr into ports. an explosion in the complexity of the problem that needs to be solved via linear programming (lp) is thus avoided. computation is shifted away from lp and into the graph domain where efficient and accurate solution methods have been demonstrated
communication-aware task scheduling and voltage selection for total systems energy minimization. in this paper, we present an interprocessor communication-aware task scheduling algorithm applicable to a multiprocessor system executing an application with dependent tasks. our algorithm takes the application task graph and the architecture graph as inputs,assigns the tasks to processors and then schedules them. as main theoreticalcontribution, the algorithm we propose reduces the overallsystems energy by (i) reducing the total interprocessor communicationand (ii) executing certain cycles at a lower voltage level. experimentalresults show that by tuning the parameter for communicationawareness, a schedule using our algorithm can reduce upto 80%interprocessor communication in a complex video/audio application(compared to a schedule which is only voltage-selection aware) withoutlosing much in the number of cycles executed at lower voltage.
test generation for comprehensive testing of linear analog circuits using transient response sampling. the problem of testing analog components continues to be the bottleneck in reducing the time-to-market of mixed-signal ics. in this paper, we present a test generation algorithm for implicit functional testing of linear analog circuits using transient response sampling. each specification of the circuit under test (cut) imposes bounds on individual parametric deviations under the single fault assumption. these bounds are mapped on to "acceptable" ranges of measurements of the transient response of the cut at various sample points using time domain sensitivity calculations. any circuit that "passes" the applied test is also guaranteed to meet its specifications. the simplicity of the test waveform, reduced test generation time and test time show that this testing method is a good alternative to existing testing schemes.