waashk/dblp huggingface dataset:
a hierarchical decomposition methodology for multistage clock circuits. this paper describes a novel methodology to automate the design of the interconnect distribution for multistage clock circuits. we introduce two key ideas. first, a hierarchical decomposition of the layout divides the problem into a set of local steiner-wired latch clusters (to minimize and balance local capacitance) fed globally by a balanced binary tree (to maximize performance). second, we recast the global clock distribution problem as a simultaneous optimization of clock topology, clock segment routing, wiresizing, and buffering. the hierarchical decomposition reduces the problem complexity and allows use of more aggressive optimization techniques. integration of the geometric and electrical optimizations likewise allows more aggressive performance goals. experiments with an industrial design comprising over 16,000 latches demonstrate the efficiency of the approach: a complete clock distribution solution met a 200mhz cycle time specification with only 310ps of skew, met strict current density constraints, exhibited good delay matching across uniform wire width and device variations, and was completed in under 10 cpu hours.
replication for logic bipartitioning. logic replication, the duplication of logic in order to limit communication between partitions, is an effective part of a complete partitioning solution. in this paper we seek a better understanding of the important issues in logic replication. by developing new optimizations to existing algorithms we are able to significantly improve the quality of these techniques, achieving up to 12.5% better results than the best existing replication techniques. when integrated into our already state-of-the-art partitioner, we improve overall cutsizes by 37.8%, while requiring the duplication of at most 7% of the logic.
embedded program timing analysis based on path clustering and architecture classification. formal program running time verification is an important issue in system design required for performance optimization under "first-time-right" design constraints and for real-time system verification. simulation based approaches or simple instruction counting are not appropriate and risky for more complex architectures in particular with data dependent execution paths. formal analysis techniques have suffered from loose timing bounds leading to significant performance penalties when strictly adhered to. we present an approach which combines simulation and formal techniques in a safe way to improve analysis precision and tighten the timing bounds. using a set of processor parameters, it is adaptable to arbitrary processor architectures. the results show an unprecedented analysis precision allowing to reduce performance overhead for provably correct system or interface timing.
transmission line design of clock trees. we investigate appropriate regimes for transmission line propagation of signals on digital integrated circuits. we start from exact solutions to the transmission line equations proposed by davis and meindl. we make appropriate modifications due to finite rise time. they affect the delay calculation and hypothesis pertaining the constancy of the electromagnetic parameters. we study these effects in detail. to find the domain of physical variables where transmission line behavior is feasible, we pose the problem as a nonlinear minimization problem in a space spanned by two continuous variables, with four parameters. from the resulting solutions and employing monotonicity properties of the functional we extract regimes of validity. these regimes of validity happen to be commensurate with what is reachable and doable with todays leading technologies. we complete this study with a qualitative analysis of driver insertion in the presence of transmission lines. the resulting configurations are suitable for the development of an improved clock design discipline.
attractor-repeller approach for global placement. traditionally, analytic placement used linear or quadratic wirelength objective functions. minimizing either formulation attracts cells sharing common signals (nets) together. the result is a placement with a great deal of overlap among the cells. to reduce cell overlap, the methodology iterates between global optimization and repartitioning of the placement area. in this work, we added new attractive and repulsive forces to the traditional formulation so that overlap among cells is diminished without repartitioning the placement area. the superiority of our approach stems from the fact that our new formulations are convex and no hard constraints are required. a preliminary version of the new placement method is tested using a set of mcnc benchmarks1 and, on average, the new method achieved 3.96% and 7.6% reduction in wirelength and cpu time compared to timberwolf v7.0 in hierarchical mode [10].
a router for symmetrical fpgas based on exact routing density evaluation. this paper presents a new performance and routability driven routing algorithm for symmetrical array based field-programmable gate arrays (fpgas). a key contribution of our work is to overcome one essential limitation of the previous routing algorithms: inaccurate estimations of routing density which were too general for symmetrical fpgas. to this end, we derive an exact routing density calculation that is based on a precise analysis of the structure (switch block) of symmetrical fpgas, and utilize it consistently in global and detailed routings. with an introduction of the proposed accurate routing metrics, we design a new routing algorithm called a cost-effective net-decomposition based routing which is fast, and yet produces remarkable routing results in terms of both routability and path/net delays. we performed an extensive experiment to show the effectiveness of our algorithm based on the proposed cost metrics.
voltage-drop-constrained optimization of power distribution network based on reliable maximum current estimates. the problem of optimum design of tree-shaped power distribution networks with respect to the voltage drop effect is addressed in this paper. an approach for the width adjustment of the power lines supplying the circuit's major functional blocks is formulated, so that the network occupies the minimum possible area under specific voltage drop constraints at all blocks. the optimization approach is based on precise maximum current estimates derived by statistical means from recent advances in the field of extreme value theory. experimental tests include the design of power grid for a choice of different topologies and voltage drop tolerances in a typical benchmark circuit.
binary time-frame expansion. this paper introduces a new method for performing time-frame expansion based on writing the number of time frames in terms of powers of two. in the proposed method, the behavior of a circuit for t time frames, where n 0 ⪣t < n is modeled by unrolling the circuit 20, 21, 22, ..., 2(log n &minus;1) times and combining them. this formulation of the problem makes it possible to prune the search space quickly when the problem is infeasible. to show the advantage of this method, we have used it to model the state justification problem and solve the problem using a sat-solver. experimental results show several orders of magnitude speedup for some non-trivial infeasible problems. furthermore, in most cases the cpu time requirement grows linearly in terms of the number of time frames.
general models for optimum arbitrary-dimension fpga switch box designs. an fpga switch box is said to be hyper-universal if it is routable for all possible surrounding multi-pin net topologies satisfying the routing resource constraints. it is desirable to design hyper-universal switch boxes with the minimum number of switches. a previous work, universal switch module, considered such a design problem concerning 2-pin net routings around a single fpga switch box. however, as most nets are multi-pin nets in practice, it is imperative to study the problem that involves multi-pin nets. in this paper, we provide a new view of global routings and formulate the most general &kappa;-sided switch box design problem into an optimum &kappa;-partite graph design problem. applying a powerful decomposition theorem of global routings, we prove that, for a fixed &kappa;, the number of switches in an optimum &kappa;-sided switch box with w terminals on each side is o (w), by constructing some hyper-universal switch boxes with o(w) switches. furthermore, we obtain optimum, hyper-universal 2-sided and 3-sided switch boxes, and propose hyper-universal 4-sided switch boxes with less than 6.7w switches, which is very close to the lower bound 6w obtained for pure 2-pin net models in [5].
a routing algorithm for flip-chip design. the flip-chip package gives the highest chip density of any packaging method to support the pad-limited application-specific integrated circuit (asic) designs. in this paper, we propose the first router for the flip-chip package in the literature. the router can redistribute nets from wire-bonding pads to bump pads and then route each of them. the router adopts a two-stage technique of global routing followed by detailed routing. in global routing, we use the network flow algorithm to solve the assignment problem from the wire-bonding pads to the bump pads, and then create the global routing path for each net. the detailed routing consists of three stages, cross point assignment, net ordering determination, and track assignment, to complete the routing. experimental results based on seven real designs from the industry demonstrate that the router can reduce the total wirelength by 10.2%, the critical wirelength by 13.4%, and the signal skews by 13.9%, compared with a heuristic algorithm currently used in industry.
fast, accurate static analysis for fixed-point finite-precision effects in dsp designs. translating digital signal processing (dsp) software intoits finite-precision hardware implementation is often a time-consumingtask. we describe a new static analysis techniquethat can accurately analyze finite-precision effects arisingfrom fixed-point implementations of dsp algorithms.the technique is based on recent interval representation methodsfrom affine arithmetic, and the use of new probabilisticbounds. the resulting numerical error estimates are comparableto detailed statistical simulation, but achieve speedupsof four to five orders of magnitude by avoiding actual bit-truesimulation. we show error analysis results on both feedforward and feedback dsp kernels.
simultaneous functional-unit binding and floorplanning. as device feature size decreases, interconnection delay becomes the dominating factor of system performance. thus it is important that accurate physical information is used during high level synthesis. in this paper, we consider the problem of simultaneously performing functional-unit binding and floorplanning. experimental results indicate that our approach to combine binding and floorplanning is superior to the traditional approach of separating the two tasks.
a hierarchical functional structuring and partitioning approach for multiple-fpga implementations. in this paper, we present a new synthesis and partitioning approach for multiple-fpga implementations from register-transfer-level (rtl) netlists. our approach bridges the gap between rtl/logic synthesis and physical partitioning by finely tuning logic implementations suited for multiple-fpga systems. we propose a hierarchical functional structuring and partitioning method which fully exploits the design structural hierarchy by decomposing rtl components into sets of logic sub-functions. this allows the partitioner to place portions of components into fpga partitions. experimental results on a number of benchmarks and industrial designs show that our approach achieves significant improvements in clb and io-pin utilizations of fpgas compared to that produced using a traditional multiple-fpga partitioning method.
hardware/software co-testing of embedded memories in complex socs. a novel approach for testing embedded memories in complexsystems-on-a-chip (socs) is presented. the proposedsolution aims to balance the usage of the existing on-chipresources and dedicated design for test (dft) hardwaresuch that the functional power constraints are not exceededduring test while trading-off the testing time againstdft area and performance overhead. the suitability ofsoftware-centric and hardware-centric approaches for embeddedmemory testing is examined and to combine the advantagesof both directions, a new built-in self-test (bist)-basedmethod, called hardware/software co-testing, is introduced.the proposed solution is programmable, scalableand guarantees low routing overhead.
local search for final placement in vlsi design. a new heuristic is presented for the general cell placement problem where the objective is to minimize total bounding box netlength. the heuristic is based on the guided local search (gls) metaheuristic. gls modifies the objective function in a constructive way to escape local minima. previous attempts to use local search on final (or detailed) placement problems have often failed as the neighborhood quickly becomes too excessive for large circuits. nevertheless, by combining gls with fast local search it is possible to focus the search on appropriate sub-neighborhoods, thus reducing the time complexity considerably.comprehensive computational experiments with the developed algorithm are reported on small, medium and large industrial circuits, and for standard cell and general cell variants of the problem. the experiments demonstrate that the developed algorithm is able to improve the estimated routing length of large-sized general cell layouts with as much as 20 percent.the general nature of the proposed method makes it easy to incorporate other goals, such as routability and timing constraints, into the objective function. current layout algorithms use a feedback approach in which a placement is evaluated by performing (partial) routing and timing analysis; the output of this analysis is then used to construct an improved placement. this iterative nature of the design process calls for placement algorithms that take an existing placement and construct an improved placement that resembles the original one, but in which the information from the routing/timing analysis is taken into account.
system partitioning to maximize sleep time. abstract: partitioning of a system to maximize exploitable sleep time for low-power synthesis is discussed. the motivation is to deactivate the memory refresh circuitry, apply power down or disable the clock signals during the inactive periods of operation of circuit elements, and thus minimize the power consumption. since it is impractical to have a separate set of control signals for each circuit element (otherwise, the control itself would consume a lot of power), it is advisable to partition a circuit based on the activity patterns of its elements so that the partitions can be switched into sleep mode for long periods of time. in this paper, we formulate this partitioning problem and show that it is np-hard. we present geo-part, a geometric partitioning heuristic for this problem. an efficient implementation of geo-part using segment tree data structure is discussed. experimental results are encouraging.
timing uncertainty analysis for time-of-flight systems. time-of-flight synchronization is a new digital design methodology that eliminates all latching devices, allowing higher clock rates than alternative timing schemes. synchronization is accomplished by precisely balancing connection delays. many effective pipeline stages are created by pipelining combinational logic, similar in concept to wave pipelining but differing in several respects. due to the unique flow-through nature of circuits and to the need for pulse-mode operation, time-of-flight design exposes interesting new areas for cad timing analysis. this paper discusses how static propagation delay uncertainty limits the clock period for time-of-flight circuits built with opto-electronic devices. we present algorithms for placing a minimum set of clock gates to restore timing in feedback loops that implement memory and for propagating delay uncertainty through a circuit graph. a mixed integer program determining the minimum feasible clock period subject to pulse width and arrival time constraints is discussed. algorithms are implemented in xhatch, a time-of-flight cad package.
sparse and efficient reduced order modeling of linear subcircuits with large number of terminals. in the process of designing state-of-the art vlsi circuit we often encounter large but highly structured linear subcircuits with large number of terminals. classical examples are power supply networks, clock distribution networks, large data buses, etc. various applications would benefit from efficient high level models of such networks. unfortunately the existing model-order-reduction algorithms are not adapted to handle more than a few tens of terminals. this talk introduces recmor, an algorithm for the computation of reduced order models of structured linear circuits with numerous i/o ports. the algorithm exploits certain regularities of the subcircuit response that are typical in numerous applications of interest. when these regularities are present, the normally dense matrix-transfer function of the subcircuit contains sub-blocks that in some sense are significantly low rank and can be compactly modeled by the recently introduced svdmor algorithm. the new recmor algorithm decomposes the large matrix-transfer function recursively, and applies svdmor compression adaptively to the sub-blocks of the transfer function. the result is a reduced order model that is sparse, efficient, and directly usable as an efficient substitute of the subcircuit in circuit simulations. the method is illustrated on several circuit examples.
automatic differentiation in circuit simulation and device modeling. automatic differentiation as a technique for accurate and reliable computation of partial derivatives in device models used by circuit simulation is introduced. the requirements for derivative computations in several simulation algorithms are reviewed, and two automatic differentiation methods are discussed. the application of automatic differentiation to circuit simulation and device modeling is demonstrated through several circuit analysis examples
computation of circuit waveform envelopes using an efficient, matrix-decomposed harmonic balance algorithm. in this paper we introduce a novel algorithm for numerically computing the "slow" dynamics (envelope) of circuits in which a "fast" varying carrier signal is also present. the algorithm proceeds at the rate of the slow behavior and its computational cost is fairly insensitive to the rate of the fast signals. the envelope computation problem is formulated as a differential-algebraic system of equations (daes) in terms of frequency-domain quantities (e.g. amplitudes and phases) that capture the fast varying behavior of the circuit. the solution of this dae represents the "slow" variation of these quantities, i.e., the envelope. the efficiency of this method is the result of using the most appropriate method for each of the circuit modes: harmonic balance for the fast behavior and time-domain integration of daes for the slow behavior. the paper describes the theoretical foundations of the algorithm and presents several circuit analysis examples.
measurement and modeling of mos transistor current mismatch in analog ic's. this paper presents a new methodology for measuring mos transistor current mismatch and a new transistor current mismatch model. the new methodology is based on extracting the mismatch information from a fully functional circuit rather than on probing individual devices; this extraction leads to more efficient and more accurate mismatch measurement. the new model characterizes the total mismatch as a sum of two components, one systematic and the other random. for our process, we attribute nearly half of the mismatch to the systematic component, which we model as a linear gradient across the die. furthermore, we present a new model for the random component of the mismatch which is 60% more accurate, on average, than existing models.
testing of analog systems using behavioral models and optimal experimental design techniques. this paper describes a new cad algorithm which performs automatic test pattern generation (atpg) for a general class of analog systems, namely those circuits which can be efficiently modeled as an additive combination of user-defined basis functions. the algorithm is based on the statistical technique of i-optimal experimental design, in which test vectors are chosen to be maximally independent so that circuit performance will be characterized as accurately as possible in the presence of measurement noise and model inaccuracies. this technique allows analog systems to be characterized more accurately and more efficiently, thereby significantly reducing system test time and hence total manufacturing cost.
hierarchical statistical characterization of mixed-signal circuits using behavioral modeling. a methodology for hierarchical statistical circuit characterization which does not rely upon circuit-level monte carlo simulation is presented. the methodology uses principal component analysis, response surface methodology, and statistics to directly calculate the statistical distributions of higher-level parameters from the distributions of lower-level parameters. we have used the methodology to characterize a folded cascode operational amplifier and a phase-locked loop. this methodology permits the statistical characterization of large analog and mixed-signal systems, many of which are extremely time-consuming or impossible to characterize using existing methods.
statistical verification of power grids considering process-induced leakage current variations. transistor threshold voltages (v{th}) have been reduced as partof on-going technology scaling. the smaller v{th} values featureincreased variations due to underlying process variations, witha strong within-die component. correspondingly, given the exponential dependence of leakage on v{th}, circuit leakage currentsare increasing significantly and have strong within-die statistical variations.with these leakage currents loading the powergrid, the grid develops correspondingly large statistical voltagedrops. this leakage-induced voltage drop is an unavoidable background level of noise on the grid. any additional non-leakagecurrents due to circuit activity will lead to voltage drop which isto be added to this background noise. we propose a techniquefor checking whether the statistical voltage drop on every node iswithin user-specified bounds, given user-specified statistics of theleakage currents.