waashk/dblp huggingface dataset:
first steps towards sat-based formal analog verification. boolean satisfiability (sat) based methods have traditionally been popular for formally verifying properties for digital circuits. we present a novel methodology for formulating a spice-type circuit simulation problem as a satisfiability problem. we start with a circuit level netlist, capture the non-linear behavior of the circuits at the transistor level via conservative approximations and transform the simulation problem into a search problem that can be exhaustively explored via a sat solver. thus, for dc as well as fixed time-step based transient and periodic steady state (pss) simulation formulations, the solutions produced by the solver are formal in nature. we also present algorithms for abstraction refinement and smart interval generation to improve the computational efficiency of our proposed solution scheme. we have implemented our ideas into a tool called fspice which is the first attempt at building a formal spice engine. we demonstrate the applicability of our ideas by showing experimental results using pruned versions of real designs that faced challenges during chip tape-out.
thermal modeling for 3d-ics with integrated microchannel cooling. integrated microchannel liquid-cooling technology is envisioned as a viable solution to alleviate an increasing thermal stress imposed by 3d stacked ics. thermal modeling for microchannel cooling is challenging due to its complicated thermal-wake effect, a localized temperature wake phenomenon downstream of a heated source in the flow. this paper presents a fast and accurate thermal-wake aware thermal model for integrated microchannel 3d ics. validation results show the proposed thermal model achieves more than 400x speed up and only 2.0% error in comparison with a commercial numerical simulation tool. we also demonstrate the use of the proposed thermal model for thermal optimization during the ic placement stage. we find that due to the thermal-wake effect, tiles are placed in the descending order of power magnitude along the flow direction. we also find that modeling thermal-wakes is critical for generating a thermal-aware placement for integrated microchannel-cooled 3d ic. it could result in up to 25&deg;c peak temperature difference according to our experiments.
a framework for early and systematic evaluation of design rules. design rules have been the primary contract between technology and design and are likely to remain so to preserve abstractions and productivity. while current approaches for defining design rules are largely unsystematic and empirical in nature, this paper offers a novel framework for early and systematic evaluation of design rules and layout styles in terms of major layout characteristics of area, manufacturability, and variability. due to the focus on co-exploration in early stages of technology development, we use first order models of variability and manufacturability (instead of relying on accurate simulation) and layout topology/congestion-based area estimates (instead of explicit and slow layout generation). the framework is used to efficiently co-evaluate several debatable rules (evaluation for a 104-cell library takes 20 minutes). results show that: a) diffusion-rounding mainly from diffusion power-straps is a dominant source of variability, b) cell-area overhead of fixed gate-pitch implementation compared to 1d-poly implementation is tolerable (5%) given the improvement in variability, and c) 1d-poly restriction, which improves manufacturability and variability, has almost no area overhead compared to 2d-poly. in addition, we explore gate-spacing rules using our evaluation framework. this exploration yields almost identical values as those of a commercial 65nm process, which serves as a validation for our approach.
ipr: in-place reconfiguration for fpga fault tolerance. we describe in-place reconfiguration (ipr) for lut-based fpgas, an algorithm that maximizes identical configuration bits for complementary inputs of a lut thereby reducing the propagation of faults seen at a pair of complementary inputs. based on ipr, we develop a fault-tolerant logic resynthesis algorithm which decreases the circuit fault rate while preserving functionality and topology of the lut-based logic network. since the topology is preserved, the resynthesis algorithm can be applied post-layout and without changes in physical design. compared to the state-of-the-art academic technology mapper berkeley abc, ipr reduces the relative fault rate by 48% and increases mttf by 1.94x with the same area and performance, and ipr combined with a previous fault-tolerant logic resynthesis algorithm (rose) reduces the relative fault rate by 49% and increases mttf by 2.40x with 19% less area but same performance. the above improvement assumes a stochastic single fault and more improvement is expected for multi-fault models.
how to consider shorts and guarantee yield rate improvement for redundant wire insertion. this paper accurately considers wire short defects and proposes an algorithm to guarantee ic chip yield rate improvement for redundant wire insertion. without considering yield rate degradation caused by shorts, traditional methods may even lead to yield rate loss. however, shorts are more complicated to analyze than opens. moreover, since any two points of a routed net can be connected by a redundant wire, the number of possible insertion patterns for a chip is un-tractable. to maximize yield rate improvement and to make the problem tractable, we identify a key insight, tolerance-ratio, as an effective guide for choosing insertion patterns and insertion order. finally, to guarantee yield rate improvement, only positive gain redundant wires are committed. experimental results show that, compared with unprocessed cases, all yield rate improvements in the proposed algorithm are positive, and the defect rates are reduced by up to 65% and by 24% on average. on the other hand, without considering shorts, the defect rate can increase as much as 7%.
voltage binning under process variation. process variation is recognized as a major source of parametric yield loss, which occurs because a fraction of manufactured chips do not satisfy timing or power constraints. on the other hand, both chip performance and chip leakage power depend on supply voltage. this dependence can be used for converting the fraction of too slow or too leaky chips into good ones by adjusting their supply voltage. this technique is called voltage binning [4]. all the manufactured chips are divided into groups (bins) and each group is assigned its individual supply voltage. this paper proposes a statistical technique of yield computation for different voltage binning schemes using results of statistical timing and variational power analysis. the paper formulates and solves the problem of computing optimal supply voltages for a given binning scheme.
an efficient pre-assignment routing algorithm for flip-chip designs. the flip-chip package is introduced for modern ic designs with higher integration density and larger i/o counts. in this paper, we consider the pre-assignment flip-chip routing problem with predefined connections between driver pads and bump pads. this problem has been shown to be much more difficult than the free-assignment one, but is more popular in real-world designs because the connections between driver pads and bump pads are typically pre-determined by ic or packaging designers. based on the concept of routing sequence exchange, we propose a very efficient global routing algorithm by computing the weighted longest common subsequence (wlcs) and the maximum planar subset of chords (mpsc) for pre-assignment flip-chips. we observe that the existing work over constrains the capacity of a routing tile, which might miss some critical solution space with a better routing solution (e.g., smaller wirelength), and provide a remedy for this insufficiency to identify a better solution in a more complete solution space. we also develop a constant-time routability analyzer to check if a given set of wires can pass through a tile. experimental results show that our router can achieve a 122x speedup with even better solution quality (same routability with slightly smaller wire-length), compared with a state-of-the-art flip-chip router based on integer linear programming (ilp).
intrinsic nbti-variability aware statistical pipeline performance assessment and tuning. random process variation and variability intrinsic to pmos negative bias temperature instability (nbti-induced statistical variation) are two major reliability concerns as transistor dimensions scales with technology. previous works have studied these two sources of variation separately at device and circuit level. we study the impact of the interaction between intrinsic pmos nbti variability and time0 process variability on circuit delay spread. a statistical pipeline timing error model is proposed including both the variability sources to predict its impact on pipeline stage count. it is shown that a wide difference in statistical timing response to intrinsic nbti variability exists among different circuits. traditional design time nbti-aware delay guard-banding is proved to be statistically insufficient in pipelines and an excess of 2x guard-band needs to be incorporated at the end of 10 years. however, the guard-band is shown to be reduced by 30% when the dynamic cycle time stealing technique is employed.
an efficient algorithm for modeling spatially-correlated process variation in statistical full-chip leakage analysis. statistical full-chip leakage analysis considering spatial correlation is highly expensive due to its o(n2) complexity for logic circuits with n gates. although efforts have been made to reduce the cost at the loss of accuracy, existing methods are still unsuitable for large-scale problems. in this paper we resolve the problem by re-formulating the computation to one that can be done efficiently using a well-developed technique that has been widely used in fast em simulation and machine learning areas. the resulting algorithm is provably of o(n) or o(n log n) complexity with well-defined and easily-controlled error bounds. experiments show that using the proposed method it is feasible to handle milliongate circuits within only a few minutes on a regular desktop pc. the corresponding error is less than 0.5% compared to exhausted computation that takes more than 3 days. the proposed method is about 300x faster and 10x more accurate compared to existing grid-approximation method.
psta-based branch and bound approach to the silicon speedpath isolation problem. the lack of good "correlation" between pre-silicon simulated delays and measured delays on silicon (silicon data) has spurred efforts on so-called silicon debug. the identification of speed-limiting paths, or simply speedpaths, in silicon debug is a crucial step, required for both "fixing" failing paths and for accurate learning from silicon data. we propose using characterized, pre-silicon, variational timing models to identify speedpaths that can best explain the observed delays from silicon measurements. delays of all logic paths are written as affine functions of process parameters, called hyperplanes, and a branch and bound approach is then applied to find the "best" path combinations. our method has been tested on a set of iscas-89 circuits and the results show that it accurately identifies the speedpaths in most cases, and that this is achieved in a very efficient manner.
genetic design automation. electronic design automation (eda) tools have facilitated the design of ever more complex integrated circuits each year. synthetic biology would also benefit from the development of genetic design automation (gda) tools. existing gda tools require biologists to design genetic circuits at the molecular level, roughly equivalent to designing electronic circuits at the layout level. analysis of these circuits is also performed at this very low level. this paper presents the background and issues involved in the development of such a gda tool for modeling, analysis, and design.
adaptive power management using reinforcement learning. system level power management must consider the uncertainty and variability that comes from the environment, the application and the hardware. a robust power management technique must be able to learn the optimal decision from past history and improve itself as the environment changes. this paper presents a novel online power management technique based on model-free constrained reinforcement learning (rl). it learns the best power management policy that gives the minimum power consumption for a given performance constraint without any prior information of workload. compared with existing machine learning based power management techniques, the rl based learning is capable of exploring the trade-off in the power-performance design space and converging to a better power management policy. experimental results show that the proposed rl based power management achieves 24% and 3% reduction in power and latency respectively comparing to the existing expert based power management.
an accurate and efficient performance analysis approach based on queuing model for network on chip. an accurate and highly-efficient performance analysis approach is extremely important for the early-stage designs of network-on-chip. in this paper, the novel m/g/i/n queuing models for generic routers are proposed to analyze various packet blockings and then the performance analysis algorithm is presented to estimate some key metrics in terms of packet latency, buffer utilization, etc. for single-channel and multi-channel routers, the comparisons between analysis and observed results validate that the proposed approach with mean errors of 6.9% and 7.8% achieve the speed-ups of 240 and 210 times respectively. in our design methodology, this approach can not only effectively direct noc synthesis process but also be conveniently applied to multi-objective optimizations to find the best mapping solutions.
enhanced reliability-aware power management through shared recovery technique. while dynamic voltage scaling (dvs) remains as a popular energy management technique for real-time embedded applications, recent research has identified significant and negative impact of voltage scaling on system reliability. for this reason, a number of reliability-aware power management (ra-pm) schemes were recently proposed to preserve the system reliability when dvs is used. in this paper, we propose a new approach, called the shared recovery (shr) technique, to minimize the system-level energy consumption while still preserving the system's original reliability. the main idea of the shr technique is to avoid the offline allocation of separate recovery tasks to the scaled tasks by assigning a global/shared recovery block that can be used by any task at run-time. our simulation results show that, compared to the existing ra-pm schemes, our scheme can achieve up to 35% energy savings. further, this performance is shown to be comparable to the maximum energy savings that can be achieved by any algorithm. interestingly, our extensive evaluation indicates that shr offers also non-trivial gains over the previous algorithms on the reliability side. further, a dynamic extension is proposed to improve energy and reliability management at run-time by reducing the size of the recovery block and re-using the slack that arises from early completions.
multi-level clustering for clock skew optimization. clock skew scheduling has been effectively used to reduce the clock period of sequential circuits. however, this technique may become impractical if a different skew must be applied for each memory element. this paper presents a new technique for clock skew scheduling constrained by the number of skew domains. the technique is based on a multi-level clustering approach that progressively groups flip-flops with skew affinity. this new technique has been compared with previous work, showing the efficiency in the obtained performance and computational cost. as an example, the skews for an opensparc with almost 16k flip-flops and 500k paths have been calculated in less than 5 minutes when using only 2 to 5 skew domains.
qlmor: a new projection-based approach for nonlinear model order reduction. we present a new projection-based nonlinear model order reduction method, named qlmor (mor via quadratic-linear systems). qlmor employs two novel ideas: (1) we show that daes (differential-algebraic equations) with many commonly-encountered nonlinear kernels can be re-written equivalently into a special format, qldaes (quadratic-linear differential algebraic equations, i.e., daes that are quadratic in their state variables and linear in their inputs); (2) we adapt the moment-matching reduction technique of norm[1] to reduce these qldaes into qldaes of much smaller size. because of the generality of the qldae form, qlmor has significantly broader applicability than taylor-expansion based methods [2, 3, 1]. importantly, qlmor, unlike norm, totally avoids explicit moment calculations (aib terms), hence it has improved numerical stability properties as well. because the reduced model has only quadratic nonlinearities (i.e., no cubic and higher-order terms), its computational complexity is less than that of similar prior methods[2, 3, 1]. we also prove that qlmor-reduced models preserve local passivity, and provide an upper bound on the size of the qldaes derived from a polynomial system. we compare qlmor against prior methods [2, 3, 1] on a circuit and a biochemical reaction-like system, and demonstrate that qlmor-reduced models retain accuracy over a significantly wider range of excitation than taylor-expansion based methods [2, 3, 1]. indeed, qlmor is able to reduce systems that taylor-expansion based methods fail to reduce due to passivity loss and impractically high computational costs. qlmor therefore demonstrates that volterra-kernel based nonlinear mor techniques can in fact have far broader applicability than previously suspected, possibly being competitive with trajectory-based methods (e.g., tpwl [4]) and nonlinear-projection based methods (e.g., manimor [5]).
energy reduction for stt-ram using early write termination. the emerging spin torque transfer memory (stt-ram) is a promising candidate for future on-chip caches due to stt-ram's high density, low leakage, long endurance and high access speed. however, one of the major challenges of stt-ram is its high write current, which is disadvantageous when used as an on-chip cache since the dynamic power generated is too high. in this paper, we propose early write termination (ewt), a novel technique to significantly reduce write energy with no performance penalty. ewt can be implemented with low complexity and low energy overhead. our evaluation shows that up to 80% of write energy reduction can be achieved through ewt, resulting 33% less total energy consumption, and 34% reduction in ed2. these results indicate that ewt is an effective and practical scheme to improve the energy efficiency of a stt-ram cache.
scan power reduction in linear test data compression scheme. xor network-based on-chip test compression schemes have been widely employed in large industrial scan designs due to their high compression ratio and efficient decompression mechanism. nevertheless, such a scheme necessitates high unspecified bit ratios in the original test cubes, resulting in quite significant difficulties in preprocessing test cubes for scan power reduction. the linear mapping from the original cubes to the compressed seeds typically provides extra degrees of flexibility as multiple seeds may reconstruct the test cube. appreciable power reductions in the decompressed test data can be attained through the pinpointing of the power-optimal seeds during the compression phase. the proposed work explores the aforementioned flexibility in the seed space, and proposes the mathematical and algorithmic framework for a power-aware linear test compression scheme. the proposed technique incurs no hardware overhead over the traditional linear compression scheme; it can be easily embedded furthermore into the industrial test compaction/compression flow. experimental results confirm that the proposed technique delivers significant scan power reduction with negligible impact on the compression ratio.
voltage-drop aware analytical placement by global power spreading for mixed-size circuit designs. excessive supply voltage drops in a circuit may lead to significant circuit performance degradation and even malfunction. to handle this problem, existing power delivery aware placement algorithms model voltage drops as an optimization objective. we observe that directly minimizing voltage drops in an objective function might not resolve voltage-drop violations and might even cause problems in power-integrity convergence. to remedy this deficiency, in this paper, we propose new techniques to incorporate device power spreading forces into a mixed-size analytical placement framework. unlike the state-of-the-art previous work that handles the worst voltage-drop spots one by one, our approach simultaneously and globally spreads all the blocks with voltage-drop violations to desired locations directly to minimize the violations. to apply the power force, we model macro current density and power rails for our placement framework to derive desired macro/cell locations. to further improve the solution quality, we propose an efficient mathematical transformation to adjust the power force direction and magnitude. experimental results show that our approach can substantially improve the voltage drops, wirelength, and runtime over the previous work.
grplacer: improving routability and wire-length of global routing with circuit replacement. placement profoundly impacts physical design owing to its role in determining the lower bound of a circuit wirelength, as well as the circuit routability. to close the gap between placement and routing, this study integrates global routing and placement to improve the wirelength estimation accuracy of placement. two methods, called wirelength-reduced cell shifting and cell rearrangement by bipartite matching, are applied to minimize wirelength. cell sorting based congestion reduction and pattern-prerouting based congestion-avoided cell shifting are proposed to reduce congestion. experimental results demonstrate that the proposed placer improves total routed wirelength by 2% to rooster on ibmv2 benchmarks. moreover, the proposed grplacer resolves the original congested regions of the placements generated by rooster. compare with the detailed placer in rooster, our work can reduce more routed wire length and remove more overflows.
an efficient wakeup scheduling considering resource constraint for sensor-based power gating designs. power gating has been a very effective way to reduce leakage power. one important design issue for a power gating design is to limit the surge current during the wakeup process. normally, a wakeup scheduling is required to control turn-on times of sleep transistors. in this paper, we adopt a voltage sensor to compare pre-designed reference voltages with the virtual ground voltage and use the comparison result to determine turn-on times of sleep transistors. special properties and optimizations of using voltage sensors are discussed. since a wakeup scheduling with fast wakeup time may require significant hardware resources, we propose a new wakeup scheduling formulation which considers the trade-off between wakeup times and hardware resources. our experimental results show that with small increases on wakeup times, we can reduce significant hardware resources for a power gating design.