waashk/dblp huggingface dataset:
interpolating functions from large boolean relations. boolean relations are an important tool in system synthesis and verification to characterize solutions to a set of boolean constraints. for physical realization as hardware, a deterministic function often has to be extracted from a relation. prior methods however are unlikely to handle large problem instances. from the scalability standpoint this paper demonstrates how interpolation can be exploited to extend deter-minization capacity. a comparative study is performed on several proposed computation techniques. experimental results show that boolean relations with thousands of variables can be effectively determinized and the extracted functional implementations are of reasonable quality.
simultaneous layout migration and decomposition for double patterning technology. double patterning technology (dpt) and layout migration are two closely related problems on design for manufacturability in the nanometer era. dpt decomposes a layout into two masks and applies double exposure patterning to increase the pitch size and thus printability. in this paper, we present the first algorithm in the literature for the simultaneous layout migration and decomposition (smd) problem. our algorithm first constructs a conflict graph and dpt-aware constraint graphs, and then applies integer linear programming (ilp) corresponding to the graphs to obtain a decomposed and migrated layout. we further present an effective graph-based reduction technique to prune the ilp solution space, which maintains the same dpt conflicts. we also present a new dpt-aware objective for the smd problem to minimize the difference between the original and migrated layouts while considering the dpt effects. in addition, we present an approach to generate dpt-aware standard cells by considering the dpt effects on the cell boundaries; this technique improves the layout printability and facilitates eda tools to consider dpt. experimental results show that our algorithms can effectively generate conflict-free migrated layouts with 14% smaller layout areas and 28% smaller layout changes, compared with the traditional method of layout decomposition followed by layout migration. in particular, our reduction technique can reduce the runtimes for the test cases from more than one day for the basic ilp formulation to only seconds. can reduce the runtimes for the test cases from more than one day to only seconds.
final-value odes: stable numerical integration and its application to parallel circuit analysis. while solving initial-value odes is the de facto approach to time-domain circuit simulation, the opposite act, solving final-value odes, has been neglected for a long time. stable numerical integration of initial-value odes involves significant complications; the application of standard integration methods simply leads to instability. we show that not only practically meaningful applications of final-value ode problems exist, but also the inherent stability challenges may be addressed by recently proposed numerical methods. furthermore, we demonstrate an elegant bi-directional parallel circuit simulation scheme, where one time-domain simulation task is sped up by simultaneously solving initial and final-value odes, one from each end of the time axis. the proposed approach has unique and favorable properties: the solutions of the two ode problems are completely data independent with built-in automatic load balancing. as a specific application study, we demonstrate the proposed technique under the contexts of parallel digital timing simulation and the shooting-newton based steady-state analysis.
a method for calculating hard qos guarantees for networks-on-chip. many networks-on-chip (noc) applications exhibit one or more critical traffic flows that require hard quality of service (qos). guaranteeing bandwidth and latency for such real time flows is crucial. in this paper, we present novel methods to efficiently calculate worst-case bandwidth and latency bounds and thereby provide hard qos guarantees. importantly, the proposed methods apply even to best-effort noc architectures, with no extra hardware dedicated to qos support. by applying our methods to several realistic noc designs, we show substantial improvements (on average, more than 30% in bandwidth and 50% in latency) in bound tightness with respect to existing approaches.
taming irregular eda applications on gpus. recently general purpose computing on graphic processing units (gpus) is rising as an exciting new trend in high-performance computing. thus it is appealing to study the potential of gpu for electronic design automation (eda) applications. however, eda generally involves irregular data structures such as sparse matrix and graph operations, which pose significant challenges for efficient gpu implementations. in this paper, we propose highperformance gpu implementations for two important irregular eda computing patterns, sparse-matrix vector product (smvp) and graph traversal. on a wide range of eda problem instances, our smvp implementations outperform all published work and achieve a speedup of one order of magnitude over the cpu baseline. upon such a basis, both timing analysis and linear system solution can be considerably accelerated. we also introduce a smvp based formulation for breadth-first search and observe considerable speedup on gpu implementations. our results suggest that the power of gpu computing can be successfully unleashed through designing gpu-friendly algorithms and/or re-organizing computing structures of current algorithms.
pad assignment for die-stacking system-in-package design. wire bonding is the most popular method to connect signals between dies in system-in-package (sip) design nowadays. pad assignment, which assigns inter-die signals to die pads so as to facilitate wire bonding, is an important physical design problem for sip design because the quality of a pad assignment solution affects both the cost and performance of a sip design. in this paper, we study a pad assignment problem, which prohibits the generation of illegal crossings and aims to minimize the total signal wirelength, for die-stacking sip design. we first consider a variety of special cases and present a minimum-cost maximum-flow based approach to optimally solve them in polynomial time. we then describe an approach, which uses a modified left edge algorithm and an integer linear programming technique, to solve the general case. encouraging experimental results are shown to support our approaches.
dynatune: circuit-level optimization for timing speculation considering dynamic path behavior. traditional circuit design focuses on optimizing the static critical paths no matter how infrequently these paths are exercised dynamically. circuit optimization is then tuned to the worst-case conditions to guarantee error-free computation but may also lead to very inefficient designs. recently, there are processor works that over-clock the chip to achieve higher performance to the point where timing errors occur, and then error correction is performed either through circuit-level or microarchitecture-level techniques. this approach in general is referred to as timing speculation. in this paper, we propose a new circuit optimization technique "dynatune" for timing speculation based on the dynamic behavior of a circuit. dynatune optimizes the most dynamically critical gates of a circuit and improves the circuit's throughput under a fixed power budget. we test this proposed technique with two timing speculation schemes - telescopic unit (tu) and razor logic (rz). experimental results show that applying dynatune on the leon3 processor can increase the throughput of critical modules by up to 13% and 20% compared to the timing-speculative and non-timing-speculative results optimized by synopsys design compiler, respectively. for mcnc benchmark circuits, dynatune combined with tu can provide 9% and 20% throughput gains on average compared to timing-speculative and non-timing-speculative results optimized by design compiler. when combined with rz, dynatune can achieve 8% and 15% throughput gains on average for above experiments.
scheduling with soft constraints. in a behavioral synthesis system, a typical approach used to guide the scheduler is to impose hard constraints on the relative timing between operations considering performance, area, power, etc., so that the resulting rtl design is favorable in these aspects. the mechanism is often flawed in practice because many such constraints are actually soft constraints which are not necessary, and the constraint system may become inconsistent when many hard constraints are added for different purposes. this paper describes a scheduler that distinguishes soft constraints from hard constraints when exploring the design space. we propose a special class of soft constraints called integer-difference soft constraints, which lead to a totally unimodular constraint matrix in an integer linear programming formulation. by exploiting the total unimodularity, the problem can be solved optimally and efficiently using a linear programming relaxation without expensive branch and bound procedures. we also show how the proposed method can be used to support a variety of design considerations. as an example application, we apply the method to the problem of low-power synthesis with operation gating. in a set of experiments on real-world designs, our method achieves an average of 33.9% reduction in total power; it outperforms a previous method by 17.1% on average and gives close-to-optimal solutions on several designs.
decoupling capacitance efficient placement for reducing transient power supply noise. decoupling capacitance (decap) is an efficient way to reduce transient noise in on-chip power supply networks. however, excessive decap may cause more leakage power, chip resource waste, and even lead to more design iterations. in this paper, we present a novel decap-efficient placement algorithm for transient power supply noise reduction. in contrast to traditional design flow, our approach considers decap impacts at the placement stage to seek the placement minimizing decap requirements while still satisfying the traditional placement objectives. in the new method, we first devise a fast procedure to assess the decap requirement for the force-based placement framework, in which the required decap is modeled as a density function over the chip. then, we build a corresponding supply and demand system to adjust the placement in favor of minimizing decap. finally, we develop a decap efficient placement algorithm with a new force induced by imbalance between power supply and power demands. experimental results show that the new combined placement and decap optimization flow could reduce the minimum decap area by 35% with a wire length increase of only 0.5% at nearly the same computational cost, which is efficient for practical problems.
minimizing expected energy consumption through optimal integration of dvs and dpm. while dynamic voltage scaling (dvs) and dynamic power management (dpm) techniques are widely used in real-time embedded applications, their complex interaction is not fully understood. in this research effort, we consider the problem of minimizing the expected energy consumption on settings where the workload is known only probabilistically. by adopting a system-level power model, we formally show how the optimal processing frequency can be computed efficiently for a real-time embedded application that can use multiple devices during its execution, while still meeting the timing constraints. our evaluations indicate that the new technique provides clear (up to 35%) energy gains over the existing solutions that are proposed for deterministic workloads. moreover, in a non-negligible part of the parameter spectrum, the algorithm's performance is shown to be close to that of a clairvoyant algorithm that can minimize the energy consumption with the advance knowledge about the exact workload.
layout-driven test-architecture design and optimization for 3d socs under pre-bond test-pin-count constraint. we propose a layout-driven test-architecture design and optimization technique for core-based system-on-chips (socs) that are fabricated using three-dimensional (3d) integration. in contrast to prior work, we consider the pre-bond test-pin-count constraint during optimization since these pins occupy large silicon area that cannot be used in functional mode. in addition, the proposed test-architecture design takes the soc layout into consideration and facilitates the sharing of test wires between pre-bond tests and post-bond test, which significantly reduces the routing cost for a test-access mechanism in 3d technology. experimental results for the itc'02 soc benchmarks circuits demonstrate the effectiveness of the proposed solution.
modeling of layout-dependent stress effect in cmos design. strain technology has been successfully integrated into cmos fabrication to improve carrier transport properties since 90nm node. due to the non-uniform stress distribution in the channel, the enhancement in carrier mobility, velocity, and threshold voltage shift strongly depend on circuit layout, leading to systematic performance variations among transistors. a compact stress model that physically captures this behavior is essential to bridge the process technology with design optimization. in this paper, starting from the first principle, a new layout-dependent stress model is proposed as a function of layout, temperature, and other device parameters. furthermore, a method of layout decomposition is developed to partition the layout into a set of simple patterns for efficient model extraction. these solutions significantly reduce the complexity in stress modeling and simulation. they are comprehensively validated by tcad simulation and published si-data, including the state-of-the-art strain technologies and the sti stress effect. by embedding them into circuit analysis, the interaction between layout and circuit performance is well benchmarked at 45nm node.
ghm: a generalized hamiltonian method for passivity test of impedance/admittance descriptor systems. a generalized hamiltonian method (ghm) is proposed for passivity test of descriptor systems (dss) which describe impedance or admittance input-output responses. ghm can test passivity of dss with any system index without minimal realization. this frequency-independent method can avoid the time-consuming system decomposition as required in many existing ds passivity test approaches. furthermore, ghm can test systems with singular d + dt where traditional hamiltonian method fails, and enjoys a more accurate passivity violation identification compared to frequency sweeping techniques. numerical results have verified the effectiveness of ghm. the proposed method constitutes a versatile tool to speed up passivity check and enforcement of dss and subsequently ensures globally stable simulations of electrical circuits and components.
active-passive co-synthesis of multi-gigahertz radio frequency circuits with broadband parametric macromodels of on-chip passives. synthesis of multi-gigahertz radio frequency circuits brings together difficult challenges related to simulation, extraction and multidimensional space search. the standard approach of mapping all electromagnetic parasitics into parametric rlc models prior to synthesis is extremely restrictive especially when broadband and full-wave models with high accuracy are needed. in the presented approach, a two-stage macromodel that creates broadband, accurate parametric representations of passives, in particular spiral inductors, is developed. the broadband nature is captured through the vector fitting algorithm. the macromodels are implemented via efficient nonlinear, multidimensional regression using relevance vector machine, and are coupled into circuit simulators through admittance parameters. subsequently, optimization on both active and passive parameters are carried out simultaneously, thereby bypassing the ad hoc nature of two stage (actives and passives) approximate optimization. two standard low-noise amplifier topologies are synthesized with tight performance constraints at center frequencies 5, 10 and 12 gigahertz in order to demonstrate the frequency scalability of the methodology.
temporal and spatial idleness exploitation for optimal-grained leakage control. runtime leakage control techniques, such as power gating (pg) and body biasing (bb), have been applied in a coarse-grained manner traditionally. in order to enable more aggressive leakage reduction, researchers are seeking ways to control leakage with finer granularity. our research proposes two novel methods, namely circuit clustering for temporal and spatial idleness exploitation, to systematically reduce the granularity of leakage control and improve leakage reduction. another strength of this paper is the quantitative study of leakage saving and control cost by leakage control with different granularity. with our quantitative study, designers can make the trade-off between leakage saving and control cost, and decide the optimum granularity for leakage control. a heuristic algorithm has been developed to automate the two circuit clustering methods and determine the optimum granularity for any given circuit. the analysis and experiments of this paper is mainly based on rbb. they are also applicable to pg by modifying the cost function.
a hierarchical floating random walk algorithm for fabric-aware 3d capacitance extraction. with the adoption of ultra regular fabric paradigms for controlling design printability at the 22nm node and beyond, there is an emerging need for a layout-driven, pattern-based parasitic extraction of alternative fabric layouts. in this paper, we propose a hierarchical floating random walk (hfrw) algorithm for computing the 3d capacitances of a large number of topologically different layout configurations that are all composed of the same layout motifs. our algorithm is not a standard hierarchical domain decomposition extension of the well established floating random walk technique, but rather a novel algorithm that employs markov transition matrices. specifically, unlike the fast-multipole boundary element method and hierarchical domain decomposition (which use a far-field approximation to gain computational efficiency), our proposed algorithm is exact and does not rely on any tradeoff between accuracy and computational efficiency. instead, it relies on a tradeoff between memory and computational efficiency. since floating random walk type of algorithms have generally minimal memory requirements, such a tradeoff does not result in any practical limitations. the main practical advantage of the proposed algorithm is its ability to handle a set of layout configurations in a complexity that is basically independent of the set size. for instance, in a large 3d layout example, the capacitance calculation of 120 different configurations made of similar motifs is accomplished in the time required to solve independently just 2 configurations, i.e. a 60x speedup.
timing arc based logic analysis for false noise reduction. the problem of calculating accurate impact of crosstalk on a circuit considering its inherent logic and timing properties is very complex. although it has been widely studied, it still lacks an efficient solution. as a result, state-of-the-art crosstalk calculators use simplistic and overly pessimistic models resulting in the over-estimation of crosstalk effects. such pessimism in crosstalk analysis often leads to the triggering of false violations and consequently an inefficient use of design resources. the main contribution of this paper is a novel technique called timing arc based logic analysis (tabla) that serves as an efficient means to calculate realistic crosstalk bounds. tabla uses timing arcs as basic elements to perform an efficient temporal logic analysis employing the min-max timing model using dedicated solvers for logic and timing. additionally, a procedure to generate powerful conflict clauses is proposed to improve the run time of the overall analysis. the proposed technique has been tested in an industrial environment on benchmark circuits as well as on an industrial design, and results are provided.
iterative layering: optimizing arithmetic circuits by structuring the information flow. current logic synthesis techniques are ineffective for arithmetic circuits. they perform poorly for xor-dominated circuits, and those with a high fan-in dependency between inputs and outputs. many optimizers, therefore employ libraries of hand-optimized arithmetic components, but cannot optimize across component boundaries. to remedy this situation, we introduce a new logic synthesis algorithm which analyzes the input circuit based on its behavior on a set of random assignments of input variables, and outputs a structural implementation of the input circuit. the method presented here is similar to the covering algorithm used in multi-level optimizations [4]; however, it is not based on sum-of-product form, or any specific input representation. our experiments show that our approach is not only capable of automatically reproducing some known architectural implementations without any prior knowledge about the functionality of the circuit, but also, in some cases, it is able to discover completely new designs which we have not seen described in literature.
the epsilon-approximation to discrete vt assignment for leakage power minimization. as vlsi technology reaches 45nm technology node, leakage power optimization has become a major design challenge. threshold voltage (vt) assignment has been extensively studied, due to its effectiveness in leakage power reduction. in contrast to the efficiently solvable continuous vt assignment problem, the discrete vt assignment problem is known to be np-hard. all of the existing techniques are heuristics without performance guarantee due to the np-hardness nature of the problem. it is still not known whether there is any rigorous approximation algorithm for the discrete vt assignment problem. in this paper, the first &epsilon;-approximation algorithm is designed for the discrete vt assignment problem. the algorithm can &epsilon;-approximate the optimal vt assignment solution in o([equation]) time, where n is the size of the combinational circuit and m is the number of available threshold voltages per gate. it is based on an advanced potential function technique and an efficient dual decision core query technique. our experiments on iscas'85 benchmark circuits demonstrate that the new algorithm always returns a solution with error bounded by &epsilon; even compared to the lower bound of the optimal solution. on average, it can approximate the optimal solution with 2.8% additional leakage power running in 51.3 seconds, while the integer linear programming technique is computationally prohibitive. our algorithm also significantly outperforms the heuristic in [1] by 16.5% leakage power saving with similar runtime. this clearly demonstrates the practicality of the proposed &epsilon;-approximation algorithm for the vt assignment problem.