waashk/dblp huggingface dataset:
the sizing rules method for analog integrated circuit design. this paper presents the sizing rules method for analog cmos circuit design that consists of: first, the development of a hierarchical library of transistor pair groups as basic building blocks for analog cmos circuits; second, the derivation of a hierarchical generic list of constraints that must be satisfied to guarantee the function of each block and its reliability with respect to physical effects; and third, the development of an automatic recognition of building blocks in a circuit schematic. the sizing rules method efficiently captures design knowledge on the technology-specific level of transistor pair groups. this reduces the preparatory modeling effort for analog circuit synthesis. results of industrial applications to circuit sizing, design centering, response surface modeling and analog placement show the significance of the sizing rules method. sizing rules especially make sure that automatic circuit sizing and design centering lead to technically meaningful and robust results.
e-proofs: a cmos bridging fault simulator. the problem of bridging fault simulation under the conventional voltage testing environment is considered. a method to provide electrical-level simulation accuracy, without paying the associated performance penalties, is proposed. a three-level simulation model is used, balancing the tradeoffs among gate-level, switch-level, and electrical-level simulation. large memory overheads are avoided by localizing the fault, and by performing electrical-level simulation only in the area around the fault. this approach is sufficiently flexible to model feedback faults, bicmos circuits, stuck-open faults, and any fault that can be described with a circuit netlist. tests were run on several iscas combinational and sequential benchmark circuits, using realistic cells and transistor parameters; results show that accurate simulations can be performed in reasonable time
a delay model for logic synthesis of continuously-sized networks. abstract: we present a new delay model for use in logic synthesis. a traditional model treats the area of a library cell as constant and makes the cell's delay a linear function of load. out model is based on a different, but equally fundamental linearity in the equation relating area, delay, and load: namely, we may keep a cell's delay constantly making its area a linear function of load. this allows us to technology map using a library with continuous device sizing, satisfies certain electrical noise and power constraints, and in certain cases is computationally simpler than a traditional model. we give results to support these claims. a companion paper uses the computational simplicity to explore a wide search space of algebraic factorings in a mapped network.
optimal latch mapping and retiming within a tree. we propose a technology mapping algorithm that takes existing structural technology-mapping algorithms based on dynamic programming and extends them to retime pipelined circuits. if the circuit to be mapped has a tree structure, our algorithm generates an optimal solution compatible with that structure. the algorithm takes into account gate delays and capacitive loads as latches are moved across the logic. it also supports latches with embedded logic: i.e., cells that combine a d latch with a combinational gate at little extra cost in latch delay.
mist: an algorithm for memory miss traffic management. cache misses represent a major bottleneck in embedded systems performance. traditionally, compilers optimistically treated all memory accesses as cache hits, relying on the memory controller to account for longer miss delays. however, the memory controller has only a local view of the program, and is not able to efficiently hide the latency of these memory operations. our compiler technique actively manages cache misses, and performs global miss traffic optimizations, to better hide the latency of the memory operations. our memory-aware compiler scheduled several benchmarks on the tic6211 processor architecture with a direct mapped cache, and generated an average of 61.6% improvement over the best schedule of the traditional (memory-transparent) optimizing compiler, demonstrating the utility of our miss traffic optimization approach.
efficient manipulation algorithms for linearly transformed bdds. binary decision diagrams (bdds) are the state-of-the-art data structure in vlsi cad. but due to their ordering restriction only exponential sized bdds exist for many functions of practical relevance. linear transformations (lts) have been proposed as a new concept to minimize the size of bdds and it is known that in some cases even an exponential reduction can be obtained.in addition to a small representation, the efficient manipulation of a data structure is also important. in this paper we present polynomial time manipulation algorithms that can be used for linearly transformed bdds (lt-bdds) analogously to bdds. for some operations, like synthesis algorithms based on ite, it turns out that the techniques known from bdds can be directly transferred, while for other operations, like quantification and cofactor computation, completely different algorithms have to be used. experimental results are given to show the efficiency of the approach.
iterative abstraction using sat-based bmc with proof analysis. resolution-based proof analysis techniques have been proposedrecently to identify a sufficient set of reasons for unsatisfiabilityderived by a cnf-based sat solver. we have adapted thesetechniques to work with a hybrid sat solver. we use the proofanalysis technique with sat-based bmc, in order to generateuseful abstract models. our abstraction procedure is usediteratively in a top-down framework, starting from the concretedesign, where we apply bmc on increasingly more abstractmodels. we apply various sat-based and bdd-basedverification methods on these abstract models, in order to obtainproofs of correctness, or to perform deeper searches forcounterexamples. we demonstrate the effectiveness of ourprototype implementation on several large industry designs.
width minimization of two-dimensional cmos cells using integer programming. we address the problem of cmos cell width minimization in the general two-dimensional (2-d) layout style and propose a novel technique based on integer linear programming (ilp) to solve it exactly. we formulate a 0-1 ilp model whose solution minimizes cell width along with the routing complexity across the diffusion rows. we present experimental results that evaluate the performance of two ilp solvers that have very different solution methods, and assess the effect of the number of rows on cell width. run-times for optimal layouts are in seconds for cells with up to 20 transistors. for larger cells, we propose a practical circuit pre-processing scheme that dramatically reduces the run time with little or no loss in optimality.
formal methods for dynamic power management. dynamic power management or dpm refers to the problem ofjudicious application of various low power techniques based onruntime conditions in an embedded system to minimize the totalenergy consumption.to be effective, often such decisions takeinto account the operating conditions and the system-level designgoals.dpm has been a subject of intense research in thepast decade driven by the need for low power in modern embeddeddevices.we present an overview of the formal methods thathave been explored in solving the system-level dpm problem.we show how formal reasoning frameworks can potentially unifyapparently disparate dpm techniques.
manufacturing-aware physical design. ultra-deep submicron manufacturability impacts physicaldesign (pd) through complex layout rules and large guardbands for process variability; this creates new requirements for new manufacturing-aware pd technologies. the firstpart of this tutorial reviews pd complications and methodology changes - notably in the detailed routing arena - that arise from subwavelength lithography and deep-submicronmanufacturing (antennas, metal planarization and mask-wafer mismatch). process variations and their sources are taxonomized for modeling and simulation. a framework ofdesign for cost and value is described. the second part covers yield-constrained optimizations in pd, especially "beyond corners" approaches that escape today's pessimistic or even incorrect corner-based approaches. statistical timingand noise analyses enable optimization of parametric yieldand reliability. yield-aware cell libraries and "analog" design rules (as opposed to "digital", 0/1 rules) can help designers explore yield-cost tradeoffs, especially for low-volumeparts. we then examine performance impact-limited fill insertion which goes beyond mere capacitance rules. modeling, objectives, and filling strategies are discussed. finally,we discuss current and near-term prospects for the overall design-to-manufacturing pd methodology. key aspects include better integrations with analysis and manufacturing interfaces, as well as cost-benefit tradeoffs for "regular"layout structures that are likely beyond 90nm, cost optimizations for low-volume production, and the role of robust and/or stochastic optimization in pd.
layout-aware scan chain synthesis for improved path delay fault coverage. path delay fault testing becomes increasingly important due tohigher clock rates and higher process variability caused by shrinkinggeometries. achieving high-coverage path delay fault testingrequires the application of scan justified test vector pairs, coupledwith careful ordering of the scan flip-flops and/or insertion ofdummy flip-flops in the scan chain. previous works on scan synthesisfor path delay fault testing using scan shifting have focusedexclusively on maximizing fault coverage and/or minimizing thenumber of dummy flip-flops, but have disregarded the scan wirelengthoverhead. in this paper we consider both dummy flip-flopand wirelength costs, and focus on post-layout formulations thatcapture the achievable tradeoffs between these costs and delay faultcoverage in scan chain synthesis.
towards formal verification of analog designs. we show how model checking methods developed for hybrid dynamic systems may be usefully applied for analog circuit verification. finite-state abstractions of the continuous analog behavior are automatically constructed using polyhedral outer approximations to the flows of the underlying continuous differential and difference equations. in contrast to previous approaches, we do not discretize the entire continuous state space, and our abstraction captures the relevant behaviors for verification in terms of the transitions between "states" (regions of the continuous state space) as a finite state machine in the hybrid system model. the approach is illustrated for two circuits, a standard oscillator benchmark, and a much larger and more realistic delta-sigma (ai) modulator.
constrained multivariable optimization of transmission lines with general topologies. the design of system level interconnects to meet signal integrity objectives is a challenging problem. this paper formulates the transmission line synthesis problem as a constrained multi-dimensional optimization of the complete net, taking into account factors like loading conditions on the line, loss in the line and rise-time of the input signal. different design variables such as width or resistivity of the interconnect, resistive source or far-end termination, etc. can all be considered concurrently. the termination metric is based upon forcing the impulse response waveform to be symmetric using the first three exact moments of the distributed system. an efficient means to trade-off between signal rise-time and ringing is presented and no time-domain simulations are needed. several examples are presented to demonstrate the efficacy of the proposed methodology.
test pattern generation based on arithmetic operations. existing built-in self test (bist) strategies require the use of specialized test pattern generation hardware which introduces significant area overhead and performance degradation. in this paper, we propose a novel method for implementing test pattern generators based on adders widely available in data-path architectures and digital signal processing circuits. test patterns are generated by continuously accumulating a constant value and their quality is evaluated in terms of the pseudo-exhaustive state coverage on subspaces of contiguous bits. this new test generation scheme, along with the recently introduced accumulator-based compaction scheme facilitates a bist strategy for high performance datapath architectures that uses the functionality of existing hardware, is entirely integrated with the circuit under test, and results in at-speed testing with no performance degradation and area overhead.
acyclic modeling of combinational loops. this paper presents a method to convert gate-level combinational loop into an acyclic circuit, if the combinational loop is not oscillatory. combinational loops breach design methodologies, because they can involve undesirable circuit behavior and can possibly lead to oscillations based on the external stimuli to the loops. however, for designs compiled using automated synthesis-compiler, these loops are very likely to appear in the generated gate-level designs. we present a modeling of combinational loops as state holding elements and break non oscillatory loops using a level sensitive latch. apart from modeling combinational loops consisting of gates, the algorithm also converts the loops through design latches. the increase in design area, due to the loop conversion, has an upper bound of twice the size of the original feedback path. however, in case of multiply nested feedback paths, each path is treated separately. unlike previous work that converts cyclic combinational logic where the feedback is not exercised, this paper presents an algorithm to identify the stateful "latch" behavior in a class of feedback logic (non-oscillatory, monotonic). a conversion algorithm replaces such feedback logic by an equivalent circuit comprising explicit latches and acyclic combinational logic. the replacement circuit has an identical behavior as the original stateful feedback logic.
partition-based decision heuristics for image computation using sat and bdds. methods based on boolean satisfiability (sat) typically use a conjunctive normal form (cnf) representation of the boolean formula, and exploit the structure of the given problem through use of various decision heuristics and implication methods. in this paper, we propose a new decision heuristic based on separator-set induced partitioning of the underlying cnf graph. it targets those variables whose choice generates clause partitions with disjoint variable supports. this can potentially improve performance of sat applications by decomposing the problem dynamically within the search. in the context of a recently proposed image computation method combining sat and bdds, this results in simpler bdd subproblems. we provide algorithms for cnf partitioning -- one based on a clause-variable dependency matrix, and another based on standard hypergraph partitioning techniques, and also for the use of partitioning information in decision heuristics for sat. we demonstrate the effectiveness of our proposed partition-based heuristic with practical results for reachability analysis of benchmark sequential circuits.
a high-level interconnect power model for design space exploration. in this paper, we present a high-level power model toestimate the power consumption in semi-global and global interconnects.such interconnects are used for communications between logic modules,clock distribution networks, and power supply rails. the main purposeof our model is to set forward a simple methodology to efficiently obtainfirst-order estimates of interconnect power in early stages of the designprocess. hence, the objective is to provide designers and/or high-leveldesign automation tools with a way to quickly explore the design spaceand weed out architectures whose interconnect power requirements donot meet the allocated power budget. in addition to switching power,which includes inter-wire coupling, our model also considers power dueto vias and repeaters. our experimental results show that in comparisonto an accurate low-level model, the error in our method in estimatingtotal switching power is only 6% (while the speedup is three-to-fourorders of magnitude), and an estimate of the numbers of vias (hence, viapower) is within 3% agreement of that obtained for designs synthesizedby commercial tools. furthermore, we develop a probabilistic segmentlength distribution model for cases in which rent's rule is inadequate. byanalyzing the netlists of a set of complex designs, we have been able tovalidate our segment length distribution model. the novelty of this worklies in the introduction of a high-level interconnect modeling methodologyin which it is possible to efficiently compute all the major sources ofpower consumption in interconnects and hence, enable interconnect-aware,high-level design space exploration.
gate sizing using incremental parameterized statistical timing analysis. as technology scales into the sub-90 nm domain, manufacturing variations become an increasingly significant portion of circuit delay. as a result, delays must be modeled as statistical distributions during both analysis and optimization. this paper uses incremental, parametric statistical static timing analysis (ssta) to perform gate sizing with a required yield target. both correlated and uncorrelated process parameters are considered by using a first-order linear delay model with fitted process sensitivities. the fitted sensitivities are verified to be accurate with circuit simulations. statistical information in the form of criticality probabilities are used to actively guide the optimization process which reduces run-time and improves area and performance. the gate sizing results show a significant improvement in worst slack at 99.86% yield over deterministic optimization.
re-encoding sequential circuits to reduce power dissipation. we present a fully implicit encoding algorithm for minimization of average power dissipation in sequential circuits, based on the reduction of the average number of bit changes per state transition.we have studied two novel schemes for this purpose, one based on recursive weighted non-bipartite matching, and one on recursive minicut bi-partitioning. we employ adds (algebraic decision diagrams) to computate the transition probabilities, to measure the potential area saving, and in the encoding algorithms themselves.our experiments show the effectiveness of our method in reducing power dissipation for large sequential designs.
a symbolic algorithm for maximum flow in 0-1 networks. we present an algorithm for finding the maximum flow in a 0-1 network. the algorithm is symbolic and does not require explicit enumeration of the nodes and edges of the network. therefore, it can handle much larger graphs than it was previously possible (more than 10^36 edges). the main idea is to trace (implicitly) sets of edge-disjoint augmenting paths. disjointness is enforced by solving an edge matching problem for each layer of the network with the help of newly defined priority functions.
a new approach to effective circuit clustering. it is pointed out that the complexity of next-generation vlsi systems will exceed the capabilities of top-down layout synthesis algorithms, particularly in netlist partitioning and module placement. bottom-up clustering is needed to condense the netlist so that the problem size becomes tractable to existing optimization methods. here, the ds quality measure, a general metric for evaluation of clustering algorithms, is established. the dc metric in turn motivates the rw-st algorithm, a self-tuning clustering method based on random walks in the circuit netlist. rw-st efficiently captures a globally good circuit clustering. when incorporated within a two-phase iterative fiduccia-mattheyses partitioning strategy, the rw-st clustering method improves bisection width by an average of 17% over previous matching-based methods
a system for synthesizing optimized fpga hardware from matlab. efficient high level design tools that can map behavioral descriptions to fpga architectures are one of the key requirements to fully leverage fpga for high throughput computations and meet time-to-market pressures. we present a compiler that takes as input algorithms described in matlab and generates rtl vhdl. the rtl vhdl then can be mapped to fpgas using existing commercial tools. the input application is mapped to multiple fpgas by parallelizing the application and embedding communication and synchronization primitives automatically. our compiler infers the minimum number of bits required to represent the variable through a precision analysis framework. the compiler can leverage optimized ip cores to enhance the hardware generated. the compiler also exploits parallelism in the input algorithm by pipelining in the presence of resource constraints. we demonstrate the utility of the compiler by synthesizing hardware for a couple of signal/image processing algorithms and comparing them with manually designed hardware.
efficient construction of binary moment diagrams for verifying arithmetic circuits. bdd-based approaches cannot handle some arithmetic functions such as multiplication efficiently, while binary moment diagrams proposed by bryant and chen provide compact representations for those functions. they reported a bmd-based polynomial-time algorithm for verifying multipliers. this approach requires high-level information such as specifications to subcomponents. this paper presents a new technique called backward construction which can construct bmds directly from circuit descriptions without any high-level information. the experiments show that the computation time for verifying for n-bit multipliers is approximately n^4. we have successfully verified 64-bit multipliers of several type in 3-6 hours with 40 mbyte of memory on sparcstation10/51. this result outperforms previous bdd-based approaches for verifying multipliers.
deterministic test pattern generation techniques for sequential circuits. this paper presents new test generation techniques for improving the average-case performance of the iterative logic array based deterministic sequential circuit test generation algorithms. to be able to assess the effectiveness of the proposed techniques, we have developed a new atpg system for sequential circuits, called atoms, and we have incorporated these techniques into the test generator. atoms achieved very high fault coverages in a short amount of time for the iscas89 sequential benchmark circuits, demonstrating the effectiveness of these techniques on the test generation performance.
wirelength optimization by optimal block orientation. rectangular cells can be flipped in place along either horizontal or vertical axis without changing the area of a layout. during floorplanning, both the location and orientation of cells are determined. however, the complexity of the floorplanning process usually means that the wirelength is not minimum. this paper proposes a technique for wirelength minimization based on in-place flipping of cells that can be applied to any floorplan style consisting of rectangular blocks or sub-blocks. instead of conventional search procedures, a boolean symbolic approach is proposed to generate flip-optimal floorplans. experimental results show that it can effectively reduce the wirelength of current state of the art approaches, at no cost in area and with modest runtimes.