waashk/dblp huggingface dataset:
generalized fdtd-adi: an unconditionally stable full-wave maxwell's equations solver for vlsi interconnect modeling. the finite-difference time-domain (fdtd) method of solving the full-wave maxwell's equations has been recently extended to provide accurate and numerically stable operation for time steps exceeding the courant limit. the elimination of an upper bound on the size of the time step was achieved using an alternating-implicit direction (adi) time-stepping scheme. this greatly increases the computational efficiency of the fdtd method for classes of problems where the cell size of the three-dimensional space lattice is constrained to be much smaller than the shortest wavelength in the source spectrum. one such class of problems is the analysis of high-speed vlsi interconnects where full-wave methods are often needed for the accurate analysis of parasitic electromagnetic wave phenomena. in this paper, we present an enhanced fdtd-adi formulation which permits the modeling of realistic lossy materials such as semiconductor substrates and metal conductors as well as artificial lossy materials needed for perfectly matched layer (pml) absorbing boundary conditions. simulations using our generalized fdtd-adi formulation are presented to demonstrate the accuracy and extent to which the computational burden is reduced by the adi scheme.
perturb and simplify: multi-level boolean network optimizer. in this paper, we discuss the problem of optimizing a multi-level logic combinational boolean network. our techniques apply a sequence of local perturbations and modifications of the network which are guided by the automatic test pattern generation atpg based reasoning. in particular, we propose several new ways in which one or more redundant gates or wires can be added to a network. we show how to identify gates which are good candidates for local functionality change. furthermore, we discuss the problem of adding and removing two wires, none of which alone is redundant, but when jointly added/removed they do not affect functionality of the network. we also address the problem of efficient redundancy computation which allows to eliminate many unnecessary redundancy tests. we have performed experiments on mcnc benchmarks and compared the results to those of misii and rambo. experimental results are very encouraging.
overall consideration of scan design and test generation. a complete system which takes the test generation algorithm, the scan cell selection strategy and the structure of the scan chain into account is proposed. it is totally different from the traditional approaches which try to enhance the ability of the individual subject. the goal of this research is to reduce the extra costs caused by the scan design, especially the test application time. experimental results show that the overall consideration of scan design and test generation can speed up test generation and greatly reduce the amount of test application time
post-placement rewiring and rebuffering by exhaustive search for functional symmetries. separate optimizations of logic and layout have been thoroughly studied in the past and are well documented for common benchmarks. however, to be competitive, modern circuit optimizations must use physical and logic information simultaneously. in this work, we propose new algorithms for rewiring and rebuffering - a post-placement optimization that reconnects pins of a given netlist without changing the logic function and gate locations. these techniques are compatible with separate layout and logic optimizations, and appear independent of them. in particular, when the new optimization is applied before or after detailed placement, it approximately doubles the improvement in wirelength. our contributions are based on exhaustive search for functional symmetries in sub-circuits consisting of several gates. our graph-based symmetry finding is more comprehensive than previously known algorithms - it detects permutational and phase-shift symmetries on multiple input and output wires, as well as hybrid symmetries, creating more opportunities for rewiring and rebuffering.
integrating loop and data optimizations for locality within a constraint network based framework. in the context of data-intensive embedded applications, there have been two complementary approaches to data locality problem: restructuring code and restructuring data layout. conceivably, an integrated approach that combines these two can generate much better results than each individual approach. however, there is an inherent difficulty in optimizing both data layout and loop access pattern simultaneously under a unified setting. this difficulty occurs due to the fact that a given data structure can be accessed by different loop nests of the application, and each such loop nest can demand a different memory layout transformation for the said data structure. this results in a coupling problem, where the behaviors of two (or more) loop nests are coupled to each other as a result of data sharing between them. in this paper, we present a constraint network (cn) based formulation of the integrated loop-data optimization problem. we present two alternate solutions to the data locality problem with our cn based formulation and discuss the pros and cons of each scheme. the first solution is a pure backtracking based one, whereas the second one improves upon the first one by employing three additional optimizations, including backjumping.
an iterative gate sizing approach with accurate delay evaluation. this paper introduces a new gate sizing approach with accurate delay evaluation. the approach solves gate sizing problems by iterating local sizing results from linear programming within small variable ranges of gate sizes. in each iterative step, variable ranges of gate sizes are updated according to the result from a previous step. solutions with accurate delay evaluation which consider input signal slopes and separately evaluate rising and falling delays are obtained after several iterative steps. a speedup technique is used to pick out gates actually involved in each local sizing step so as to reduce cpu time. experiments on sample circuits show that our approach can provide solutions with smaller circuit area than conventional approaches for the same circuit delay or provide solutions under tight delay constraints where conventional approaches can not reach. moreover, our approach is faster than the conventional approaches for most circuits, especially under loose delay constraints.
statistical timing analysis considering spatial correlations using a single pert-like traversal. we present an efficient statistical timing analysis algorithm thatpredicts the probability distribution of the circuit delay while incorporatingthe effects of spatial correlations of intra-die parametervariations, using a method based on principal component analysis.the method uses a pert-like circuit graph traversal, and hasa run-time that is linear in the number of gates and interconnects,as well as the number of grid partitions used to model spatial correlations.on average, the mean and standard deviation valuescomputed by our method have errors of 0.2% and 0.9%, respectively,in comparison with a monte carlo simulation.
a new global routing algorithm for fpgas. as in traditional asic technologies, fpga routing usually consists of two steps: global routing and detailed routing. unlike existing fpga detailed routers, which can take full advantage of the special structures of the programmable routing resources, fpga global routing algorithms still greatly resemble their counterparts in the traditional asic technologies. in particular, the routing congestion information of a switch block essentially is still measured by the numbers of available rows and columns in the switch block. since the internal architecture of a switch block decides what can route through the block, the traditional measure of routing capacity is no longer accurate. in this paper, we present an accurate measure of switch block routing capacity. our new measure considers the exact positions of the switches inside a switch block. experiments with a global router based on these ideas show an average improvement of 38% in the channel width required to route some benchmark circuits using a popular switch block, compared with an algorithm based on the traditional methods for congestion control.
wire reconnections based on implication flow graph. global flow optimization (gfo) can perform the fanout/fanin wire re-connections by modeling the problem of the wire reconnections by a flow graph and then solving the problem using the maxflow-mincut algorithm on the flow graph. however, the flow graph cannot fully characterize the wire re-connections which causes gfo to lose optimality on several obvious cases. in addition, we find that the fanin re-connection can have more optimization power than the fanout re-connection but requires more sophisticated modeling. in this paper, we re-formulate the problem of the fanout/fanin re-connections by a new graph called the implication flow graph. we show that the problem of wire re-connections on the implication flow graph is np complete and also propose an efficient heuristic on the new graph. our experimental results are very exciting.
a wire-length minimization algorithm for single-layer layouts. the authors consider a steiner tree s interconnecting a set n of terminals. the minimizing length of s can be shown to be equivalent to the traditional (np-hard) steiner tree problem. an exact polynomial-time algorithm for minimizing the length of s when operations on s are limited is presented. these operations are called topology preserving transformations (tpts). based on the notion of tpt, an exact algorithm for minimizing the total length of a single-layer layout involving a set of multi-terminal nets and a collection of obstacles is proposed. the algorithm has been used to find a minimum length single-layer layout. the algorithm was also applied to find a steiner tree interconnecting a net n of terminals. the idea is to find a minimum spanning tree t of n. then, generate k steiner trees by randomly flipping edges of t to both its upper- and lower-l-shaped configurations. then, a topology preserving transformation is applied to each steiner tree. the best of them is selected as the final steiner tree. on the average, 9.4% improvement over the mst length has been reported
behavioral synthesis for testability. a synthesis for testability approach is presented. in this approach test points or flip-flops to be used in test point insertion or partial scan to enhance circuit testability are selected. the selection is based on circuit behavioral information rather than low level structural description. this allows test point insertion or partial scan usage on circuits described as interconnections of high level modules. test statement insertion is also proposed as an alternative to test point insertion and to partial scan. the major advantage of using test statement insertion is a lower pin count and lower test application time overhead than test point insertion and partial scan. the tool has been implemented in a computer program
provably good algorithm for low power consumption with dual supply voltages. dual-voltage approach emerges as an effective and practical technique for power reduction. in this paper we explore the power optimization with dual supply voltages under the given timing constraints. by analyzing the relations among the timing slack, delay and power consumption in a given circuit, we relate the voltage-scaling power optimization to maximal-weighted-independent-set (mwis) problem which is polynomial-time solvable on transitive graph. then we develop a provably good lower-bound algorithm based on mwis to generate the lower bound of power consumption. also, we propose a fast approach to predict the optimum supply voltages. the maximum power reduction is obtained by using the modified lower-bound algorithm with optimum voltages. experimental results show that the resulting lower bound is tight for most circuits and that the estimated optimum supply voltage is exactly, or very close to, the best choice of actual voltages.
layer assignment for high-performance multi-chip modules. in this paper, we present a layer assignment method for high-performance multi-chip module environments. in contrast with treating global routing and layer assignment separately, our method assigns nets to layers while considering preferable global routing topologies simultaneously. we take transmission line effects into account to avoid noise in high-speed circuit packages. the problem is formulated as a quadratic boolean programming problem and an algorithm is presented to solve the problem after linearization. our method is applied to a set of benchmark circuits to demonstrate the effectiveness.
signal integrity optimization on the pad assignment for high-speed vlsi design. in this paper, an efficient method is proposed to effectively minimize both simultaneous switching noise and crosstalk that are inevitably caused by package inductance and capacitance during the design of high-speed/high-bandwidth circuits. due to its efficiency, our algorithm can be incorporated into existing circuit floorplanning and placement schemes for the co-design of vlsi and packaging. for a set of industrial circuits/packages tested in our experiment, on the average, our method achieves a 16.8% reduction of total electrical noise when compared with the conventional design rule of thumb popularly used by circuit designers.
response shaper: a novel technique to enhance unknown tolerance for output response compaction. the presence of unknown values in the simulation result is a key barrier to effective output response compaction in practice. this paper proposes a simple circuit module, called a response shaper, to reshape the scan-out responses before feeding them to a space compactor. along with the proposed reshaping algorithm, response shapers can help the space compactor to reduce the number of undetectable modeled and unmodeled faults in the presence of unknown values. moreover, the proposed compaction scheme is atpg-independent and its hardware requirement is pattern-independent. in our experiments, we use a simple xor compactor as the space compactor to evaluate the effectiveness of the response shaper. the results show that the number of undetectable faults and unobservable scan-out responses can be significantly reduced in comparison with the results of a convolutional compactor. the number of the extra scan-in bits required for the control signals of the response shapers is only a small fraction of the total test data volume. also, its hardware overhead is acceptable and the runtime of the reshaping algorithm is scalable for large industrial designs.
hisim: hierarchical interconnect-centric circuit simulator. to ensure the power and signal integrity of modern vlsi circuits, it is crucial to analyze huge amount of nonlinear devices together with enormous interconnect and even substrate parasitics to achieve the required accuracy. neither traditional circuit simulation engines such as spice nor switch-level timing analysis algorithms are equipped to handle such a tremendous challenge in both efficiency and accuracy. we establish a solid framework that simultaneously takes advantage of a hierarchical nonlinear circuit simulation algorithm and an advanced large-scale linear circuit simulation method using a new predictor-corrector algorithm. under solid convergence and stability guarantees, our simulator, hisim, a hierarchical interconnect-centric circuit simulator, is capable of handling the post-layout rlkc power and signal integrity analysis task efficiently and accurately. experimental results demonstrate over 180x speed up over the conventional flat simulation method with spice-level accuracy.
a clustering- and probability-based approach for time-multiplexed fpga partitioning. improving logic density by time-sharing, time-multiplexed fpgas (tmfpgas) have become an important research topic for reconfigurable computing. due to the precedence and capacity constraints in tmfpgas, the clustering and partitioning problems for tmfpgas are different from the traditional ones. in this paper, we propose a two-phase hierarchical approach to solve the partitioning problem for tmfpgas. with the precedence and capacity considerations for both phases, the first phase clusters nodes to reduce the problem size, and the second phase applies a probability-based iterative-improvement approach to minimize cut cost. experimental results based on the xilinx tmfpga architecture show that our algorithm significantly outperforms previous works.
semi-analytical techniques for substrate characterization in the design of mixed-signal ics. a number of methods are presented for highly efficient calculation of substrate current transport. a three-dimensional green function based substrate representation, in combination with the use of the fast fourier transform, significantly speeds up the computation of sensitivities with respect to all parameters associated with a given architecture. substrate sensitivity analysis is used in a number of physical optimization tools, such as placement and trend analysis for the estimation of the impact of technology migration and/or layout re-design.
generalized constraint generation in the presence of non-deterministic parasitics. in a constraint-driven layout synthesis environment, parasitic constraints are generated and implemented in each phase of the design process to meet a given set of performance specifications. the success of the synthesis phase depends in great part on the effectiveness and the generality of the constraint generation process. none of the existing approaches to the constraint generation problem however are suitable for a number of parasitic effects in active and passive devices due to non-deterministic process variations. to address this problem a novel methodology is proposed based on the separation of all variables associated with non-deterministic parasitics, thus allowing the translation of the problem into an equivalent one in which conventional constrained optimization techniques can be used. the requirements of the method are a well-defined set of statistical properties for all parasitics and a reasonable degree of linearity of the performance measures relevant to design.
potential slack: an effective metric of combinational circuit performance. this paper proposes the concept of potential slack and show it is an effective metric of combinational circuit performance. we provide several methods for estimating potential slack and prove one (a maximal-independent-set based algorithm) in particular works best. experiments in gate sizing show that potential slack provides 100% correct prediction for circuit area optimization. we also explore the role of potential slack in timing-driven placement.
copyright protection of designs based on multi source ips. this paper addresses the copyright protection problem of integrated circuits designed with blocks which are originated from multiple design sources. the process consists of two phases. first, a compact signature is generated from every block independently and made public. utilizing such signatures, a design can be decomposed into its original building blocks, regardless of multiple hierarchies. then, a map of all the blocks can be built, thus allowing to reconstruct the original copyright dependencies. the proposed methodology can be used by foundries to verify that designs submitted for fabrication contain blocks traceable to a legal source of intellectual property. the verification process is also useful to intellectual property providers and integrators, as it reduces the likelihood of infringement, thus ultimately minimizing the risk of litigation.
a sliding window scheme for accurate clock mesh analysis. mesh architectures are used for distributing critical global signals on a chip such as clock and power/ground. the inherent redundancy created by loops present in the mesh smooths out undesirable variations between signal nodes spatially distributed over the chip. however, one outstanding problem with mesh architectures is the difficulty in analyzing them with sufficient accuracy. in this paper, we present a new sliding window-based scheme to analyze the latency in clock meshes. we show that for small meshes, our scheme comes within 1% of the spice simulation of the complete mesh with respect to clock latency. our scheme is ideally suited for distributed- or grid-computing. we show large design instances where spice could not finish, whereas our scheme could complete the analysis in less than 2 hours.
raft191486: a novel program for rapid-fire test and diagnosis of digital logic for marginal delays and delay faults. the problem of delay fault-testing and detection of chips with marginal performance has become even more critical than before due to advancing clock speeds. in this paper, a methodology for detection of marginal digital circuits and diagnosis of gate delay failures is developed. a new test application methodology is proposed in which test vectors may be applied to digital combinational circuits at intervals smaller than the critical path delay of the circuit and signal waveform analysis is used to interpret the test results. the resulting tests are called rapid fire tests (for raft) and allow classification of circuits from &ldquo;good&rdquo; to &ldquo;bad&rdquo; along a continuous scale.
timing macro-modeling of ip blocks with crosstalk. with the increase of design complexities and the decrease of minimal feature sizes, ip reuse is becoming a common practice while crosstalk is becoming a critical issue that must be considered. this work presents two macro-models for specifying the timing behaviors of combinational hard ip blocks with crosstalk effects. the gray-box model keeps a coupling graph and lists the conditions on relative input arrival time combinations for couplings not to take effect. the black-box model stores the output response windows for a basic set of relative input arrival time combinations, and computes the output arrival time for any given input arrival time combination through the union of some combinations in the basic set. both macro-models are conservative, and can greatly reduce the pessimism existing in the conventional "pin-to-pin" model. this is the first work to deal with timing macro-modeling of combinational hard ip blocks with the consideration of crosstalk effects.
a new incremental placement algorithm and its application to congestion-aware divisor extraction. this work presents two contributions. the first is an incremental placement algorithm for placement-aware logic synthesis along with a proof of optimality. the algorithm can efficiently compute the optimum location for a newly introduced node in a network that minimizes the incremental increase in the total half-perimeter wire-length of the network. the algorithm can be applied in a variety of placement-aware optimization contexts. the second contribution is a specific application of this algorithm to placement-aware common divisor extraction. we evaluate the effectiveness of the proposed extraction procedure by using it in an otherwise non-placement-aware flow with two different final placers. the first flow uses an industrial congestion-driven placer and results in an average reduction of 21% in congestion as measured by the global router. the second flow uses an academic wire-length-driven placer and results in an average reduction of 11% for a tool-specific measure of congestion estimated from the placement. our experiments also reveal a rather surprising phenomenon: in many cases the attempt to minimize the wire-length results in fewer literals after extraction than with a conventional literal-driven approach.