waashk/dblp huggingface dataset:
an approximate timing analysis method for datapath circuits. we present a novel timing analysis method acd that computes an approximate value for the delay of datapath circuits. based on the conditional delay matrix (cdm) formalism we introduced earlier, the acd method exploits the fact that most datapath signals are directed by a small set of control inputs. the signal propagation conditions are restricted to a set of predefined control inputs, which results in significant reductions in the size of the conditions as well as computation time. we have implemented acd and experimented with reverse-engineered high-level versions of the iscas-85 benchmarks. our results demonstrate up to three orders of magnitude speedup in computation time over exact methods, with little or no loss in accuracy.
deep submicron defect detection with the energy consumption ratio. advances in technology and increasing integration are expected to degrade the effectiveness of iddq test. total leakage currents per ic are expected to be very large, making it difficult to detect the impact of a single defect (t.w. williams et al., 1996; m. sachdev, 1997). test methods which detect faults by monitoring the dynamic supply current have been suggested as one alternative. almost all the dynamic current techniques proposed in the literature are adversely affected by the impact of process variations. many are also susceptible to timing and magnitude errors in measurement. the energy consumption ratio (ecr) is a new dynamic current-based test metric (b. vinnakota et al., 1998), that addresses some of these problems. ecr-based test offers several advantages over other dynamic test methods and the iddq test such as tolerance to process variations, reduced test process complexity and a proven ability to detect faults that escape other techniques. the ecr has been validated through extensive simulation and through application to a 50k gate sub-micron biomedical ic (w. jiang and b. vinnakota, 1999). our contributions are directed towards further validating the real quality of the ecr
perfect-balance planar clock routing with minimal path-length. the design of high speed digital vlsi circuits prefers that the clock net is routed on the metal layer with the smallest rc delay. this strategy not only avoids the difficulties of having different electrical parameters on different layers, but also eliminates the delay and attenuation of the clock signal through vias. the clock phase-delay is also decreased. in this paper, we present a novel algorithm, based on hierarchical max-min optimization, to construct a planar clock tree which can be embedded on a single metal layer. the clock tree achieves equal path length---the length of the path from the clock source to each clock terminal is exactly the same. in addition, the path length from the source to clock terminals is minimized. some examples including industrial benchmarks have been tested and the results are promising. we further optimize the geometry of the clock tree to minimize both the skew and path delay of the clock signal while maintaining the planarity of the clock network. some premilinary results are promising which achieve near zero skew by using spice simulation.(supersedes ucsc-crl-92-12)
symbolic pointer analysis. one of the bottlenecks in the recent movement of hardware synthesis from behavioral c programs is the difficulty in reasoning about runtime pointer values at compile time. the pointer analysis problem has been investigated in the compiler community for two decades, which has yielded efficient, polynomial time algorithms for context-insensitive analysis. however, at the accuracy level for which hardware synthesis is desired, namely context and flow sensitive analysis, the time and space complexity of the best algorithms reported grow exponentially with program size. in this paper, we present our first step towards a new analysis technology which potentially leads to almost-linear time complexity and sub-linear space complexity algorithm even for the most accurate analysis. the key idea that contributes to this efficiency is to implicitly encode the pointer-to relation in the boolean domain, thereby capturing the procedure transfer function completely, compactly and canonically. this represents a wide departure from the traditional techniques, all of which explicitly capture pointer-to relation using variations of point-to graph, which have to be re-evaluated for different calling contexts. experiments for our first flow-insensitive algorithm on common benchmarks show promising result.
optimization techniques for high-performance digital circuits. the relentless push for high performance in custom digital circuits has led to renewed emphasis on circuit optimization or tuning. the parameters of the optimization are typically transistor and interconnect sizes. the design metrics are not just delay, transition times, power and area, but also signal integrity and manufacturability. this tutorial paper discusses some of the recently proposed methods of circuit optimization, with an emphasis on practical application and methodology impact. circuit optimization techniques fall into three broad categories. the first is dynamic tuning, based on time-domain simulation of the underlying circuit, typically combined with adjoint sensitivity computation. these methods are accurate but require the specification of input signals, and are best applied to small data-flow circuits and "cross-sections" of larger circuits. efficient sensitivity computation renders feasible the tuning of circuits with a few thousand transistors. second, static tuners employ static timing analysis to evaluate the performance of the circuit. all paths through the logic are simultaneously tuned, and no input vectors are required. large control macros are best tuned by these methods. however, in the context of deep submicron custom design, the inaccuracy of the delay models employed by these methods often limits their utility. aggressive dynamic or static tuning can push a circuit into a precipitous corner of the manufacturing process space, which is a problem addressed by the third class of circuit optimization tools, statistical tuners. statistical techniques are used to enhance manufacturability or maximize yield. in addition to surveying the above techniques, topics such as the use of state-of-the-art nonlinear optimization methods and special considerations for interconnect sizing, clock tree optimization and noise-aware tuning will be briefly considered.
post global routing crosstalk risk estimation and reduction. previous approaches for crosstalk synthesis often fail to achieve satisfactory results due to limited routing flexibility. furthermore, the risk tolerance bounds partitioning problem critical for constrained optimization has not been adequately addressed. this paper presents the first approach for crosstalk risk estimation and reduction at the global (instead of detailed) routing level. it quantitatively defines and estimates the risk of each routing region using a graph-based optimization approach and globally adjusts routes of nets for risk reduction. at the end of the entire optimization process, a risk-free global routing solution is obtained together with partitions of nets' risk tolerance bounds which reflect the crosstalk situation of the chip. the proposed approach has been implemented and tested on cbl/ncsu benchmarks and the experimental results are very promising.
timing-driven placement for heterogeneous field programmable gate array. in this paper, a new timing-driven placement algorithm is proposed to handle complicated placement requirements inherent in fpgas with heterogeneous resources (dedicated logic block, memory block). the new algorithm employs a multi-layer density system with each layer modeling a drastically different architectural resource. by introducing the multi-layer density system, a heterogeneous placement task is translated to a set of homogeneous ones, with each of them being handled at a different density layer. we also present a new iterative timing optimization scheme which is seamlessly integrated in the placement process. the tight interaction between the placement and timing optimization produces superior timing results for industrial designs.
formulation of static circuit optimization with reduced size, degeneracy and redundancy by timing graph manipulation. static circuit optimization implies sizing of transistors and wires on a static timing basis, taking into account all paths through a circuit. previous methods of formulating static circuit optimization produce problem statements that are very large and contain inherent redundancy and degeneracy. in this paper, a method of manipulating the timing formulation is presented which produces a dramatically more compact optimization problem, and reduces redundancy and degeneracy. the circuit optimization is therefore more efficient and effective. numerical results to demonstrate these improvements are presented.
a unified signal transition graph model for asynchronous control circuit synthesis. both low-level (analysis-oriented) and high-level (specification-oriented) models for asynchronous circuits and the environment where they operate, together with strong equivalence results between the properties at the low levels, are described. one interesting side result is the precise characterization of classical static and dynamic hazards in terms of the model. consequently the designer can check the specification and directly decide if the behavior of any implementation will depend, e.g., on the delays of the signals described by such specification
solving the minimum-cost satisfiability problem using sat based branch-and-bound search. boolean satisfiability (sat) has seen many successful applications in various fields, such as electronic design automation (eda) and artificial intelligence (ai). however, in some cases it may be required/preferable to use variations of the general sat problem. in this paper we consider one important variation, the minimum-cost satisfiability problem (mincostsat). mincostsat is a sat problem which minimizes the cost of the satisfying assignment. mincostsat has various applications, e.g. automatic test pattern generation (atpg), fpga routing, ai planning, etc. this problem has been tackled before - first by covering algorithms, e.g. scherzo [3], and more recently by sat based algorithms, e.g. bsolo [16]. however the sat algorithms they are based on are not the current generation of highly efficient solvers. the solvers in this generation, e.g. chaff [20], minisat [5] etc., incorporate several new advances, e.g. two literal watching based boolean constraint propagation, that have delivered order of magnitude speedups. we first point out the challenges in using this class of solvers for the mincostsat problem and then present techniques to overcome these challenges. the resulting solver mincostchaff shows order of magnitude improvement over several current best known branch-and-bound solvers for a large class of problems, ranging from minimum test pattern generation, bounded model checking in eda to graph coloring and planning in ai.
hybrid floorplanning based on partial clustering and module restructuring. in this paper, we propose a hybrid floorplanning methodology. two hierarchical strategies for avoiding local optima during iterative improvement are proposed: (1) partial clustering, and (2) module restructuring. these strategies work for localizing nets connecting small modules in small regions, and conceal such small modules and their nets during the iterative improvement phase. this method is successful in reducing both area and wire length in addition to reducing the computational time required for optimization. although our method only searches slicing floorplans, the results are superior to the results obtained even with non-slicing floorplans. we applied our method to the largest mcnc floorplan benchmark example, ami49, and industrial data. for the ami49 benchmark, we obtained results superior to any published results for both estimated area and routing results.
clock skew optimization for ground bounce control. high speed synchronous digital systems require large switching currents to facilitate rapid signal transitions. these large currents create voltage drops on the power distribution network and necessitate expensive chip packaging with a large number of supply pins. in this paper we propose a novel technique to reduce the dynamic transient current drawn from the supply pins. our approach is based on sub-dividing the synchronous clocking into multiple sub-clocks with relative skew. this spreads the computation across the entire clock cycle instead of largely occurring at the beginning. timing constraints must also be obeyed, so that no races or timing errors are introduced. we propose an exact algorithm based on integer linear programming to solve this problem. we have used our method in the design of a 5ghz ecl encoder chip to achieve a factor of two reduction in ground bounce, as shown by hspice simulations. we also obtained order-of-magnitude improvements in ground bounce on benchmarks laid out in sub-micron cmos technology. the approach potentially leads to significant reductions in packaging costs.
a new method to express functional permissibilities for lut based fpgas and its applications. this paper presents a new method to express functional permissibilities for look-up table (lut) based field programmable gate arrays (fpgas). the method represents functional permissibilities by using sets of pairs of functions, not by incompletely specified functions. it makes good use of the properties of luts such that their internal logics can be freely changed. the permissibilities expressed by the proposed method have the desired property that at many points of a network they can be simultaneously treated. applications of the proposed method are also presented; a method to optimize networks and a method to remove connections that are obstacles at the routing step. preliminary experimental results are given to show the effectiveness of our proposed method.
mixed-size placement via line search. we describe a remarkably simple yet very effective line search technique for cell placement. our method "corrects" errors in force scaling by sampling different force weights in each iteration of placement and selecting the best candidate placements based on an objective function. our technique is not only very fast, but it does away with the need for the ad hoc scaling that has plagued prior force-directed methods. we describe the implementation of our method within a multilevel flow and show that it can achieve good wire lengths with competitive run-times compared to other academic tools. specifically, we produce placements with 12% and 15% better hpwl than fengshui 5.0 and capo 9.1, respectively, on the iccad04 mixed-size benchmarks, while presenting run-times that are 37% faster than capo 9.1.
engineering details of a stable force-directed placer. analytic placement methods that simultaneously minimize wire length and spread cells are receiving renewed attention from both academia and industry. we describe the implementation details of a force-directed placer, fdp. specifically, we provide: (1) a description of efficient force computation for spreading cells; (2) an illustration of numerical instability in these methods and a means by which these instabilities are avoided; (3) spread metrics for measuring cell distribution throughout the placement region; and (4) a complementary technique which aids in directly minimizing hpwl. we present results comparing our analytic placer to other academic tools for both standard cell and mixed-size designs. compared to kraftwerk and capo 8.7, our tool produces results with an average improvement of 9% and 3%, respectively.
combined dynamic voltage scaling and adaptive body biasing for heterogeneous distributed real-time embedded systems. dynamic voltage scaling (dvs) is a powerful technique for reducingdynamic power consumption in a computing system. however, astechnology feature size continues to scale, leakage power is increasing and willlimit power savings obtained by dvs alone. previous system-level real-timescheduling approaches use dvs alone to optimize power consumption withoutconsidering leakage power. to overcome this limitation, we propose a newscheduling algorithm that combines dvs and adaptive body biasing (abb)to simultaneously optimize both dynamic power consumption and leakagepower consumption for real-time distributed embedded systems. first, wederive an analytical expression to determine the optimal supply voltage andbody bias voltage under a given clock frequency. based on this expression, wecompute the optimal energy consumption at a given clock frequency and analyzethe tradeoff between energy consumption and execution time for a set oftasks with precedence relationships and real-time constraints. we then proposea scheduling algorithm to reduce total power consumption under givenreal-time constraints. this algorithm also considers variations in power consumptionof different tasks and characteristics of different voltage-scalableprocessing elements (pes) to maximize power reduction. experimental resultsshow that the average power reduction of our technique with respect todvs alone is 34.7%, while the average saving compared to no voltage scalingis 68.3% for the 0.07µm technology.
generalized matching from theory to application. we present a novel approach for post-mapping optimization. we exploit the concept of generalised matching, a technique that finds symbolically all possible matching assignments of library cells to a multi-output network specified by a boolean relation. several objectives are targeted: area minimization under delay constraints; power minimization under delay constraints; and unconstrained delay minimization. we describe the theory of generalized matching and the algorithmic optimization required for its efficient and robust implementation. a tool based on generalized matching has been implemented and tested on large examples of the mcnc'91 benchmark suite. we obtain sizable improvements in: speed (6% in average, up to 20.7%); area under speed constraints (13.7% an average, up to 29.5%); and power under speed constraints (22.3% in average, up to 38.1%).
optimized power-delay curve generation for standard cell ics. an effective way to compare logic techniques, logic families, or cell libraries is by means of power (or area) versus delay plots, since the efficiency of achieving a particular delay is of crucial significance. in this paper we describe a method of producing an optimized power versus delay curve for a combinational circuit. we then describe a method for comparing the relative merits of a set of power versus delay curves for a circuit, each generated with a different cell library. our results indicate that very few combinational functions need to be in a cell library, at most 11. the power-delay points achieved by design compiler from synopsys using the state-of-the-art artisan sage-x library compare unfavorably to our approach. in terms of minimum energy-delay product, our approach is superior by 79% on average. our approach yields the same delay points with a 107% savings in power consumption, on average. we also show that the specified vdd for a process technology should only be used for the absolute fastest implementations of a circuit.
hurwitz stable reduced order modelling for rlc interconnect trees. we present a new relizable reduced order modeling technique for rlc interconnect trees. both lumped and distributed wire models can be used with this technique. provable stability is achieved by using hurwitz polynomials. moment computation process is avoided but moments can still be matched implicitly. in experiments, the proposed hurwitz three-pole model can accurately and efficiently capture inductive effect for both near end and far end nodes.
timing-driven placement using design hierarchy guided constraint generation. design hierarchy plays an important role in timing-driven placement for large circuits. in this paper, we present a new methodology for delay budgeting based timing-driven placement. a novel slack assignment approach is described as well as its application on delay budgeting with design hierarchy information. the proposed timing-driven placement flow is implemented into a placement tool named dragon (timing-driven mode), and evaluated using an industrial place and route flow. compared to cadence qplace, timing-driven dragon generates placement results with shorter clock cycle and better routability.
efficient finite-difference method for quasi-periodic steady-state and small signal analyses. this paper discusses a finite-difference mixed frequency-time (mft) method for the quasi-periodic steady-state analysis and introduces the quasi-periodic small signal analysis. a new approach for solving the huge nonlinear system the mft finite difference method generates from practical circuits is given, which makes efficient frequency-sweeping quasi-periodic small-signal analysis possible. the new efficient solving technique works well with the krylovsubspace recycling or reuse [4], which can not be achieved with existing techniques. in addition, this paper gives a way to calculate the quasi-periodic fourier integration weights, necessary in the adjoint mft small-signal analyses, and a way to calculate quasi-periodic large-signal fourier spectrum that is more efficient than existing methods. numerical examples also show that the finite-difference mft method can be significantly more accurate than shooting-newton mft method and the new preconditioning technique is more efficient.
multi-level logic optimization of fsm networks. current approaches to compute and exploit the flexibility of a component in an fsm network are all at the symbolic level. conventionally, exploitation of this flexibility relies on state minimizers for incompletely specified fsms (isfsms) or pseudo non-deterministic fsms (pndfsm's). however, state-of-the art state minimizers cannot handle large isfsms or pndfsms. in addition, these exploitation techniques are at the symbolic level, not directly at the net-list logic level. we present a general approach to exploit exact or approximate flexibility directly at the net-list logic level, and we demonstrate that many sequential logic optimization techniques can be applied in exploitation. moreover, we propose a new procedure for input don't care sequences. as a result, both computation and exploitation of input don't care sequences in larger fsm networks can be made efficient and effective. finally, we give preliminary results on some artificially constructed fsm networks. preliminary results indicate that our approach can be effective in reducing the size of a component of an fsm network
gste through a case study. generalized symbolic trajectory evaluation (gste) [17, 18, 19] is a very significant extension of ste that has the power to verify all &omega;-regular properties but at the same time preserves the benefits of the original ste [16]. it also extends the symbolic quaternary model used by ste to support seamless model refinement for efficiency and accuracy trade-off in gste model checking. in this paper, we present a case study on fifo verification to illustrate the strength of gste and demonstrate its methodology in specifying and verifying large scale designs.