waashk/dblp huggingface dataset:
extraction and lvs for mixed-domain integrated mems layouts. as design of integrated microelectromechanical systems (mems) matures, there is an increasing need for verification of mems layouts. this requires a mixed-domain lvs (layout-versus-schematic) methodology capable of extracting an integrated schematic from the mixed-domain layout and verifying it against the designed schematic. this paper reports on a prototype implementation of mems lvs and a mems extractor, which, in addition to reconstructing the extracted schematic also captures the domain-specific parasitics in the individual devices. this schematic is then used by a custom schematic-versus-schematic comparator to match connectivity of various elements between the designed and extracted schematics. finally, simulation of the extracted schematic also helps in capturing the true behavior of the system.
automatic generation and verification of sufficient correctness properties for synchronous processors. a general strategy for automatically generating and verifying sufficient correctness properties for a broad class of synchronous processors is presented. given a particular specification and implementation pair, it is shown how basic correctness properties can be algorithmically translated into a set of computation tree logic (ctl) formulae which are sufficient for equivalence between the behavioral and logic descriptions. preliminary experimental results on the verification of microcoded and array processors are presented
design exploration for high-performance pipelines. exploration plays an important role in the design of high-performance pipelines. we propose an exploration strategy for varying three design parameters by using a performance-constrained component selection and pipelining algorithm on different &ldquo;architectures&rdquo;. the architecture is specified manually by using a mix of behavioral and structural constructs, while the component selection and pipelining is performed automatically using our algorithms. results on two industrial-strength dsp systems, indicate the effectiveness of our strategy in exploring a large design space within a matter of seconds.
a new efficient approach to statistical delay modeling of cmos digital combinational circuits. this paper presents one of the first attempts to statistically characterize signal delays of basic cmos digital combinatorial circuits using the transistor level approach. hybrid analytical/iterative delay expressions in terms of the transistor geometries and technological process variations are created for basic building blocks. local delays of blocks along specific signal paths are combined together for the analysis of complex combinational vlsi circuits. the speed of analysis is increased by 2 to 4 orders of magnitude relative to spice, with about 5&ndash;10% accuracy. the proposed approach shows good accuracy in modeling the influence of the &ldquo;noise&rdquo; parameters on circuit delay relative to direct spice-based monte carlo analysis. examples of statistical delay characterization are shown. the important impact of the proposed approach is that statistical evaluation and optimization of delays in much larger vlsi circuits will become possible.
stars in vcc: complementing simulation with worst-case analysis. stars is a methodology for worst-case analysis of embedded systems. stars manipulates abstract representations of system components to obtain upper bounds on the number of various events in the system, as well as a bound on the response time. vcc is a commercial discrete event simulator, that can be used both for functional and performance verification. we describe an extension of vcc to facilitate stars. the extension allows the user to specify abstract representations of vcc modules. these abstractions are used by stars, but their validity can also be checked by vcc simulation. we also propose a mostly automatic procedure to generate these abstractions. finally, we illustrate on an example how stars can be combined with simulation to find bugs that would be hard to find by simulation alone.
statistical timing analysis for intra-die process variations with spatial correlations. process variations have become a critical issue in performanceverification of high-performance designs. we present a new, statisticaltiming analysis method that accounts for inter- and intra-dieprocess variations and their spatial correlations. since statisticaltiming analysis has an exponential run time complexity, we proposea method whereby a statistical bound on the probability distributionfunction of the exact circuit delay is computed with linear run time.first, we develop a model for representing inter- and intra-die variationsand their spatial correlations. using this model, we thenshow how gate delays and arrival times can be represented as a sumof components, such that the correlation information betweenarrival times and gate delays is preserved. we then show howarrival times are propagated and merged in the circuit to obtain anarrival time distribution that is an upper bound on the distributionof the exact circuit delay. we prove the correctness of the bound andalso show how the bound can be improved by propagating multiplearrival times. the proposed algorithms were implemented andtested on a set of benchmark circuits under several process variationscenarios. the results were compared with monte carlo simulationand show an accuracy of 3.32% on average over all test cases.
worst-case analysis of discrete systems. we propose a methodology for worst-case analysis of systems with discrete observable signals. the methodology can be used to verify different properties of systems such as power consumption, timing performance or resource utilization. we also propose an application of the methodology to timing analysis of embedded systems implemented on a single processor. the analysis provides a bound on the response time of such systems. it is typically very efficient, because it does not require a state space search.
statistical clock skew analysis considering intra-die process variations. with shrinking cycle times, clock skew has become an increasinglydifficult and important problem for high performance designs.traditionally, clock skew has been analyzed using case-files whichcannot model intra-die process variations and hence result in a veryoptimistic skew analysis. in this paper, we present a statistical skewanalysis method to model intra-die process variations. we firstpresent a formal model of the statistical clock skew problem and thenpropose an algorithm which is based on propagation of joint probabilitydistribution functions in a bottom up fashion in a clock tree.the analysis accounts for topological correlations between pathdelays and has linear run time with the size of the clock tree. theproposed method was tested on several large clock tree circuits,including a clock tree from a large industrial high-performancemicroprocessor. the results are compared with monte carlo simulationfor accuracy comparison and demonstrate the need for statisticalanalysis of clock skew.
iterative algorithms for formal verification of embedded real-time systems. most embedded real-time systems consist of many concurrent components operating at significantly different speeds. thus, an algorithm for formal verification of such systems must efficiently deal with a large number of states and large ratios of timing constants. we present such an algorithm based on timed automata, a model where a finite state system is augmented with time measuring devices called timers. we also present a semi-decision procedure for an extended model where timers can be decremented. this extension allows describing behaviors that are not expressible by timed automata, for example interrupts in a real-time operating system.
accurate estimation and modeling of total chip leakage considering inter- & intra-die process variations. in this paper we propose an accurate estimation and modeling of total circuit leakage distribution, considering both inter- and intra-die variations (variation in l, t/sub ox/ and random dopant fluctuation). since, the total leakage in a circuit depends on leakage in a transistor, integration of transistors in a logic gate, and the gate topology in a circuit block, we model the total circuit leakage distribution at all levels of circuit design, while taking the different correlations among transistors, logic gates, circuit topology, and input vectors into account. the proposed model accurately estimates both statistical information (mean and variance) and the shape of the leakage distribution. we have verified the model using monte carlo simulation using devices of 50nm effective length and analyzed the results to enumerate the effect of different process parameters on individual components of total leakage.
modeling non-slicing floorplans with binary trees. several novel topological representations of non-slicing floor-plans [2] have been more recently proposed, providing new ideas and techniques for solving block placement problems and other related layout applications. among these topological representations, ordered trees exhibit a lower redundancy and, therefore, a provable smaller search space, which makes them the best topological candidate for solving general block placement problems. starting from the early eighties, binary trees have been widely used to represent slicing floorplans [7]. this paper shows that binary trees can efficiently model non-slicing floorplans as well, as there is a one-to-one mapping between the sets of binary and ordered trees representing the floorplan. moreover, this paper shows that binary trees exhibiting a certain property can be used to represent block placement configurations with symmetry constraints, which is very useful when dealing with device-level placement problems for analog layout. as the number of these trees is proven to be smaller than the number of symmetric-feasible sequence-pairs [1], using binary trees is better than using either sequence-pairs or o-trees when solving analog placement problems. a comparative evaluation, substantiating these theoretical results, has been carried out by providing alternative optimization engines to a placement tool operating in an industrial environment.
hierarchical performance macromodels of feasible regions for synthesis of analog and rf circuits. accurate performance modeling is essential for its usage in a circuit synthesis flow. only a small fraction of the entire design space is occupied by designs with meaningful behavior and performance. in this work, we have focussed on modeling these feasible regions accurately in contrast with modeling the entire design space. macromodels for the feasible regions were built hierarchically until the desired accuracy was achieved. an accuracy driven synthesis methodology is proposed to guide the identification of the feasible regions and dynamically enhance the performance of the macromodels. dynamic performance modeling ensures true convergence of our synthesis approach as opposed to existing static macromodel based techniques. we applied the proposed methodology for modeling and synthesis of several analog and rf circuits and the results demonstrate that our approach yields highly accurate design solutions in a much smaller time compared to simulation based approaches.
speeding up technology-independent timing optimization by network partitioning. technology-independent timing optimization is an important problem in logic synthesis. although many promising techniques have been proposed in the past, unfortunately they are quite slow and thus impractical for large networks. in this paper, we propose depart, a delay-based partitioner-cum-optimizer, which purports to solve this problem. given a combinational logic network that is to be optimized for timing, depart divides it into sub-networks using timing information and a constraint on the maximum number of gates allowed in a single sub-network. these sub-networks are then dispatched, one by one, to a standard timing optimizer. the optimized sub-networks are re-glued, generating an optimized network. the challenge is how to partition the original network into sub-networks so that the final solution quality after partitioning and optimization is comparable to that from the timing optimizer. we propose a partitioning technique that is timing-driven and is simple yet effective. we compare depart with speed_up, a state-of-the-art timing optimization tool, and with various partitioning techniques such as min-cut based and region growing, on a suite of large industrial and iscas circuits. on more than half of the benchmarks, depart yields run-time improvements of 20 to 450 times over a normal invocation of speed_up (the overall average improvement being 8 times), without compromising the solution quality much. min-cut and region growing partitioning schemes, not being timing-driven, perform poorly in terms of the final circuit delay.
dataflow-driven memory allocation for multi-dimensional signal processing systems. memory cost is responsible for a large amount of the chip and/or board area of customized video and image processing systems. in this paper, a novel background memory allocation and assignment technique is presented. it is intended for a behavioural algorithm specification, where the procedural ordering of the memory related operations is not yet fully fixed. instead of the more restricted classical scheduling-based explorations, starting from procedurally interpreted specifications in terms of loops, a novel optimization approach&mdash;driven by data flow analysis&mdash;is proposed. employing the estimated silicon area as a steering cost, this allocation/assignment technique yields one or (optionally) several distributed (multi-port) memory architecture(s) with fully-determined characteristics, complying with a given clock cycle budget for read/write operations. moreover, our approach can accurately deal with complex multi-dimensional signals by means of a polyhedral data-flow analysis operating with groups of scalars.
an architecture and a wrapper synthesis approach for multi-clock latency-insensitive systems. this paper presents an architecture and a wrapper synthesis approach for the design of multi-clock systems-on-chips. we build upon the initial work on multi-clock latency-insensitive systems by singh and theobald (2004), and provide a detailed system architecture with the following capabilities and benefits: (i) modules arc stalled only when needed, thereby avoiding unnecessary stalling, (ii) adequate metastability resolution is provided, (iii) handshake interfaces between modules are high-performance and low-latency, i.e., capable of transferring data packets on every clock cycle, (iv) ip cores with large clock distribution delays are correctly handled, and (v) an automated approach is provided for wrapper synthesis from formal specifications. for wrapper synthesis, we have developed an automated tool which accepts interface specifications in a high-level language (component wrapper language, or cwl), and automatically produces gate-level implementations of wrapper circuitry that will correctly and efficiently stall the synchronous modules depending on the availability of i/o channels. an optimization is introduced to reduce the cost of the wrapper circuitry by eliminating "busy waiting." a small set of benchmark examples is also proposed, and synthesis results for the tool are promising.
sequential synthesis using s1s. we present a mathematical framework for analyzing the synthesis of interacting finite state systems. the logic s1s is used to derive simple, rigorous, and constructive solutions to problems in sequential synthesis. we obtain exact and approximate sets of permissible fsm network behavior, and address the issue of fsm realizability. this approach is also applied to synthesizing systems with fairness and timed systems.
flute: fast lookup table based wirelength estimation technique. wirelength estimation is an important tool to guide the design optimization process in early design stages. in this paper, we present a wirelength estimation technique called flute. our technique is based on pre-computed lookup table to make wirelength estimation very fast and very accurate for low degree nets. we show experimentally that for flute, rmst, and hpwl, the average error in wirelength are 0.72%, 4.23%, and -8.71%, respectively, and the normalized runtime are 1, 1.24, and 0.16, respectively.
fractional cut: improved recursive bisection placement. in this paper, we present improvements to recursive bisection basedplacement. in contrast to prior work, our horizontal cut lines arenot restricted to row boundaries; this avoids a "narrow region"problem. to support these new cut line positions, a dynamic programmingbased legalization algorithm has been developed. thecombination of these has improved the stability and lowered thewire lengths produced by our feng shui placement tool.on benchmarks derived from industry partitioning examples,our results are close to those of the annealing based tool dragon,while taking only a fraction of the run time. on synthetic benchmarks,our wire lengths are nearly 23% better than those of dragon.for both benchmark suites, our results are substantially better thanthose of the recursive bisection based tool capo and the analyticplacement tool kraftwerk.
efficient solution space exploration based on segment trees in analog placement with symmetry constraints. the traditional way of approaching devicelevel placement problems for analog layout is to explore a huge search space of absolute placement representations, where cells are allowed to illegally overlap during their moves [2, 7, 8]. this paper presents a novel analog placement technique operating on the set of binary tree representations of the layout [3], where the typical presence of an arbitrary number of symmetry groups of devices is directly taken into account during the exploration of the solution space. the efficiency of the novel approach is due to a data structure called segment tree, mainly used in computational geometry.
coupled analysis of electromigration reliability and performance in ulsi signal nets. in deep submicron vlsi circuits, interconnect reliability due to electromigration and thermal effects is fast becoming a serious design issue particularly for long signal lines. this paper presents for the first time a rigorous coupled analysis of ac electromigration that are prevalent in signal lines and thermal effects arising due to joule heating of the wires. the analysis is applied to study the effect of technology scaling using itrs data, wherein the effects of increasing interconnect (cu) resistivity with line dimensions and the effect of a finite barrier metal thickness have been included. finally, we have also quantified the reliability implications for minimum sized vias in optimally buffered signal nets. our analysis suggests that for the optimally buffered interconnects, while the maximum current density in the line remains limited by the performance, the current density in the vias exceeds the reliability limits and therefore requires careful consideration in the physical design process flow.
compact and complete test set generation for multiple stuck-faults. we propose a novel procedure for testing all multiple stuck-faults in a logic circuit using two complementary algorithms. the first algorithm finds pairs of input vectors to detect the occurrence of target single stuck-faults independent of the occurrence of other faults. the second uses a sophisticated branch and bound procedure to complete the test set generation on the faults undetected by the first algorithm. the technique is complete and applies to all circuits. experimental results presented in this paper demonstrate that compact and complete test sets can be quickly generated for standard benchmark circuits.
timing analysis in presence of power supply and ground voltage variations. given the sensitivity of circuit delay to supply and ground voltagevalues, static timing analysis (sta) must take into account supplyvoltage variations. existing sta techniques allow one to verifythe timing at different process corners which effectively only considers cases where all the supplies are low or all are high. cases of mismatch between the supplies of driver and load are not considered. in practice, supply voltages are neither totally independentnor totally dependent. in this work, we consider the supply andground nodes of a logic gate to be either totally independent variables, or to be directly tied or connected to those of some other gate(s) in the circuit. we also assume that the exact supplyvoltage values are not known exactly, but that only upper/lowerbounds on them are known. in this framework, we propose newtiming models for logic gates and identify the worst-case voltagecon gurations for individual gates and for simple paths. we thengive an sta technique that provides the worst-case circuit delaytaking supply variations into account.
track assignment: a desirable intermediate step between global routing and detailed routing. routing is one of the most complex stages in the back-end design process. simple routing algorithms based on two stages of global routing and detailed routing do not offer appropriate opportunities to address problems arising from signal delay, cross-talk and process constraints. an intermediate stage of track assignment between global and detailed routing proves to be an ideal place to address these problems. with this stage it is possible to use global routing information to efficiently address these problems and to aid the detailed router in achieving the wiring completions. in this paper we formulate routing as a three stage process; global routing, track assignment and detailed routing. we describe the intermediate track assignment problem and suggest an efficient heuristic for its solution. we introduce cost metrics to model basic effects arising from connectivity. we discuss extensions to include signal integrity and process constraints. we propose a heuristic based on weighted bipartite matching as a core routine. to improve its performance additional heuristics based on lookahead and segment splitting are also suggested. experimental results are given to highlight the efficacy of track assignment stage in routing process.
m-trie: an efficient approach to on-chip logic minimization. boolean logic minimization is being increasingly applied to new applications which demands very fast and frequent minimization services. these applications typically offer very limited computing and memory resources rendering the traditional logic minimizers ineffective. we present a new approximate logic minimization algorithm based on ternary trie. we compare its performance with espresso-ii and rocm logic minimizers for routing table compaction and demonstrate that it is 100 to 1000 times faster and can run with a data memory as little as 16kb. it is also found that proposed approach can support up to 25000 incremental updates per seconds positioning itself as an ideal on-chip logic minimization algorithm.