waashk/dblp huggingface dataset:
performance-driven synthesis of asynchronous controllers. we examine the implications of a new hazard-free combinational logic synthesis method, which generates multiplexor trees from binary decision diagrams (bdds)&mdash;representations of logic functions factored recursively with respect to input variables&mdash;on extended burst-mode asynchronous synthesis. first, the use of the bdd-based synthesis reduces the constraints on state minimization and assignment, which reduces the number of additional state variables required in many cases. second, in cases where conditional signals are sampled, it eliminates the need for state variable changes preceding output changes, which reduces overall input to output latency. third, selection variables can easily be ordered to minimize the latency on a user-specified path, which is important for optimizing the performance of systems that use asynchronous components. we present extensive evaluations showing that, with only minimal optimization, the bbd-based synthesis gives comparable results in area with our previous exact two-level synthesis method. we also give a detailed example of the specified path optimization.
fpga device and architecture evaluation considering process variations. process variations in nanometer technologies are becoming an important issue for cutting-edge fpgas with a multi-million gate capacity. considering both die-to-die and within-die variations in effective channel length, threshold voltage, and gate oxide thickness, we first develop closed-form models of leakage and timing variations at the fpga chip level. experiments show that our models are within 3% from monte carlo simulation, and the leakage and delay variations can be up to 3/spl times/ and 1.9/spl times/, respectively. we then derive analytical yield models considering both leakage and timing variations, and use such models to evaluate fpga device and architecture under process variations. compared to the architecture similar to a commercial fpga and device setting from itrs roadmap, device tuning alone improves leakage yield by 39% and architecture and device co-optimization increases leakage yield by 73%. we also show that lut size 4 gives the highest leakage yield, lut size 7 gives the highest timing yield, but lut size 5 achieves the maximum combined leakage and timing yield. to the best of our knowledge, this is the first in-depth study on fpga device and architecture co-evaluation considering process variations.
scalable compositional minimization via static analysis. state-equivalence based reduction techniques, e.g. bisimulation minimization, can be used to reduce a state transition system to facilitate subsequent verification tasks. however, the complexity of computing the set of equivalent state pairs often exceeds that of performing symbolic property checking on the original system. we introduce a fully-automated efficient compositional minimization approach which requires only static analysis. key to our approach is a heuristic algorithm that identifies components with high reduction potential in a bit-level netlist. we next inject combinational logic which restricts the component's inputs to selected representatives of symbolically-computed equivalence classes thereof. finally, we use existing transformations to synergistically exploit the dramatic netlist reductions enabled by these input filters. experiments confirm that our technique is able to efficiently yield substantial reductions on large industrial netlists.
wire-length prediction using statistical techniques. we address the classic wire-length estimation problem and propose a new statistical wire-length estimation approach that captures the probability distribution function of net lengths after placement and before routing. the wire-length prediction model was developed using a combination of parametric and non-parametric statistical techniques. the model predicts not only the length of the net using input parameters extracted from the floorplan of a design, but also probability distributions that a net with given characteristics obtained after placement will have a particular length. the model is validated using both learn-and-test and resubstitution techniques. the model can be used for a variety of purposes, including the generation of a large number of statistically sound and therefore realistic instances of designs. we applied the net models to the probabilistic buffer insertion problem and obtained substantial improvement in net delay after routing.
general framework for removal of clock network pessimism. the paper presents a simple yet powerful general theoretical framework and efficient implementation for removal of clock network timing pessimism. we address pessimism in static timing analysis (sta) tools caused by considering delay variation along common segments of clock paths. the sta tools compute setup (hold) timing slack based on conservative combinations of late (early) launching and early (late) capturing arrival times. to avoid exponential-time path-based analysis the sta tools use both early and late arrival times on gates common to both launching and capturing paths. it is impossible in real circuit and is observed as the clock network pessimism in sta. our approach supports any kind of delay variation though the typical causes of the pessimism are process, voltage, and temperature on-chip variation, and reconvergence in clock network. we propose a new theoretical framework that allows to apply known graph algorithms instead of time consuming forward and backward multi-pass tracing algorithms and heuristics that are limited to some network topologies [4]. the new graph-based framework supports clock networks of virtually any size and type, e.g., tree, mesh, hybrid, clock gating, chains of multipliers and dividers, loops in such chains, etc. the implementation based on the proposed framework has proven its strength in a commercial sign-off static timing analyzer and thus is helping hundreds of designers to achieve faster clock speeds of their chips.
paras: system-level concurrent partitioning and scheduling. partitioning for the asic designs is examined and the interaction between high-level synthesis and partitioning is studied and incorporated in the solution. four algorithms (called paras) which can exploit this interaction by solving the scheduling and partitioning problems concurrently are presented. paras maximizes the overall performance of the final design and considers different chip configurations and communication structures. experiments, conducted with specifications ranging in size from few to hundreds of operations, demonstrate the success of this approach.
a technology-independent cad tool for esd protection device extraction: esdextractor. the challenges for developing an esd (electro-static discharge) layout extractor originate from unconventional layout patterns of esd protection devices, parasitic esd device extraction and device count reduction. this paper reports a new technology-independent layout extractor, esdextractor, which is capable of extracting all types of esd devices and answers the demands for esd design verification. general methodology to extract both intentional and parasitic esd devices, specific algorithms and implementation methods for efficiencyenhancement are presented, followed by a design example.
a probabilistic constructive approach to optimization problems. we propose a new optimization paradigm for solving intractable combinatorial problems. the technique, named probabilistic constructive (pc), combines the advantages of both constructive and probabilistic algorithms. the constructive aspect provides relatively short runtime and makes the technique amenable for the inclusion of insights through heuristic rules. the probabilistic nature facilitates a flexible trade-off between runtime and the quality of solution.in addition to presenting the generic technique, we apply it to the maximal independent set problem. extensive experimentation indicates that the new approach provides very attractive trade-offs between the quality of the solution and runtime, often outperforming the best previously published approaches.
a high efficiency full-chip thermal simulation algorithm. thermal simulation has become increasingly important in chip design, especially in the nanometer regime, where the on-chip hot spots severely degrade the performance and reliability of the circuit and increase the leakage power. in this paper, we present a highly efficient and accurate thermal simulation algorithm that is capable of performing full-chip temperature calculations at the cell level. the algorithm is a combination of several important numerical techniques including the green function method, the discrete cosine transform (dct), and the frequency domain computations. experimental results show that our algorithm can achieve orders of magnitude speedup compared with previous green function based algorithms while maintaining the same accuracy.
gate-level simulation of digital circuits using multi-valued boolean algebras. this paper describes an algorithm for the simulation of gate-level logic. multiple logic levels are used to describe the state of each node. each state corresponds to a different voltage level, and the number of levels to be used for a simulation is user-defined. this feature simplifies considerably the interface between a digital and an analog simulator. a dc solver is incorporated to find the initial operating point of a circuit before a transient analysis begins. this solver has the capability of finding the operating point of gates located in feedback loops. for transient analysis, a gate delay model that takes into account the slope of the input waveforms is used. the performance of the algorithm is demonstrated by simulations of a number of benchmark circuits.
statistical critical path analysis considering correlations. critical path analysis is always an important task in timing verification. for todays nanometer ic technologies, process variations have a significant impact on circuit performance. the variability can change the criticality of long paths (gattiker et al., 2002). therefore, statistical approaches should be incorporated in critical path analysis. in this paper, we present two novel techniques that can efficiently evaluate path criticality under statistical non-linear delay models. they are integrated into a block-based statistical timing tool with the capability of handling arbitrary correlations from manufacturing process dependence and also path sharing. experiments on iscas85 benchmarks as well as industrial circuits prove both accuracy and efficiency of these techniques.
efficient solution of systems of boolean equations. this paper describes an algorithm for the efficient solution of large systems of boolean equations. the algorithm exploits the fact that, in some cases, the composition operation of boolean functions represented by bdd's can be performed in a very efficient manner. thus, the algorithm tries to eliminate as many variables and equations as possible through function composition. when the system can no longer be reduced in this way, the elimination process is continued through the use of shannon decomposition. numerical results show that the performance of this algorithm is significantly superior to that of a previous algorithm proposed by the authors.
energy-aware fault tolerance in fixed-priority real-time embedded systems. we investigate an integrated approach to fault tolerance anddynamic power management in real-time embedded systems. faulttolerance is achieved via checkpointing and power management iscarried out using dynamic voltage scaling (dvs). we presentfeasibility-of-scheduling tests for checkpointing schemes for aconstant processor speed as well as for variable processor speeds.dvs is then carried out on the basis of these feasibility analyses.experimental results show that compared to fault-obliviousmethods, the proposed approach significantly reduces powerconsumption and guarantees timely task completion in the presence of faults.
soft self-synchronising codes for self-calibrating communication. self-calibrating designs are gaining momentum in both the computation and communication worlds. instead of relying on the worst-case characterisation of design parameters, self calibrating systems determine autonomously the boundary of correct behaviour, and set design parameters accordingly. we focus on the communication task. we model errors due to over-aggressive operation and derive a channel model. we show that self-synchronising codes achieve completely reliable communication over this channel model, and study a known example, ledr (level encoded 2-phase dual-rail), which is an improvement of the well-known dual-rail code. then, we introduce a family of coding schemes which are a generalisation of ledr, and study their performance over our channel model. we observe that the wiring overhead can be significantly reduced at the expense of a limited loss in reliability. finally, we extend our channel model to include additive noise, and show that in this more general situation a specific instance of our coding scheme has similar or better performance than ledr, at a smaller wiring overhead.
gradual relaxation techniques with applications to behavioral synthesis. heuristics are widely used for solving computational intractablesynthesis problems. however, until now, there has been limitedeffort to systematically develop heuristics that can be applied to avariety of synthesis tasks. we focus on development of generaloptimization principles so that they can be applied to a wide rangeof synthesis problems. in particular, we propose a new way torealize the most constraining principle where at each step wegradually relax the constraints on the most constrained elementsof the solution. this basic optimization mechanism is augmentedwith several new heuristic principles: minimal freedom reduction,negative thinking, calibration, simultaneous step consideration,and probabilistic modeling.we have successfully applied these optimization principles to anumber of common behavioral synthesis tasks. specifically, wedemonstrate a systematic way to develop optimization algorithmsfor maximum independent set, time-constrained scheduling, andsoft real-time system scheduling. the effectiveness of theapproach and algorithms is validated on extensive real-lifebenchmarks.
a data flow fault coverage metric for validation of behavioral hdl descriptions. behavioral hdl descriptions are commonly used to capture the high-level functionality of a hardware circuit for simulation and synthesis. the manual process of creating a behavioral description is error prone, so significant effort must be made to verify the correctness of behavioral descriptions. simulation-based validation and formal verification are both techniques used to verify correctness. we investigate validation because formal verification techniques are frequently intractable for large designs. the first step toward a behavioral validation technique is the development of a validation fault coverage metric which can be used to evaluate the likelihood of design defect detection with a given test sequence.we propose a validation fault coverage metric which is based on an analysis of the control data flow description associated with the behavior. the proposed metric identifies a subset of paths through the data flow which must be traversed during testing to detect faults. the proposed metric is a tractable compromise between the statement coverage metric which requires only that each statement be executed, and the path coverage metric which requires that all data flow paths be executed. data flow paths are identified based on the relative code locations of definitions and uses of variables which may be assigned incorrectly due to a design error. we propose an efficient method to compute all data flow paths which must be traversed, and we generate coverage results for several benchmark vhdl circuits for comparison to other approaches.
area minimization of power distribution network using efficient nonlinear programming techniques. this paper deals with area minimization of power distribution network for vlsis. a new algorithm based on efficient nonlinear programming techniques is presented to solve this problem. the experiment results prove that this algorithm has achieved the objects that minimize the area of power/ground networks with higher speed.
partial bist insertion to eliminate data correlation. a new partial bist insertion approach based on eliminating data correlation to improve pseudo-random testability is presented. data correlation causes the circuit to be in a subset of the states more or less frequently, which leads to low fault coverage in pseudo-random test. one important cause of correlation is reconvergent fanout. incorporating bist test flip-flops into reconvergent paths will break correlation, however, breaking all reconvergent fanout is unnecessary since some reconvergent fanout results in negligible correlation. we introduce a metric to determine the degree of correlation caused by a set of reconvergent fanout paths. we use this metric to identify problematic reconvergent fanout which must be broken through partial bist insertion. we provide an algorithm to break high correlation reconvergent paths. our algorithm provides high fault coverage while selecting fewer bist flip-flops than required using loop breaking techniques. experimental results produced using our algorithm rank on average among the top 11.6% of all possible solutions with the same number of flip-flops.
an efficient multi-view design model for real-time interactive synthesis. an efficient multiview design model for real-time interactive synthesis of behavioral descriptions into layout data is described. a hybrid data structure which combines all of the design data needed throughout multiple levels of abstraction, including behavior, structure, and floorplan, into a single unified view is presented. a detailed time and space complexity analysis of the proposed design model is also given, showing that it provides fast updating capabilities for incremental design changes but does not require an exorbitant amount of memory space. these features make this design model ideal for user-controlled synthesis systems that support incremental design and redesign tasks. furthermore, the simplicity of the data structure allows easy implementation, maintenance, and extensibility
conflict driven learning in a quantified boolean satisfiability solver. within the verification community, there has been a recent increase in interest in quantified boolean formula evaluation (qbf) as many interesting sequential circuit verification problems can be formulated as qbf instances. a closely related research area to qbf is boolean satisfiability (sat). recent advances in sat research have resulted in some very efficient sat solvers. one of the critical techniques employed in these solvers is conflict driven learning. in this paper, we adapt conflict driven learning for application in a qbf setting. we show that conflict driven learning can be regarded as a resolution process on the clauses. we prove that under certain conditions, tautology clauses obtained from resolution in qbf also obey the rules for implication and conflicts of regular (non-tautology) clauses; and therefore they can be treated as regular clauses and used in future search. we have implemented this idea in a new qbf solver called quaffle and our initial experiments show that conflict driven learning can greatly speed up the solution process for most of the benchmarks we tested.
error catch and analysis for semiconductor memories using march tests. we present an error catch and analysis (eca) system for semiconductor memories. the system consists of a test algorithm generator called tags, a fault simulator called ram-ses, and an error analyzer (era). we use tags to generate a set of test algorithms of different lengths and diagnostic resolutions for the memory under test, and use ramses to generate the march dictionary for each test algorithm. with the march dictionaries, era is able to support march algorithms for easy diagnosis of faulty rams. legacy test algorithms also can be reused. when integrated with a ram tester, our eca system can generate ram bitmaps that are similar to the ram layout. the bitmaps provide detail information about the error locations and faults causing the errors. based on the information, diagnosis of the ram chips for yield and reliability improvement can be done more easily.
incremental deductive & inductive reasoning for sat-based bounded model checking. bounded model checking (bmc) based on boolean satisfiability (sat) methods has recently gained popularity as a viable alternative to bdd-based techniques for verifying large designs. this work proposes a number of conceptually simple, but extremely effective, optimizations for enhancing the performance of sat-based bmc flows. the key ideas include: (1) a novel idea to combine sat-based inductive reasoning and bmc; (2) clever orchestration of variable ordering and learned information in an incremental framework for bmc; and (3) bmc-specific ordering strategies for the sat solver. our experiments, conducted on a wide range of industrial designs, show that the proposed optimizations consistently provide between 1-2 orders of magnitude speedup and can be extremely useful in enhancing the efficacy of typical sat-bmc tools.
post-placement voltage island generation under performance requirement. high power consumption not only leads to short battery life for handheld devices, but also causes on-chip thermal and reliability problems in general. as power consumption is proportional to the square of supply voltage, reducing supply voltage can significantly reduce power consumption. multi-supply voltage (msv) has previously been introduced to provide finer-grain power and performance trade-off. in this work we propose a methodology on top of a set of algorithms to exploit non-trivial voltage island boundaries for optimal power versus design cost trade-off under performance requirement. our algorithms are efficient, robust and error-bounded, and can be flexibly tuned to optimize for various design objectives (e.g., minimal power within a given number of voltage islands, or minimal fragmentation in voltage islands within a given power bound) depending on the design requirement. our experiment on real industry designs shows a ten-fold improvement of our method over current logical-boundary based industry approach.
stochastic wire-length and delay distribution of 3-dimensional circuits. 3-d technology promises higher integration density and lower interconnection complexity and delay. at present, however, not much work on circuit applications has been done due to lack of insight into 3-d circuit architecture and performance. in this paper, we investigate the interconnect distributions of 3-d circuits. we divide the 3-d interconnects into horizontal wires and vertical wires and derive their wire-length distributions, respectively. based on the stochastic wire-length distributions, we calculate 3-d circuit interconnect delay distribution. we show that 3-d structures effectively reduce the number of long delay nets, significantly reduce the number of repeaters needed, and dramatically improve the performance. with 3-d structures, a circuit can work at a much higher clock rate (double, even triple) than with 2-d. however, we also show that the impacts of vertical wires on chip area and interconnect delay may limit the number of device layers that we can integrate.