waashk/dblp huggingface dataset:
performance optimization of sequential circuits by eliminating retiming bottlenecks. a method to improve the effectiveness of retiming by transforming the sequential circuit is proposed. bottlenecks which prevent retiming to achieve a desired clock period are identified. conditions to eliminate the retiming bottlenecks are derived. these conditions are satisfied by a process of identifying subcircuits and satisfying a set of timing constraints on the subcircuits. the transformed circuit, which satisfies the timing constraints, can be retimed to achieve the desired clock period. if the original circuit has its initial state specified, the method always generates the final circuit with an equivalent initial state. experimental results on a variety of sequential benchmark circuits demonstrate significant performance improvement
fast timing simulation of transient faults in digital circuits. transient fault simulation is an important verification activity for circuits used in critical applications since such faults account for over 80% of all system failures. this paper presents a timing level transient fault simulator that bridges the gap between electrical and gate-level transient fault simulators. a generic mos circuit primitive and analytical solutions of node differential equations are used to perform transistor level simulation with accurate mos-fet models. the transient fault is modeled by a piecewise quadratic injected current waveform; this retains the electrical nature of the transient fault and provides spice-like accuracy. detailed comparisons with spice3 show the accuracy of this technique and speedups of two orders of magnitude are observed for circuits containing up to 2000 transistors. latched error distributions of the benchmark circuits are also provided.
fast and accurate timing simulation with regionwise quadratic models of mos i-v characteristics. this paper presents a technique called regionwise quadratic (rwq) modeling that allows highly accurate mos models, as well as measured i-v data, to be used in fast timing simulation. this technique significantly increases the accuracy of fast timing simulation while maintaining efficiency by permitting analytical solutions of node equations. a fast timing simulator using these rwq models has been implemented. several examples of rwq modeling are provided, and comparisons of simulation results with spice3 are shown to demonstrate accuracy and efficiency. speedups of two to three orders of magnitude for circuits containing up to 2000 transistors are observed.
algorithm for achieving minimum energy consumption in cmos circuits using multiple supply and threshold voltages at the module level. this paper proposes an optimum methodology forassigning supply and threshold voltages to modules in a cmoscircuit such that the overall energy consumption is minimizedfor a given delay constraint. the modules of the circuit shouldhave large enough gate depths such that the delay and energypenalties of the level shifters connecting them are negligible.both static and dynamic energy are considered in theoptimization. energy savings of up to 48% have been achievedon various example circuits. the first step in the optimizationfinds optimum supply and threshold voltages for each modulein the circuit. if the circuit has a large number of modules, thisstep might yield a correspondingly large number of differentsupply and threshold voltages for minimum energyconsumption. since having a large number of different supplyand threshold voltages on an ic is not feasible in currenttechnologies, an additional step clusters the multiple voltagesobtained from the first step into a fixed number of supply andthreshold voltages (for example, 2 different supply voltagesand 2 different threshold voltages). in addition to theapplication of this method to circuit optimization, it can also beapplied to a wide range of problems with delay constraints,such as software tasks running on a dynamically variable v{dd}and v{th} processor.
mogac: a multiobjective genetic algorithm for the co-synthesis of hardware-software embedded systems. in this paper, we present a hardware-software co-synthesis system, called mogac, that partitions and schedules embedded system specifications consisting of multiple periodic task graphs. mogac synthesizes real-time heterogeneous distributed architectures using an adaptive multiobjective genetic algorithm that can escape local minima. price and power consumption are optimized while hard real-time constraints are met. mogac places no limit on the number of hardware or software processing elements in the architectures it synthesizes. our general model for bus and point-to-point communication links allows a number of link types to be used in an architecture. application-specific integrated circuits consisting of multiple processing elements are modeled. heuristics are used to tackle multi-rate systems, as well as systems containing task graphs whose hyperperiods are large relative to their periods. the application of a multiobjective optimization strategy allows a single co-synthesis run to produce multiple designs which trade off different architectural features. experimental results indicate that mogac has advantages over previous work in terms of solution quality and running time.
efficient crosstalk noise modeling using aggressor and tree reductions. this paper describes a fast method to estimate crosstalk noise in the presence of multiple aggressor nets for use in physical design automation tools. since noise estimation is often part of the innerloop of optimization algorithms, very efficient closed-form solutions are needed. previous approaches have typically used simple lumped 3--4 node circuit templates. one aggressor net is modeled at a time assuming that the coupling capacitances to all quiet aggressor nets are grounded. they also model the load from interconnect branches as a lumped capacitor and use a dominant pole approximation to solve the template circuit. while these approximations allow for very fast analysis, they result in significant underestimation of the noise. in this paper, we propose a new and more comprehensive fast noise estimation model. we use a 6 node template circuit and propose a novel reduction technique for modeling quiet aggressor nets based on the concept of coupling point admittance. we also propose a reduction method to replace tree branches with effective capacitors which models the effect of resistive shielding. finally, we propose a new double pole approach to solve the template circuit. we tested the proposed method on noiseprone interconnects from an industrial high performance processor. our results show a worst-case error of 7.8% and an average error of 2.7%, while allowing for very fast analysis.
stratified random sampling for power estimation. in this paper, we propose a statistical power evaluation framework at the rt-level. we first discuss the power macro-modeling formulation, and then propose a simple random sampling technique to alleviate the the overhead of macro-modeling during rtl simulation. next, we describe a regression estimator to reduce the error of the macro-modeling approach. experimental results indicate that the execution time of the simple random sampling combined with power macro-modeling is 50 x lower than that of conventional macro-modeling while the percentage error of regression estimation combined with power macro-modeling is 16 x lower than that of conventional macro-modeling. hence, we provide the designer with options to either improve the accuracy or the execution time when using power macro-modeling in the context of rtl simulation.
accurate net models for placement improvement by network flow methods. an efficient iterative improvement procedure for row based cell placement is described. special emphasis is placed on the objective function used to model net lengths. it is shown that minimizing the net length estimated with the net model also minimizes the half perimeter of a rectangle enclosing all pins of a net. contrary to the half perimeter the new objective function permits computation of costs for assigning cells to locations independently for all cells to be placed simultaneously. this provides the algorithm an important advantage compared to other iterative improvement techniques: many cells can be placed simultaneously by formulating placement as a network flow problem. the algorithm is superior to timber-wolfsc 5.4, which minimizes the half perimeter
provably good global buffering using an available buffer block plan. to implement high-performance global interconnect without impacting the performance of existing blocks, the use of buffer blocks is increasingly popular in structured-custom and block-based asic/soc methodologies. recent works by cong et al. [6] and tang and wong [25] give algorithms to solve the buffer block planning problem. in this paper we address the problem of how to perform buffering of global nets given an existing buffer block plan. assuming as in [6, 25] that global nets have been already decomposed into two-pin connections, we give a provably good algorithm based on a recent approach of garg and k&ouml;nemann [8] and fleischer [7]. our method routes connections using available buffer blocks, such that required upper and lower bounds on buffer intervals -- as well as wirelength upper bounds per connection -- are satisfied. unlike [6, 25], our model allows more than one buffer to be inserted into any given connection. in addition, our algorithm observes buffer parity constraints, i.e., it will choose to use an inverter or a buffer (= co-located pair of inverters) according to source and destination signal parity. the algorithm outperforms previous approaches [6] and has been validated on top-level layouts extracted from a recent high-end microprocessor design.
latency-guided on-chip bus network design. deep submicron technology scaling has two major ramifications on the design process. first, reduced feature size significantly increases wire delay, thus resulting in critical paths being dominated by global interconnect rather than gate delays. second, ultra high level of integration mandates design of systems-on-chip that encompass numerous intra-synchronous blocks with decreased functional granularity and increased communication demands. to address these issues we have developed an on-chip bus network design methodology and corresponding set of tools which, for the first time, close the synthesis loop between system and physical design. the approach has three components: a communication profiler, a bus network designer, and a fast approximate floorplanner. the communication profiler collects run-time information about the traffic between system cores. the bus network design component optimizes the bus network structure by coordinating information from the other two components. the floorplanner aims at creating a feasible floorplan and to communicate information about the most constrained parts of the network.
frequency domain simulation of high-q oscillators with homotopy methods. an algorithm for the robust and efficient simulation of high-q oscillators using the harmonic balance method is presented. globally convergent homotopy methods are combined with the harmonic balance method for high-q oscillator simulation. various homotopy options are evaluated leading to an algorithm that is applicable to a wide variety of oscillator circuits.
kauffman networks: analysis and applications. a kauffman network is an abstract model of gene regulatory networks. each gene is represented by a vertex. an edge from one vertex to another implies that the former gene regulates the latter. statistical features of kauffman networks match the characteristics of living cells. the number of cycles in the network's state space, called attractors, corresponds to the number of different cell types. the attractor's length corresponds to the cell cycle time. the sensitivity of attractors to different kinds of disturbances, modeled by changing a network connection, the state of a vertex, or the associated function, reflects the stability of the cell to damage, mutations and virus attacks. in order to evaluate attractors, their number and lengths have to be computed. this problem is the major open problem related to kauffman networks. available algorithms can only handle networks with less than a hundred vertices. the number of genes in a cell is often larger. in this paper, we present a set of efficient algorithms for computing attractors in large kauffman networks. the resulting software package is hoped to be of assistance in understanding the principles of gene interactions and discovering a computing scheme operating on these principles.
guiding cnf-sat search via efficient constraint partitioning. contemporary techniques to identify a good variable order for sat rely on identifying minimum tree-width decompositions. however, the problem of finding a minimal width tree decomposition for an arbitrary graph is np complete. the available tools and methods are impractical, as they cannot handle large and hard-to-solve cnf-sat instances. this work proposes a hypergraph partitioning based constraint decomposition technique as an alternative to contemporary methods. we model the cnf-sat problem on a hypergraph and apply min-cut based bi-partitioning. clause-variable statistics across the partitions are analyzed to further decompose the problem, iteratively. the resulting tree-like decomposition provides a variable order for guiding cnf-sat search. experiments demonstrate that our partitioning procedure is fast, scalable and the derived variable order results in significant increase in performance of the sat engine.
vlsi circuit partitioning by cluster-removal using iterative improvement techniques. move-based iterative improvement partitioning methods such as the fiduccia-mattheyses (fm) algorithm and krishnamurthy's look-ahead (la) algorithm are widely used in vlsi cad applications largely due to their time efficiency and ease of implementation. this class of algorithms is of the "local improvement" type. they generate relatively high quality results for small and medium size circuits. however, as vlsi circuits become larger, these algorithms are not so effective on them as direct partitioning tools. we propose new iterative-improvement methods that select cells to move with a view to moving clusters that straddle the two subsets of a partition into one of the subsets. the new algorithms significantly improve partition quality while preserving the advantage of time efficiency. experimental results on 25 medium to large size acm/sigda benchmark circuits show up to 70% improvement over fm in cutsize, with an average of per-circuit percent improvements of about 25%, and a total cut improvement of about 35%. they also outperform the recent placement-based partitioning tool paraboli and the spectral partitioner melo by about 17% and 23%, respectively, with less cpu time. this demonstrates the potential of iterative improvement algorithms in dealing with the increasing complexity of modern vlsi circuitry.
efficient incremental rerouting for fault reconfiguration in field programmable gate arrays. the ability to reconfigure around manufacturing defects and operational faults increases fpga chip yield, reduces system downtime and maintenance in field operation, and increases reliabilities of mission- and life-critical systems. the fault reconfiguration technique discussed in this work use the principle of node covering in which reconfiguration is achieved by constructing replacement chains of cells from faulty cells to spare/unused ones. a key issue in such reconfiguration is efficient incremental rerouting in the fpga. previous methods for node-covering based reconfiguration are &ldquo;static&rdquo; in the sense that extra interconnects are added a-priori as part of the initial circuit routing so that a specific fault pattern (e.g., one fault per row) can be tolerated [1]. this, however, results in worst-case track overheads and also in an inflexibility to tolerate other realistic fault patterns. in this paper, we develop dynamic reconfiguration and incremental rerouting techniques that are fault specific. in this approach, the fpga is initially routed without any extra interconnects for reconfiguration. when faults occur, the routed nets have to be minimally perturbed to allow these interconnects to be inserted &ldquo;on-the-fly&rdquo; for reconfiguration. these requirements are addressed in our minimally incremental rerouting technique conv_t-dag, which uses a cost-directed depth-first search strategy. we prove several results that establishes the near-optimality of conv_t-dag in terms of track overhead. to the best of our knowledge, this is the first time that an incremental rerouting technique has been developed for fpgas. for several benchmark circuits, the static approach to tolerating one fault per row resulted in a 43% to 34% track overhead. using the dynamic reconfiguration approach and conv_t-dag results in an average overhead of only 16%&mdash;an improvement of more than 50%. over all circuits, the reconfiguration time per fault ranges from 16.8 to 72.9 secs. simulation of smaller fault sets of one to four faults show very small track overheads ranging from 1.75% to 4.49%. conv_t-dag can also be used for interconnect fault tolerance.
partitioning around roadblocks: tackling constraints with intermediate relaxations. constraint satisfaction during partitioning and placement of vlsi circuits is an important problem, and effective techniques to address it lead to high-quality physical design solutions. this problem has, however, been cursorily treated in previous partitioning and placement research. our work presented here addresses the balance-ratio constraint, and is a crucial first step to an effective solution to the general constraint-satisfaction problem. in current iterative-improvement mincut partitioners, the balance-ratio constraint is tackled by disallowing moves that violate it. these methods can lead to sub-optimal solutions since the process is biased against the movement of large cells and clusters of cells. we present techniques for an informed relaxation process that attempts to estimate whether relaxing the constraint temporarily will ultimately benefit the mincut objective. if so, then a violating move is allowed, otherwise it is disallowed. the violations are corrected in future moves so that the final solution satisfies the given constraint. on a set of acm/sigda proud benchmark circuits with actual cell sizes, we obtained up to 38% and an average of 14.5% better cutsizes with as little as 13% time overhead using our techniques compared to the standard method of not allowing any relaxation.
system software techniques for low-power operation in wireless sensor networks. the operation of wireless sensor networks is fundamentally constrained by available energy sources. the underlying hardware determines the power draw of each possible mode of operation. system software attempts maximize the use of the lowest possible modes of each of the subsystems. this tutorial paper describes the system software techniques used at several levels. at the application sensing level, this includes duty-cycling, sensor hierarchy, and aggregation. at the communication level, it includes low-power listening, communication scheduling, piggybacking, post-hoc synchronization, and power-aware routing. at the node os level, it includes event driven execution with split-phase operation and cooperative power management interfaces. at the lowest level, it includes management of primary and secondary energy storage devices coupled with intelligent charge transfer scheduling. all of these aspects must be integrated in a systematic software framework.
computer-aided design for dna self-assembly: process and applications. cad plays a fundamental role in both top-down and bottom-up system fabrication. this paper presents a bottom-up circuit patterning process based on dna self-assembly. the process is described in terms of the design tool requirements and the new opportunities that self-assembly creates for circuit designers. the paper also connects recent demonstrations of addressable self-assembly to applications in computer architecture and system design.
optimization of hierarchical designs using partitioning and resynthesis. this paper explores the influence of optimization along the boundary between hierarchically described components. a novel technique called repartitioning combines partitioning and sequential resynthesis of the design under various quality measures. it is applied to various digital circuits which consist of a controller and a datapath. the outcome of this effort is a versatile, parametrizable resynthesis tool which preserves this hierarchy. due to the cost measures, an average improvement ranging between 5% and 15% was obtained.
fast transient power and noise estimation for vlsi circuits. today's digital design systems are running out of steam, when it comes to meeting the challenges presented by simultaneous switching, power consumption and reliabilty constraints emerging in vlsi circuits. in this paper a new technique to accurately estimate the transient behavior of large cmos cell-based circuits in a reasonable amount of time is presented. gate-level simulations and a consistent modeling methodology are employed to compute the time-domain waveforms for signal voltages, supply currents, power consumption and &dgr;&igr; noise on power lines. this can be done for circuit blocks and complete designs by our new tool powtim, which adds spice-like capabilities to digital design standards.
an analytical method for finding the maximum crosstalk in lossless-coupled transmission lines. the crosstalk in a system containing n(n&ges;2) lossless microstrip transmission lines is formulated as a linear function in time. the maximum crosstalk is computed by evaluating the crosstalk at certain breakpoints in time. the technique also provides the pattern (rising or falling) of input voltages and their relative delays for which the maximum crosstalk occurs. this pattern is usually determined by the system parameters. since the maximum crosstalk determines the faulty vs fault-free operation, the pattern found could be used for testing integrated logic circuits during the design stage
a block rational arnoldi algorithm for multipoint passive model-order reduction of multiport rlc networks. recent work in the area of model-order reduction for rlc interconnect networks has been focused on building reduced-order models that preserve the circuit-theoretic properties of the network, such as stability, passivity, and synthesizability. passivity is the one circuit-theoretic property that is vital for the successful simulation of a large circuit netlist containing reduced-order models of its interconnect networks. non-passive reduced-order models may lead to instabilities even if they are themselves stable. in this paper, we address the problem of guaranteeing the accuracy and passivity of reduced-order models of multiport rlc networks at any finite number of expansion points. the novel passivity-preserving model-order reduction scheme is a block version of the rational arnoldi algorithm. the scheme reduces to that of the prima algorithm when applied to a single expansion point at zero frequency. although the treatment of this paper is restricted to expansion points that are on the negative real axis, it is shown that the resulting passive reduced-order model is superior in accuracy to the one that would result from expanding the original model around a single point. nyquist plots are used to illustrate both the passivity and the accuracy of the reduced-order models.