waashk/dblp huggingface dataset:
decomposition of timed decision tables and its use in presynthesis optimizations. presynthesis optimizations transform a behavioral hdl description into an optimized hdl description that results in improved synthesis results. we introduce the decomposition of timed decision tables (tdt), a tabular model of system behavior. the tdt decomposition is based on the kernel extraction algorithm. by experimenting using named benchmarks, we demonstrate how tdt decomposition can be used in presynthesis optimizations.
theoretical framework for compositional sequential hardware equivalence verification in presence of design constraints. we are interested in sequential hardware equivalence (or alignability equivalence) verification of synchronous sequential circuits as stated in c. pixley (1992). to cope with large industrial designs, the circuits must be divided into smaller subcircuits and verified separately. furthermore, in order to succeed in verifying the subcircuits, design constraints must be added to the subcircuits. these constraints mimic "essential" behavior of the subcircuit environment. in this work, we extend the classical alignability theory in the presence of design constraints, and prove a compositionality result allowing inferring alignability of the circuits from alignability of the subcircuits. as a result, we build a divide and conquer framework for alignability verification. this framework is successfully used on intel designs.
multigrid-like technique for power grid analysis. modern sub-micron vlsi designs include huge power grids that are required to distribute large amounts of current, at increasingly lower voltages. the resulting voltage drop on the grid reduces noise margin and increases gate delay, resulting in a serious performance impact. checking the integrity of the supply voltage using traditional circuit simulation is not practical, for reasons of time and memory complexity. we propose a novel multigrid-like technique for the analysis of power grids. the grid is reduced to a coarser structure, and the solution is mapped back to the original grid. experimental results show that the proposed method is very efficient as well as suitable for both dc and transient analysis of power grids.
cross-talk immune vlsi design using a network of plas embedded in a regular layout fabric. we present a vlsi design methodology to address the cross-talk problem, which is becoming increasingly important in deep sub-micron (dsm) ic design. in our approach, we implement the logic netlist in the form of a network of medium sized plas. we utilize two regular layout "fabrics" in our methodology, one for areas where pla logic is implemented, and another for routing regions between such logic blocks. we show that a single pla implemented in the first fabric style is not only cross-talk immune, but also about 2&times; smaller and faster than a traditional standard cell based implementation of the same logic. the second fabric, utilized in the routing region between individual plas, is also highly cross-talk immune. additionally, in this fabric, power and ground signals are essentially "pre-routed" all over the die.our synthesis flow involves decomposing the design into a network of plas, each of which has a bounded width and height. the number of inputs and outputs of each pla are flexible as long as the resulting pla width is bounded. we perform folding of plas to achieve better logic density. routing is performed using 2, 3, 4, 5 and 6 routing layers. state-of-the-art commercial routing tools are utilized for the experiments involving the use of 3, 4, 5 and 6 routing layers.we have implemented the entire design flow using these ideas. our scheme results in a reduction in the cross-talk between signal wires of between one and two orders of magnitude. as a result, for a 0.1&mu;m process, the delay variation due to cross-talk dramatically drops from 2.47:1 to 1.02:1. additionally, our methodology results in circuits that are extremely fast and dense, with a timing improvement of about 15% and an overall area penalty of about 3% compared to standard cells. the regular arrangement of metal conductors in our scheme results in low and highly predictable inductive and capacitive parasitics, resulting in highly predictable designs. the crosstalk immunity, high speed, low area overhead and high predictability of our methodology indicate that it is a strong candidate as the preferred design methodology in the dsm era.
assignment of global memory elements for multi-process vhdl specifications. a method for the synthesis of the global memory structure for a behavioral vhdl specification which consists of several concurrent processes is described. the global memory cells may be implemented as separate registers or rams. emphasis was laid on the minimization of both the area demand and timing demand due to access conflicts. the vhdl description is modeled as a petri net. the cases of this petri net are regarded as possible states of the system. the conflicts are then estimated on the basis of the probabilities that the system is in a certain state. finally the global signals are combined to larger memory structures by a clustering algorithm which is guided by both a decrease in area cost and possible conflicts
bit-level arithmetic optimization for carry-save additions. this paper addresses the bit-level optimization of carry-save adder (csa) arrays when the operands are of unequal wordlength (such as in some datapaths in digital signal processing circuits). we first show that by relaxing the carry-save representation to allow for more than two signals per bit position, we gain flexibility in the bit-level implementation of csa arrays that can be exploited to achieve a more efficient design. we then propose algorithms to optimize a single adder array at the bit-level. in addition, we proposed a heuristic to optimize a series of adder arrays that might occur in a datapath. we have applied our algorithms to the optimization of high-speed digital fir filters and have achieved 15% to 30% savings (weighted cost) in the overall filter implementation array in comparison to the standard carry-save implementation.
asf: a practical simulation-based methodology for the synthesis of custom analog circuits. this paper describes asf, a novel cell-level analog synthesis framework that can size and bias a given circuit topology subject to a set of performance objectives and a manufacturing process. to manage complexity and time-to-market, soc designs require a high level of automation and reuse. digital methodologies are inapplicable to analog ip, which relies on tight control of low-level device and circuit properties that vary widely across manufacturing processes. this analog synthesis solution automates these tedious, technology specific aspects of analog design. unlike previously proposed approaches, asf extends the prevalent "schematic and spice" methodology used to design analog and mixed-signal circuits. asf is topology and technology independent and can be easily integrated into a commercial schematic capture design environment. furthermore, asf employs a novel numerical optimization formulation that incorporates classical downhill techniques into stochastic search. asf consistently produces results comparable to expert manual design with 10x fewer candidate solution evaluations than previously published approaches that rely on traditional stochastic optimization methods.
generating sparse partial inductance matrices with guaranteed stability. this paper proposes a definition of magnetic vector potential that can be used to evaluate sparse partial inductance matrices. unlike the commonly applied procedure of discarding the smallest matrix terms, the proposed approach maintains accuracy at middle and high frequencies and is guaranteed to be positive definite for any degree of sparsity (thereby producing stable circuit solutions). while the proposed technique is strictly based upon potential theory (i.e. the invariance of potential differences on the zero potential reference choice), the technique is, nevertheless, presented and discussed in both circuit and magnetic terms. the conventional and the proposed sparse formulation techniques are contrasted in terms of eigenvalues and circuit simulation results on practical examples.
memory binding for performance optimization of control-flow intensive behaviors. this paper presents a memory binding algorithm for behaviors that are characterized by the presence of conditionals and deeply-nested loops that access memory extensively through arrays. unlike previous works, this algorithm examines the effects of branch probabilities and allocation constraints. first, we demonstrate, through examples, the importance of incorporating branch probabilities and allocation constraint information when searching for a performance-efficient memory binding. we also show the interdependence of these two factors and how varying one without considering the other may greatly affect the performance of the behavior. second, we introduce a memory binding algorithm that has the ability to examine numerous bindings by employing an efficient performance estimation procedure. the estimation procedure exploits locality of execution, which is an inherent characteristic of target behaviors. this enables the performance estimation technique to look at the global impact of the different bindings, given the allocation constraints.we tested our algorithm using a number of benchmarks from the parallel computing domain. a series of experiments demonstrates the algorithm's ability to produce bindings that optimize performance, meet memory allocation constraints, and adapt to different resource constraints and branch probabilities. results show that the algorithm requires 37% fewer memories with a performance loss of only 0.3% when compared to a parallel memory architecture. when compared to the best of a series of random memory bindings, the algorithm improves schedule performance by 21%.
generalized symmetries in boolean functions. in this paper we take a fresh look at the notion of symmetries in boolean functions. our studies are motivated by the fact that the classical characterization of symmetries based on invariance under variable swaps is a special case of a more general invariance based on unrestricted variable permutations. we propose a generalization of classical symmetry that allows for the simultaneous swap of ordered and unordered groups of variables, and show that it captures more of a function's invariant permutations without undue computational requirements. we apply the new symmetry definition to analyze a large set of benchmark circuits and provide extensive data showing the existence of substantial symmetries in those circuits. specific case studies of several of these benchmarks reveal additional insights about their functional structure and how it might be related to their circuit structure.
pipeline optimization for asynchronous circuits: complexity analysis and an efficient optimal algorithm. this paper addresses the problem of identifying the minimal pipelining needed in an asynchronous circuit (e.g., number/size of pipeline stages/latches required) to satisfy a given performance constraint, thereby implicitly minimizing area and power for a given performance. in contrast to the somewhat analogous problem of retiming in the synchronous domain, we first show that the basic pipeline optimization problem for asynchronous circuits is np-complete. this paper then presents an efficient branch and bound algorithm that can find the optimal pipeline configuration for moderately-sized problems. our experimental results on a few scalable system models demonstrate that our novel branch and bound solver can find the optimal pipeline configuration for models that have up to 235 possible pipeline configurations.
resynthesis of multi-level circuits under tight constraints using symbolic optimization. we apply recently introduced constructive multi-level synthesis in the resynthesis loop targeting convergence of industrial designs. the incremental ability of the resynthesis approach allows more predictable circuit implementations while allowing their aggressive optimization. the approach is based on a very general symbolic decomposition template for logic synthesis that uses information-theoretical properties of a function to infer its decomposition patterns (rather than more conventional measures such as literal counts). using this template the decomposition is done in a boolean domain unrestricted by the representation of a function, enabling superior implementation choices driven by additional technological constraints. the symbolic optimization is applied in resynthesis of industrial circuits which have tight timing constraints yielding their much improved timing properties.
leakage power optimization techniques for ultra deep sub-micron multi-level caches. on-chip l1 and l2 caches represent a sizeable fraction of the totalpower consumption of microprocessors. in deep sub-micron technology,the subthreshold leakage power is becoming the dominantfraction of the total power consumption of those caches. in thispaper, we present optimization techniques to reduce the leakagepower of on-chip caches assuming that there are multiple thresholdvoltages, vth's, available. first, we show a cache leakage optimizationtechnique that examines the trade-off between access timeand leakage power by assigning distinct vth's to each of the fourmain cache components - address bus drivers, data bus drivers,decoders, and sram cell arrays with sense-amps. second, we showoptimization techniques to reduce the leakage power of l1 and l2on-chip caches without affecting the average memory access time.the key results are: 1) 2 vth's are enough to minimize leakage in asingle cache; 2) if l1 size is fixed, increasing the l2 size can resultin much lower leakage without reducing average memory accesstime; 3) if l2 size is fixed, reducing l1 size can result in lower leakagewithout loss of the average memory access time; and 4) smallerl1 and larger l2 caches than are typical in today's processorsresult in significant leakage and dynamic power reduction withoutaffecting the average memory access time.
coupling-driven signal encoding scheme for low-power interface design. coupling effects between on-chip interconnects must be addressed in ultra deep submicron vlsi and system-on-a-chip (soc) designs. a new low-power bus encoding scheme is proposed to minimize coupled switchings which dominate the on-chip bus power consumption. the coupling-driven bus invert method use slim encoder and decoder architecture to minimize the hardware overhead. experimental results indicate that our encoding methods save effective switchings as much as 30% in an 8-bit bus with one-cycle redundancy.
a novel methodology for statistical parameter extraction. ic manufacturing process variations are typically expressed in terms of joint probability density function (jpdf's) or as worst case combinations/corners of the device model parameters. however, since device models can only provide approximations to actual device behavior, the difference between the two being the modeling error, only a part of the measured variation in device behavior can be modeled using device model parameter variations and the remaining appears as modeling error variation. in this paper, we present a novel statistical parameter extraction methodology that accounts for the effect of modeling error on device model parameter statistics and can be used to quantify the statistical suitability of conventional mos device models.
awe macromodels of vlsi interconnect for circuit simulation. the results of linear asymptotic waveform evaluation (awe) and of nonlinear circuit simulation are combined for the purpose of efficiently incorporating accurate interconnect information in the overall circuit description. a simple macromodel based on the y-parameter description of a complex interconnect network is discussed. the model makes possible the reduction of large, stiff interconnect configurations into compact representations that pose minimal problems to conventional circuit simulation techniques. the macromodel can be incorporated directly into a conventional circuit simulation with no modification of the original simulation software. the techniques are suitable for development as a software library that can be used to enhance existing simulators so that they can handle large vlsi interconnect configurations very efficiently. in addition, the ability to handle elements at the port level makes approach extremely attractive for any linear(ized) macromodels or for application such as mixed-mode simulation
adjustable width linear combinational scan vector decompression. a new scheme for combinational linear expansion isproposed for decompression of scan vectors. it has thecapability to adjust the width of the linear expansion each clockcycle. this eliminates the requirement that every scan bit-slicebe in the output space of the linear decompressor. depending onhow specified the current bit-slice is, the decompressor may loadall scan chains or may load only a subset of the scan chains.this provides the nice feature that any scan vector can begenerated using the proposed scheme regardless of the numberor distribution of the specified bits. thus, the proposed schemeallows the use of any atpg procedure without any constraints.moreover, it allows greater compression to be achieved thanfixed width expansion techniques since the ratio of the number ofscan chains to the number of tester channels can be scaled muchlarger. a procedure for designing and optimizing the adjustablewidth decompression hardware and obtaining the compresseddata is described. experimental data indicates that the proposedscheme is simple yet very effective.
behavior-to-placed rtl synthesis with performance-driven placement. interconnect delay should be considered together with computation delay during architectural synthesis in order to achieve timing closure in deep submicrometer technology. in this paper, we propose an architectural synthesis technique for distributed-register architecture, which separates interconnect delay for data transfer from component delay for computation. the technique incorporates performance-driven placement into the architectural synthesis to minimize performance overhead due to interconnect delay. experimental results show that our methodology achieves performance improvement of up to 60% and 22% on the average.
checking consistency of c and verilog using predicate abstraction and induction. it is common practice to write c models of circuits due to the greater simulation efficiency. once the c program satisfies the requirements, the circuit is designed in a hardware description language (hdl) such as verilog. it is therefore highly desirable to automatically perform a correspondence check between the c model and a circuit given in hdl. we present an algorithm that checks consistency between an ansi-c program and a circuit given in verilog using predicate abstraction. the algorithm exploits the fact that the c program and the circuit share many basic predicates. in contrast to existing tools that perform predicate abstraction, our approach is sat-based and allows all ansi-c and verilog operators in the predicates. we report experimental results on an out-of-order risc processor. we compare the performance of the new technique to bounded model checking (bmc).
automatic translation of behavioral testbench for fully accelerated simulation. this work presents the automated process of translating behavioral testbench into synthesizable one for the hardware-accelerated simulation. testbench is mainly implemented in unsynthesizable hdl description such as time delay, event control, non-static loops and sequential statements. nonetheless, fpga-based accelerator is limited to synthesizable design. to apply hardware acceleration to behavioral testbench, the proposed method automatically translates testbench into equivalent hardware by emulating the standard simulation reference model. by mapping testbench into hardware accelerator to be merged with the design under verification, we can accelerate behavioral testbench and remove the communication overhead between the software simulator and hardware accelerator. our experiments demonstrated that the simulation time is reduced by a factor of about 1000 as compared to the conventional hardware accelerated simulation.
static scheduling of multi-domain memories for functional verification. over the past decade both the quantity and complexity of available on-chip memory resources have increased dramatically. in order to ensure accurate asic behavior, both logic functions and memory resources must be successfully verified before fabrication. often, the functional verification of contemporary asic memory is complicated by the presence of multiple design clocks that operate asynchronously to each other. the presence of multiple clock domains presents significant challenges for large parallel verification systems such as parallel simulators and logic emulators that model both design logic and memory. specifically, multiple asynchronous design clocks make it difficult to verify that design hold times are met during memory model execution and causality along memory data/control paths is preserved during signal communication. in this paper, we describe new scheduling heuristics for memory-based designs with multiple asynchronous clock domains that are mapped to parallel verification systems. our scheduling approach scales to an unlimited number of clock domains and converges quickly to a feasible solution if one exists. it is shown that when our technique is applied to an fpga-based emulator containing 48mb of sram, evaluation fidelity is maintained and increased verification performance is achieved for large, memory-intensive circuits with multiple asynchronous clock domains.
a timing-driven data path layout synthesis with integer programming. we propose an efficient data path synthesis algorithm which generates bit-sliced layouts. since data path circuits have special characteristics which are different from those of random logic circuits, the dedicated synthesis system is required for efficient layouts. our main goal in the data path synthesis is to satisfy the timing constraints of circuits as well as to reduce layout areas. timing-driven placement and over-the-cell routing techniques are developed to generate data path modules. also, signal interfaces between bit-slices are carefully considered to further reduce layout areas. our synthesis techniques take advantage of the common characteristics of data path structures under timing constraints and applies mixed integer linear programming approach to solve the problem. the superior results from our data path synthesis system are demonstrated through comparison with the layout results with the simulated annealing technique.
metrics for structural logic synthesis. routability or wiring congestion in a vlsi chip is becoming increasingly important as chip complexity increases. congestion has a significant impact on performance, yield and chip area. although advances in placement algorithms have attempted to alleviate this problem, the inherent structure of the logic netlist has a significant impact on the routability irrespective of the placement algorithm used. placement algorithms find optimal assignment of locations to the logic and do not have the ability to change the netlist structure. significant decisions regarding the circuit structure are made early in synthesis such as during the technology independent logic optimization step. optimizations in this step use literal count as a metric for optimization and do not adequately capture the intrinsic entanglement of the netlist. two circuits with identical literal counts may have significantly different congestion characteristics post placement. in this paper, we motivate that a property of the network structure called adhesion can make a significant contribution to routing congestion. we then provide a metric to measure this property. we also show that adhesion as measured by this metric can be used in addition to literal counts to estimate and optimize post routing congestion early in the design flow.