waashk/dblp huggingface dataset:
optimality and stability study of timing-driven placement algorithms. this work studies the optimality and stability of timing-drivenplacement algorithms. the contributions of this work include twoparts: 1) we develop an algorithm for generating synthetic examples with known optimal delay for timing driven placement(t-peko). the examples generated by our algorithm can closelymatch the characteristics of real circuits. 2) using these syntheticexamples with known optimal solutions, we studied the optimalityof several timing-driven placement algorithms for fpgas by comparing their solutions with the optimal solutions, and their stability by varying the number of longest paths in the examples. our study shows that with a single longest path, the delay produced by these algorithms is from 10% to 18% longer than the optima on the average, and from 34% to 53% longer in the worst case. furthermore, their solution quality deteriorates as the number of longest paths increases. for examples with more than 5 longest paths, their delay is from 23% to 35% longer than the optima on the average, and is from 41% to 48% longer in the worst case.
a thermal-driven floorplanning algorithm for 3d ics. as the technology progresses, interconnect delays have become bottlenecks of chip performance. 3d integrated circuits are proposed as one way to address this problem. however, thermal problem is a critical challenge for 3d ic circuit design. we propose a thermal-driven 3d floorplanning algorithm. our contributions include: (1) a new 3d floorplan representation, cba and new interlayer local operations to more efficiently exploit the solution space; (2) an efficient thermal-driven 3d floorplanning algorithm with an integrated compact resistive network thermal model (cba-t); (3) two fast thermal-driven 3d floorplanning algorithms using two different thermal models with different runtime and quality (cba-t-fast and cba-t-hybrid). our experiments show that the proposed 3d floorplan algorithm with cba representation can reduce the wirelength by 29% compared with a recent published result from (hsiu et al., 2004). in addition, compared to a nonthermal-driven 3d floorplanning algorithm, the thermal-driven 3d floorplanning algorithm can reduce the maximum on-chip temperature by 56%.
an enhanced multilevel routing system. in this paper, we present several novel techniques that make the recently published multilevel routing scheme [19] more effective and complete. our contributions include: (1) resource reservation for local nets during the coarsening process, (2) congestion-driven, graph-based steiner tree construction during the initial routing and the refinement process and (3) multi-iteration refinement considering the congestion history. the experiments show that each of these techniques helps to improve the completion rate considerately. compared to [19], the new routing system reduces the number of failed nets by 2&times; to 18&times;, with less than 50% increase in runtime in most cases.
thermal via planning for 3-d ics. heat dissipation is one of the most serious challenges in 3-d ic designs. one effective way of reducing circuit temperature is to introduce thermal through-the-silicon (tts) vias. in this paper, we extended the tts-via planning in a multilevel routing framework by cong and zhang (2005), but use a much enhanced tts-via planning algorithm. we formulate the tts-via minimization problem with temperature constraints as a constrained nonlinear programming problem (nlp) based on the thermal resistive model and develop an efficient heuristic algorithm, named m-advp, which solves a sequence of simplified via planning subproblems in alternating direction in a multilevel framework. the vertical via distribution is formulated as a convex programming problem, and the horizontal via planning is based on two efficient techniques: path counting and heat propagation. experimental results show that the m-advp algorithm is more than 200/spl times/ faster than the direct solution to the npl formulation for via planning with very similar solution quality (within 1% of ts-vias count). however, compared to a recent work of multilevel ts-via planning algorithm based on temperature profiling (cong and zhang, 2005), our algorithm can reduce the total ts-via number by over 68% for the same required temperature with similar runtime.
optimization of custom mos circuits by transistor sizing. optimization of a circuit by transistor sizing is often a slow, tedious and iterative manual process which relies on designer intuition. circuit simulation is carried out in the inner loop of this tuning procedure. automating the transistor sizing process is an important step towards being able to rapidly design high-performance, custom circuits. jiffytune is a new circuit optimization tool that automates the tuning task. delay, rise/fall time, area and power targets are accommodated. each (weighted) target can be either a constraint or an objective function. minimax optimization is supported. transistors can be ratioed and similar structures grouped to ensure regular layouts. bounds on transistor widths are supported. jiffytune uses lancelot, a large-scale nonlinear optimization package with an augmented lagrangian formulation. simple bounds are handled explicitly and trust region methods are applied to minimize a composite objective function. in the inner loop of the optimization, the fast circuit simulator specs is used to evaluate the circuit. specs is unique in its ability to efficiently provide time-domain sensitivities, thereby enabling gradient-based optimization. both the adjoint and direct methods of sensitivity computation have been implemented in specs. to assist the user, interfaces in the cadence and sled design systems have been constructed. these interfaces automate the specification of the optimization task, the running of the optimizer and the back-annotation of the results on to the circuit schematic. jiffytune has been used to tune over 100 circuits for a custom, high-performance microprocessor that makes use of dynamic logic circuits. circuits with over 250 tunable transistors have been successfully optimized. automatic circuit tuning has been found to facilitate design re-use. the designers' focus shifts from solving the optimization problem to specifying it correctly and completely. this paper describes the algorithms of jiffytune, the environment in which it is used and presents a case study of the application of jiffytune to individual circuits of the microprocessor.
circuit optimization via adjoint lagrangians. the circuit tuning problem is best approached by means of gradient-based nonlinear optimization algorithms. for large circuits, gradient computation can be the bottleneck in the optimization procedure. traditionally, when the number of measurements is large relative to the number of tunable parameters, the direct method is used to repeatedly solve the associated sensitivity circuit to obtain all the necessary gradients. likewise, when the parameters outnumber the measurements, the adjoint method is employed to solve the adjoint circuit repeatedly for each measurement to compute the sensitivities. in this paper, we propose the adjoint lagrangian method, which computes all the gradients necessary for augmented-lagrangian-based optimization in a single adjoint analysis. after the nominal simulation of the circuit has been carried out, the gradients of the merit function are expressed as the gradients of a weighted sum of circuit measurements. the weights are dependent on the nominal solution and on optimizer quantities such as lagrange multipliers. by suitably choosing the excitations of the adjoint circuit, the gradients of the merit function are computed via a single adjoint analysis, irrespective of the number of measurements and the number of parameters of the optimization. this procedure requires close integration between the nonlinear optimization software and the circuit simulation program. the adjoint lagrangian formulation has been implemented in the jiffytune tool which optimizes delay, area, slew (transition time) and power measurements by adjusting transistor widths and wire sizes. speedups of over 35x have been realized in the gradient computation procedure by using the adjoint lagrangian formulation, leading to speedups of up to 2.5x in the overall optimization procedure. perhaps more importantly, these speedups have rendered feasible the tuning of large circuits. a circuit with 6,900 transistors was optimized in under two hours of cpu time.
automatic netlist extraction for measurement-based characterization of off-chip interconnect. an approach is presented for modeling board level, package-level, and mcm substrate-level interconnect circuitry based an measured time domain refectometry data. the time-domain scattering parameters of a multiport system are used to extract a spice netlist which uses standard elements to match the behavior of the device up to a user-specified cutoff frequency. linear or nonlinear circuits may be connected to the model ports, and the entire circuit simulated in a standard circuit simulator. two-port and four-port example microstrip circuits are characterized, and the simulation results are compared with measured data. delay, reflection transmission, and crosstalk are accurately modeled in each case.
synthesis of asynchronous control circuits with automatically generated relative timing assumptions. this paper describes a method of synthesis of asynchronous circuits with relative timing. asynchronous communication between gates and modules typically utilizes handshakes to ensure functionality. relative timing assumptions in the form &ldquo;event a occurs before event b&rdquo; can be used to remove redundant handshakes and associated logic. this paper presents a method for automatic generation of relative timing assumptions from the untimed specification. these assumptions can be used for area and delay optimization of the circuit. a set of relative timing constraints sufficient for the correct operation of the circuit is back-annotated to the designer. experimental results for control circuits of a prototype ia32 instruction length decoding and steering unit called rappid (&ldquo;revolving asynchronous pentium&reg; processor instruction decoder&rdquo;) shows significant improvements in area and delay over speed-independent circuits.
decomposition and technology mapping of speed-independent circuits using boolean relations. presents a new technique for the decomposition and technology mapping of speed-independent circuits. an initial circuit implementation is obtained in the form of a netlist of complex gates, which may not be available in the design library. the proposed method iteratively performs boolean decomposition of each such gate f into a two-input combinational or sequential gate g, which is available in the library, and two gates h/sub 1/ and h/sub 2/, which are simpler than f, while preserving the original behavior and speed-independence of the circuit. to extract functions for h/sub 1/ and h/sub 2/, the method uses boolean relations, as opposed to the less powerful algebraic factorization approach used in previous methods. after logic decomposition, overall library matching and optimization is carried out. logic resynthesis, performed after speed-independent signal insertion for h/sub 1/ and h/sub 2/, allows for the sharing of decomposed logic. overall, this method is more general than existing techniques based on restricted decomposition architectures, and thereby leads to better results in technology mapping.
synthesizing petri nets from state-based models. this paper presents a method to synthesize labeled petri nets from state-based models. although state-based models (such as finite state machines) are a powerful formalism to describe the behavior of sequential systems, they cannot explicitly express the notions of concurrency, causality and conflict. petri nets can naturally capture these notions. the proposed method in based on deriving an elementary transition system (ets) from a specification model. previous work has shown that for any ets there exists a petri net with minimum transition count (one transition for each label) with a reachability graph isomorphic to the original ets. this paper presents the first known approach to obtain an ets from a non-elementary ts and derive a place-irredundant petri net. furthermore, by imposing constraints on the synthesis method, different classes of petri nets can be derived from the same reachability graph (pure, free choice, unique choice). this method has been implemented and efficiently applied in different frameworks: petri net composition, synthesis of petri nets from asynchronous circuits, and resynthesis of petri nets.
observability analysis of embedded software for coverage-directed validation. the most common approach to checking correctness of a hardware or software design is to verify that a description of the design has the proper behavior as elicited by a series of input stimuli. in the case of software, the program is simply run with the appropriate inputs, and in the case of hardware, its description written in a hardware description language (hdl) is simulated with the appropriate input vectors. in coverage-directed validation, coverage metrics are defined that quantitatively measure the degree of verification coverage of the design.motivated by recent work on observability-based coverage metrics for models described in a hardware description language, we develop a method that computes an observability-based code coverage metric for embedded software written in a high-level programming language. given a set of input vectors, our metric indicates the instructions that had no effect on the output. an assignment that was not relevant to generate the output value cannot be considered as being covered. results show that our method offers a significantly more accurate assessment of design verification coverage than statement coverage. existing coverage methods for hardware can be used with our method to build a verification methodology for mixed hardware/software or embedded systems.
synthesis of customized loop caches for core-based embedded systems. embedded system programs tend to spend much time in small loops. introducing a very small loop cache into the instruction memory hierarchy has thus been shown to substantially reduce instruction fetch energy. however, loop caches come in many sizes and variations -- using the configuration best on the average may actually result in worsened energy for a specific program. we therefore introduce a loop cache exploration tool that analyzes a particular program's profile, rapidly explores the possible configurations, and generates the configuration with the greatest power savings. we introduce a simulation-based approach and show the good energy savings that a customized loop cache yields. we also introduce a fast estimation-based approach that obtains nearly the same results in seconds rather than tens of minutes or hours.
incremental cad. comprehensive study of incremental algorithms and solutions in the context of cad tool development is an open area of research with a great deal of potential. incremental algorithms for synthesis and layout are needed when design undergoes local or incremental change. often these local changes are made to react to local change in the design, correct local errors or to make local improvements in one or more of the design quality metrics. in this paper we outline fundamental problems in incremental logic synthesis and physical design. preliminary solutions to a subset of these problems will be outlined.
a sum-over-paths impulse-response moment-extraction algorithm for ic-interconnect networks: verification, coupled rc lines. we have created a stochastic impulse-response (ir) moment-extractionalgorithm for rc circuit networks. it employs anewly discovered feynman sum-over-paths postulate. fullparallelism has been preserved. numerical verification resultsfor coupled rc lines confirmed rapid convergence. we believethis algorithm may find useful application in massively coupledelectrical systems, such as those encountered in high-enddigital-ic interconnects.
a high-level design and optimization tool for analog rf receiver front-ends. this paper presents a high-level analysis and optimization tool for the design of analog rf receiver front-ends, which takes all design parameters and all aspects of performance degradation (noise, distortion, self-mixing...) into account. the simulations are performed in the spectral domain with a behavioral model library for the rf building blocks. the tool allows to explore alternative rf receiver topologies as well as to investigate design trade-offs within each topology. by having integrated the performance analysis routine within a simulated annealing optimization loop, the tool can also perform an optimal high-level synthesis of a given topology towards a specific application. it then determines the optimal specifications for the rf building blocks such that the required receiver signal quality is met while the overall power and/or area consumption is minimized.
fault modeling and simulation for crosstalk in system-on-chip interconnects. system-on-chips (socs) using ultra deep sub-micron (dsm) technologies and ghz clock frequencies have been predicted by the 1997 sia road map. recent studies [3,4], as well as experiments reported in this paper, show significant crosstalk effects in long on-chip interconnects of ghz dsm chips. recognizing the importance of high-speed, reliable interconnects in ghz socs, we address in this paper the problem of testing for glitch and delay errors caused by crosstalk in buses and interconnects between components of a soc.since it is not possible to explicitly test for all the possible process variations and defects that can lead to crosstalk errors in soc interconnects, we present an abstract model, maximum aggressor (ma) fault model, and its test requirements. the attractiveness of the model is that it can abstract crosstalk defects in interconnects with a linear number of faults, while the corresponding ma tests provide complete coverage for all physical level defects related to cross-coupling capacitance between the interconnects. a spice-level fault simulation methodology is presented which allows simulation of a small subset of the potentially exponential number of defects. the simulation methodology also enables validation of the proposed fault model and the resulting test set.
simulation-based automatic generation of signomial and posynomial performance models for analog integrated circuit sizing. this paper presents a method to automatically generate posynomial response surface models for the performance parameters of analog integrated circuits. the posynomial models enable the use of efficient geometric programming techniques for circuit sizing and optimization. to avoid manual derivation of approximate symbolic equations and subsequent casting to posynomial format, techniques from design of experiments and response surface modeling in combination with spice simulations are used to generate signomial and posynomial models in an automatic way. attention is paid to estimating the relative 'goodness-of-fit' of the generated models. experimental results allow to assess both the quality of the generated models as well as the strengths and the limitations of the presented approach.
a multiple-dominance switch-level model for simulation of short faults. short faults in cmos networks frequently give rise to intermediate node voltages. an efficient local algorithm is presented for event-driven switch-level simulation of cmos networks in which intermediate signal values are common. the proposed model allows multiple dominant signals associated with the state of a node. the strength of several logical low and high signal contributions can thereby be taken into account when the logic state of a node is computed, which means that intermediate voltages can be handled more accurately. to demonstrate the usefulness of the multiple-dominance model in fault simulations, a new fault simulation algorithm is presented. various common transistor-level fault types were simulated, and the results show that the number of discrepancies from electrical-level simulations is significantly reduced at a low computational cost.
virtual screening: a step towards a sparse partial inductance matrix. we extend the partial inductance concept by replacing the magnetic interaction between open filaments i and j by that between filament j and a (finite) closed loop, formed by connecting the endpoints of a filament pair (i-i&prime;). the secondary filament i' is constructed by radial projection of filament i onto a cylindrical shell around filament j. we show that, although individual partial inductance values are modified, the inductive behaviour of the full circuit is invariant. mutual inductances of distant filaments are particularly reduced, because the far field of a conductor loop falls off much faster than that of a single filament. therefore, it is expected that subsequent removal of such transformed off-diagonal elements from the partial inductance matrix has less effect on the overall inductive properties, so our method provides a tool to enhance robustness under matrix sparsification. we call our method &ldquo;virtual screening&rdquo;, because the screening filaments {i&prime;} are not physically present. symmetry of the inductance matrix is preserved for orthogonal networks only.we also present an extension of our method to a more general class of shells. this allows a detailed comparison of the virtual screening method and the &ldquo;potential shift-truncate method&rdquo;, introduced with spherical equipotential shells [krauter et al. iccad'95] and extended to ellipsoidal equipotential shells recently [beattie et al. iedm'98]. we find strong similarities, but also differences. an interesting result is the fact that the virtual screening method with tubular shells applied to orthogonal networks can be interpreted as a generalization of the potential shift-truncate method to non-equipotential shells, which also implies that preservation of stability is guaranteed.some numerical results, sustaining the ideas behind our method, conclude the paper.
techniques for including dielectrics when extracting passive low-order models of high speed interconnect. interconnect structures including dielectrics can be modeled by an integral equation method using volume currents and surface charges for the conductors, and volume polarization currents and surface charges for the dielectrics. in this paper we describe a mesh analysis approach for computing the discretized currents in both the conductors and the dielectrics. we then show that this fully mesh-based formulation can be cast into a form using provably positive semidefinite matrices, making for easy application of krylovsubspace based model-reduction schemes to generate accurate guaranteed passive reduced-order models. several printed circuit board examples are given to demonstrate the effectiveness of the strategy.
proximity templates for modeling of skin and proximity effects on packages and high frequency interconnect. modeling the exponentially varying current distributions in conductor interiors associated with high frequency interconnect behavior causes a rapid increase in the computation time and memory required even by recently developed fast electromagnetic analysis programs. in this paper we describe a procedure to generate numerically a set of basis functions which efficiently represent conductor current variation, and thus improving solver efficiency. the method is based on solving a sequence of template problems, and is easily generalized to arbitrary conductor cross-sections. results are presented to demonstrate that the numerically computed basis functions are seven to twenty times more efficient than the commonly used piece-wise constant basis functions.