waashk/dblp huggingface dataset:
bioroute: a network-flow based routing algorithm for digital microfluidic biochips. due to the recent advances in microfluidics, digital microfluidic biochips are expected to revolutionize laboratory procedures. one critical problem for biochip synthesis is the droplet routing problem. unlike traditional vlsi routing problems, in addition to routing path selection, the biochip routing problem needs to address the issue of scheduling droplets under the practical constraints imposed by the fluidic property and the timing restriction of the synthesis result. in this paper, we present the first network-flow based routing algorithm that can concurrently route a set of non-interfering nets for the droplet routing problem on biochips. we adopt a two-stage technique of global routing followed by detailed routing. in global routing, we first identify a set of non-interfering nets and then adopt the network-flow approach to generate optimal global-routing paths for the nets. in detailed routing, we present the first polynomial-time algorithm for simultaneous routing and scheduling using the global-routing paths with a negotiation-based routing scheme. the experimental results show the robustness and efficiency of our algorithm.
performance estimation and slack matching for pipelined asynchronous architectures with choice. this paper presents a fast analytical method for estimating the throughput of pipelined asynchronous systems, and then applies that method to develop a fast solution to the problem of pipelining "slack matching." the approach targets systems with hierarchical topologies, which typically result when high-level (block structured) language specifications are compiled into data-driven circuit implementations. a significant contribution is that our approach is the first to efficiently handle architectures with choice (i.e., the presence of conditional computation constructs such if-then-else and conditional loops). the key idea behind the fast speed of our analysis method is to exploit information about the hierarchy of a given block-structured system, thereby yielding a runtime that is linear in the number of pipeline stages. in contrast, existing approaches typically represent an entire system as a single petri net or marked graph, and then apply markov chain analysis or other state enumeration methods with costly runtimes. building upon our analysis approach, we introduce a novel solution to the problem of slack matching, i.e., determining optimal insertion of fifo stages into a pipelined design to improve performance. we present both an optimal solution using an milp formulation, and a fast heuristic algorithm that yielded optimal results for all of our examples.
the effect of process variation on device temperature in finfet circuits. with technology scaling, devices are increasingly prone to process variations. these variations cause a large spread in leakage power, since it is extremely sensitive to process variations, which in turn results in larger temperature variations across different dies. in this paper, we investigate the temperature variations in finfet circuits considering variations in following parameters (i) channel length and (ii) body thickness. we estimate temperature variation under process fluctuation by monte carlo simulation with thermal models to solve temperature and leakage power self-consistently. the results show that high activity circuits exhibit larger temperature variations since increased temperature increments leakage power and vice versa. it is also shown that under moderate process variation (3&sigma;=10% for channel length and body thickness) and a nominal primary input activity of 0.4, thermal runaway can occur in more than 15% of chips in 28nm finfet technology, severely degrading manufacturing yield.
compact modeling of variational waveforms. in ultra-deep sub-micron technologies, modeling waveform shapes correctly is essential for accurate timing and noise analysis. due to process and environmental variations, there is a need for a variational waveform model that is compact, efficient and accurate. the model should capture correlations due to common dependence on process parameters. this paper proposes a waveform model derived from basic transformations of a nominal waveform in the absence of variations. the transformations are parameterized by variational quantities that capture the sensitivity of the waveform to process parameters. the resulting waveform model works well with current-source models for static timing analysis. numerical results are presented to demonstrate the accuracy of the model both in capturing variational waveforms and in propagating waveforms through logic gates.
guaranteed stable projection-based model reduction for indefinite and unstable linear systems. in this work we present a stability-preserving projection framework for model reduction of linear systems. specifically, given one projection matrix (e.g. a right-projection matrix), we derive a set of linear constraints for the other projection matrix (e.g. the left-projection matrix) resulting in a projection framework that is guaranteed to generate a stable reduced model. several efficient techniques for solving the proposed system of constraints are presented, including an optimization problem formulation for finding the optimal stabilizing projection, and a formulation with computational complexity independent of the size of the original system. the resulting algorithms can create accurate stable and passive models of arbitrary indefinite systems at a significantly cheaper cost than existing methods such as balanced truncation. nevertheless, our algorithms integrate fully and effortlessly with most of the available standard model order reduction approaches for very large systems generated in vlsi applications (such as moment-matching methods, pod, or poor man's tbr), which can guarantee stability and passivity only in very specialized cases. our algorithms have been tested on a large variety of typical vlsi applications, including field-solver-extracted models of rf inductors for analog applications, power distribution grids for large vlsi digital integrated circuits, and mems devices for sensing and actuation applications. the results have been successfully compared to those from existing and much more expensive stabilizing reduction techniques.
a performance-driven qbf-based iterative logic array representation with applications to verification, debug and test. many cad for vlsi techniques use time-frame expansion, also known as the iterative logic array representation, to model the sequential behavior of a system. replicating industrial-size designs for many time-frames may impose impractically excessive memory requirements. this work proposes a performance-driven, succinct and parametrizable quantified boolean formula (qbf) satisfiability encoding and its hardware implementation for modeling sequential circuit behavior. this encoding is then applied to three notable cad problems, namely bounded model checking (bmc), sequential test generation and design debugging. extensive experiments on industrial circuits confirm outstanding run-time and memory gains compared to state-of-the-art techniques, promoting the use of qbf in cad for vlsi.
incremental learning approach and sat model for boolean matching with don't cares. in this paper, we will propose an incremental learning approach to solve boolean matching for incompletely specified functions. this approach can incrementally analyze current feasible partial mappings, detect and eliminate redundant manipulations in a proactive way. a new type of signature exploiting single variable symmetries is also given to reduce the searching space. moreover, a sat model of boolean matching will be proposed to handle large boolean functions. through the utilization of these novel mechanisms, a drastic improvement on the performance of our boolean matching algorithms are achieved. the experimental results demonstrate the effectiveness and efficiency of the proposed learning-based and sat-based boolean matching algorithms on many large benchmarking circuits.
accurate detection for process-hotspots with vias and incomplete specification. this paper introduces the concept of via range patterns and incompletely specified range patterns to represent new types of process-hotspots. via range patterns can represent process-hotspots containing vias that are a major source of lithography issues. an incompletely specified range pattern can accurately and succinctly represent a process-hotspot where any configuration of objects (that is unknown to the user apriori) can exist in some of its peripheral regions. these new types of range patterns cannot be accurately represented and/or detected using the concept of range patterns introduced in [7]. a new detection algorithm that can accurately detect these new types of patterns is also proposed. this is necessitated since the range pattern matching algorithm proposed earlier causes mismatches: it either misses true matches or reports false matches for these new kinds of patterns. theoretical results show that the proposed algorithm prevents the incorrect mis-match issues, while experimental results on fab provided process-hotspots show the algorithm is computationally efficient and practical for use on real industrial designs.
accurate energy breakeven time estimation for run-time power gating. run-time power gating (rtpg) is a recent technique, which aims at aggressively reducing leakage power consumption. energy breakeven time (ebt), or equivalent sleep time has been proposed as a critical figure of merit of rtpg. our research introduces the definition of average ebt in a run-time environment. we develop a method to estimate the average ebt for any given circuit block, considering the impact of circuit states. hspice simulation results on iscas85 benchmark circuits show that the average ebt model has on the average 1.8% error. the cad tool implemented based on the model can perform fast estimations with a speedup of 3000 x over hspice.
design methodology to trade off power, output quality and error resiliency: application to color interpolation filtering. power dissipation and tolerance to process variations pose conflicting design requirements. scaling of voltage is associated with larger variations, while vdd up-scaling or transistor up-sizing for process tolerance can be detrimental for power dissipation. however, for certain signal processing systems such as those used in color image processing, we noted that effective trade-offs can be achieved between vdd scaling, process tolerance and "output quality". in this paper we demonstrate how these tradeoffs can be effectively utilized in the development of novel low-power variation tolerant architectures for color interpolation. the proposed architecture supports a graceful degradation in the psnr (peak signal to noise ratio) under aggressive voltage scaling as well as extreme process variations in sub-70nm technologies. this is achieved by exploiting the fact that some computations are more important and contribute more to the psnr improvement compared to the others. the computations are mapped to the hardware in such a way that only the less important computations are affected by vdd-scaling and process variations. simulation results show that even at a scaled voltage of 60% of nominal vdd value, our design provides reasonable image psnr with 69% power savings.
selective shielding: a crosstalk-free bus encoding technique. with cmos process technology scaling to deep submicron level, propagation delay across long on-chip buses is becoming one of the main performance limiting factors in high-performance designs. propagation delay is very significant when adjacent wires are transitioning in opposite direction (i.e., crosstalk transitions) as compared to transitioning in the same direction. as crosstalk transitions have significant impact on propagation delay, several bus encoding techniques have been proposed in literature to eliminate such transitions. in this work, we propose a technique, namely, selective shielding, to eliminate crosstalk transitions. compared to the conventional shielding technique, our technique significantly reduces the number of extra wires. we give a lower bound on the number of wires required to encode n-bit data using the selective shielding technique. we show that our technique achieves better energy savings and requires less area as compared to the other techniques.
early planning for clock skew scheduling during register binding. design decisions made during high-level synthesis usually have great impacts on the later design stages. in this paper, we present a general framework, which plans for the clock skew scheduling in physical design stages during register binding in high-level synthesis. our proposed technique pursues the optimality of the native objective functions of the register binding problem. at the same time, it ensures not invalidating the subsequent clock skew scheduling for optimizing the clock period. we use the switching power as the native objective of our register binding problem. the problem is first formulated as a milp problem. an acceleration scheme based on the concept of weakly compatible edge set(wces) is proposed to speed up the milp solver to obtain the optimal solution. then, we present our heuristic algorithm to reduce the running time further. the experimental results show that on average our acceleration scheme can speed up the solver by 8.6 times, and our heuristic is 70 times faster than the solver with a 5.25% degradation of the native objective. the minimum and maximum degradation among our benchmark set are 0.82% and 12.2% respectively.
computation of minimal counterexamples by using black box techniques and symbolic methods. computing counterexamples is a crucial task for error diagnosis and debugging of sequential systems. if an implementation does not fulfill its specification, counterexamples are used to explain the error effect to the designer. in order to be understood by the designer, counterexamples should be simple, i.e. they should be as general as possible and assign values to a minimal number of input signals. here we use the concept of black boxes --- parts of the design with unknown behavior --- to mask out components for counterexample computation. by doing so, the resulting counterexample will argue about a reduced number of components in the system to facilitate the task of understanding and correcting the error. we introduce the notion of 'uniform counterexamples' to provide an exact formalization of simplified counterexamples arguing only about components which were not masked out. our computation of counterexamples is based on symbolic methods using aigs (and-inverter-graphs). experimental results using a vliw processor as a case study clearly demonstrate our capability of providing simplified counterexamples.
gate sizing by lagrangian relaxation revisited. in this paper, we formulate the generalized convex sizing (gcs) problem that unifies and generalizes the sizing problems. we revisit the approach to solve the sizing problem by lagrangian relaxation, point out several misunderstandings in the previous works, and extend the approach to handle general convex delay functions in the gcs problems. we identify a class of proper gcs problems whose objective functions in the simplified dual problem are differentiable and show many practical sizing problems, including the simultaneous sizing and clock skew optimization problem, are proper. we design an algorithm based on the method of feasible directions to solve proper gcs problems. the algorithm will provide evidences for infeasible gcs problems according to a condition derived by us. experimental results confirm the efficiency and the effectiveness of our algorithm when the elmore delay model is used.
thermalscope: multi-scale thermal analysis for nanometer-scale integrated circuits. thermal analysis has long been essential for designing reliable, high-performance, cost-effective integrated circuits (ics). increasing power densities are making this problem more important. characterizing the thermal profile of an ic quickly enough to allow feedback on the thermal effects of tentative design changes is a daunting problem, and its complexity is increasing. the move to nanoscale fabrication processes is increasing the importance of quantum thermal phenomena such as ballistic phonon transport. accurate thermal analysis of nanoscale ics containing hundreds of millions of devices requires characterization of thermal effects on length scales that vary by several orders of magnitude, from nanoscale quantum thermal effects to centimeter-scale cooling package impact. existing chip-package thermal analysis methods based on classical fourier heat transfer cannot capture nanoscale quantum thermal effects. however, accurate device-level modeling techniques, such as molecular dynamics methods, are far too slow for use in full-chip ic thermal analysis. in this work, we propose and develop thermalscope, a multi-scale thermal analysis method for nanoscale ic design. it unifies microscopic and macroscopic thermal physics modeling methods, i.e., the fourier and boltzmann transport modeling methods. moreover, it supports adaptive multi-resolution modeling. together, these ideas enable efficient and accurate characterization of nanoscale quantum heat transport as well as chip-package level heat flow. thermalscope is designed for full-chip thermal analysis of billion-transistor nanoscale ic designs, with accuracy at the scale of individual devices. thermalscope enables accurate characterization of temperature-related effects, such as variation in leakage power and delay. thermalscope has been implemented in software and used for full-chip thermal analysis and temperature-dependent leakage analysis of an ic design with more than 150 million transistors. it will be publicly released for free academic and personal use.
equalized interconnects for on-chip networks: modeling and optimization framework. this paper presents a modeling framework for fast design space exploration and optimization of equalized on-chip interconnects. the exploration is enabled by cross-layer modeling that connects the transistor and wire parameters to link performance, equalization coefficients, and architecture-friendly metrics (delay, energy-per-bit, and throughput density). appropriate models are derived to speed-up the search by more than two orders of magnitude and make a million point design space searchable in less than two hours on a standard machine. with this approach we are able to find the best link design for target throughput, power and area constraints, thus enabling the architectural optimization of energy-efficient on-chip networks. for the same latency and throughput density, equalized interconnects optimized using the new methodology have up to 10x better energy-efficiency than optimized repeater interconnects.
multi-layer global routing considering via and wire capacities. global routing for modern large-scale circuit designs has attracted much attention in the recent literature. most of the state-of-the-art academic global routers just work on a simplified routing congestion model that ignores the essential via capacity for routing through multiple metal layers. such a simplified model would easily cause fatal routability problems in subsequent detailed routing. to remedy this deficiency, we present in this paper a more effective congestion metric that considers both the in-tile nets and the residual via capacity for global routing. with this congestion metric, we develop a new global router that features two novel routing algorithms for congestion optimization, namely least-flexibility-first routing and multi-source multi-sink escaping-point routing. the least-flexibility-first routing processes the nets with the least flexibility first, facilitating a quick prediction of congestion hot spots for the subsequent nets. enjoying lower time complexity than traditional maze and a*-search routing, in particular, the linear-time escaping-point routing guarantees to find the optimal solution and achieves the theoretical lower-bound time complexity. experimental results show that our global router can achieve very high-quality routing solutions with more reasonable via usage, which can benefit and correctly guide subsequent detailed routing.
soft-edge flip-flops for improved timing yield: design and optimization. parameter variations cause high yield losses due to their large impact on circuit delay. in this paper, we propose the use of so-called soft-edge flip-flops as an effective way to mitigate these yield losses. soft-edge flip-flops have a small window of transparency (ranging from 0.25-3 fo4) instead of a hard edge, allowing limited cycle stealing on critical paths, and thus compensating for delay variations. by enabling time borrowing, soft-edge flip-flops allow random delay variations to average out across multiple logic stages. in addition, they address small amounts of delay imbalance between logic stages, further maximizing the frequency of operation. we develop a library of soft-edge flip-flops with varying amounts of softness. we show that the power and area overhead of soft-edge flip-flops grows directly with the amount of softness. we then propose a statistically aware flip-flop assignment algorithm that maximizes the gain in timing yield while minimizing the incurred power overhead. experimental results on a wide range of benchmark circuits show that the proposed approach improves the mean delay by 1.9--22.3% while simultaneously reducing the standard deviation of delay by 1.9--24.1% while increasing power by a small amount (0.3--2.8%).
monte-carlo driven stochastic optimization framework for handling fabrication variability. increasing effects of fabrication variability have inspired a growing interest in statistical techniques for design optimization. in this work, we propose a monte-carlo driven stochastic optimization framework that does not rely on the distribution of the varying parameters (unlike most other existing techniques). stochastic techniques like successive sample mean optimization (ssmo) and stochastic decomposition present a strong framework for solving linear programming formulations in which the parameters behave as random variables. we consider binning-yield loss (byl) as the optimization objective and show that we can get a provably optimal solution under a convex byl function. we apply this framework for the mtcmos sizing problem [21] using ssmo and stochastic decomposition techniques. the experimental results show that the solution obtained from stochastic decomposition based framework had 0% yield-loss, while the deterministic solution [21] had a 48% yield-loss.
variable domain transformation for linear pac analysis of mixed-signal systems. this paper describes a method to perform linear ac analysis on mixed-signal systems which appear strongly nonlinear in the voltage domain but are linear in other variable domains. common circuits like phase/delay-locked loops and duty-cycle correctors fall into this category, since they are designed to be linear with respect to phases, delays, and duty-cycles of the input and output clocks, respectively. the method uses variable domain translators to change the variables to which the ac perturbation is applied and from which the ac response is measured. by utilizing the efficient periodic ac (pac) analysis available in commercial rf simulators, the circuit's linear transfer function in the desired variable domain can be characterized without relying on extensive transient simulations. furthermore, the variable domain translators enable the circuits to be macromodeled as weakly-nonlinear systems in the chosen domain and then converted to voltage-domain models, instead of being modeled as strongly-nonlinear systems directly.