waashk/dblp huggingface dataset:
an exact algorithm for the maximal sharing of partial terms in multiple constant multiplications. in this paper, we propose an exact algorithm that maximizes the sharing of partial terms in multiple constant multiplication (mcm) operations. we model this problem as a boolean network that covers all possible partial terms which may be used to generate the set of coefficients in the mcm instance. the pis to this network are shifted versions of the mcm input. an and gate represents an adder or a subtracter, i.e., an and gate generates a new partial term. all partial terms that have the same numerical value are ored together. there is a single output which is an /spl and/ over all the coefficients in the mcm. we cast this problem into a 0-1 integer linear programming (ilp) problem by requiring that the output is asserted while minimizing the total number of and gates that evaluate to one. a sat-based solver is used to obtain the exact solution. we argue that for many real problems the size of the problem is within the capabilities of current sat solvers. we present results using binary, csd and msd representations. two main conclusions can be drawn from the results. one is that, in many cases, existing heuristics perform well, computing the best solution, or one close to it. the other is that the flexibility of the msd representation does not have a significant impact in the solution obtained.
global signaling over lossy transmission lines. we describe an interconnect scheme based on lossy transmission lines, compare this scheme with traditional bus based links, and present performance data. unlike some other schemes there is no requirement for up-conversion, equalization, or special metal processing. in preliminary work, we have measured data rates of 14 gbps (limited by test equipment) over a 7.2 mm interconnection, implemented in 0.18 /spl mu/m cmos. for active links signaling over a single serial link, is more power efficient than over traditional parallel buses, does not require repeaters and is less affected by noise and coupling.
a tutorial on logic synthesis for lookup-table based fpgas. discusses combinational logic synthesis for fpgas that use lookup tables (luts). issues that differentiate lut synthesis from conventional logic synthesis are emphasized. the ability of a k-input lut to implement any boolean function of k variables differentiates the synthesis of lut circuits from that for conventional asic technologies. the major different occurs during the technology mapping phase of logic synthesis. for values of k greater than 3, the larger number of functions that can be implemented by a k-input lut makes it impractical to use a conventional library-based technology mapping. however, the completeness of the set of functions that can be implemented by a lut eliminates the need for a library of separate functions. in addition, this completeness can be leveraged to optimize the final circuit
daisy: a simulation-based high-level synthesis tool for delta-sigma modulators. an integrated tool called daisy (delta-sigma analysis and synthesis) is presented for the high-level synthesis of &delta;&sigma; modulators. the approach determines both the optimum modulator topology and the required building block specifications, such that the system specifications -- mainly accuracy and signal bandwidth -- are satisfied at the lowest possible power consumption. a genetic-based differential evolution algorithm is used in combination with a fast dedicated behavioral simulator that includes the major nonidealities of the building blocks to realistically analyze and optimize the modulator performance. experimental results illustrate the effectiveness of the approach. also, an overview of optimized topologies as a function of the modulator specifications for a wide range of values shows the capabilities and performance range covered by the tool.
sprim: structure-preserving reduced-order interconnect macromodeling. in recent years, order-reduction techniques based on krylov subspaces have become the methods of choice for generating macromodels of large multi-port rlc circuits. a widely-used method of this type is prima. its main features are provably passive reduced-order models and a moment-matching property. on the other hand, prima does not preserve other structures, such as reciprocity or the block structure of the circuit matrices, inherent to rlc circuits, which makes it harder to synthesize the prima models as actual circuits. moreover, the prima models match only half as many moments as optimal, but non-passive, moment-matching techniques such as sympvl. in this paper, we propose the reduction technique sprim that overcomes these disadvantages of prima. in particular, sprim generates provably passive and reciprocal macromodels of multi-port rlc circuits, and the sprim models match twice as many moments as the corresponding prima models obtained with identical computational work. numerical results are reported that illustrate the higher accuracy of sprim vs. prima.
efficient small-signal circuit analysis and sensitivity computations with the pvl algorithm. we describe the application of the pvl algorithm to the small-signal analysis of circuits, including sensitivity computations. the pvl algorithm is based on the efficient computation of the pade&acute; approximation of the network transfer function via the lanczos process. the numerical stability of the algorithm permits the accurate computation of the pade&acute; approximation over any given frequency range. we extend the algorithm to compute sensitivities of network transfer functions, their poles, and zeros, with respect to arbitrary circuit parameters, with minimal additional computational cost, and we present numerical examples.
reduced-order modeling of large passive linear circuits by means of the sypvl algorithm. lucent technologiesthis paper discusses the analysis of large linear electrical networks consisting of passive components, such as resistors, capacitors, inductors, and transformers. such networks admit a symmetric formulation of their circuit equations. we introduce sypvl, an efficient and numerically stable algorithm for the computation of reduced-order models of large, linear, passive networks. sypvl represents the specialization of the more general pvl algorithm, to symmetric problems. besides the gain in efficiency over pvl, sypvl also preserves the symmetry of the problem, and, as a consequence, can often guarantee the stability of the resulting reduced-order models. moreover, these reduced-order models can be synthesized as actual physical circuits, thus facilitating compatibility with existing analysis tools. the application of sypvl is illustrated with two interconnect-analysis examples.
symbolic hazard-free minimization and encoding of asynchronous finite state machines. this paper presents an automated method for the synthesis of multiple-input-change (mic) asynchronous state machines. asynchronous state machine design is subtle since, unlike synchronous synthesis, logic must be implemented without hazards, and state codes must be chosen carefully to avoid critical races. we formulate and solve an optimal hazard-free and critical race-free encoding problem for a class of mic asynchronous state machines called burst-mode. analogous to a paradigm successfully used for the optimal encoding of synchronous machines, the problem is formulated as an input encoding problem. implementations are targeted to sum-of-product realizations. we believe this is the first general method for the optimal encoding of hazard-free mic asynchronous state machines under a generalized fundamental mode of operation. results indicate that improved solutions are produced, ranging up to 17% improvement.
optimist: state minimization for optimal 2-level logic implementation. we present a novel method for state minimization of incompletely-specified finite state machines. where classic methods simply minimize the number of states, ours directly addresses the implementation's logic complexity, and produces an exactly optimal implementation under input encoding. the method incorporates optimal ``state mapping'', i.e., the process of reducing the symbolic next-state relation which results from state splitting to an optimal conforming symbolic function. further, it offers a number of convenient sites for applying heuristics to reduce time and space complexity, and is amenable to implementation based on implicit representations. although our method currently makes use of an input encoding model, we believe it can be extended smoothly to encompass output encoding as well.
optimista: state minimization of asynchronous fsms for optimum output logic. the optimal state minimization problem is to select a reduced state machine having the best logic implementation over all possible state reductions and encodings. a recent algorithm, optimist [3], was the first general solution to this problem for synchronous fsms. in this paper, we present the first solution for asynchronous fsms.this paper makes two contributions. first, we introduce optimista, a new algorithm which guarantees optimum 2-level output logic for asynchronous fsms. in asynchronous machines, output logic is often critical: it usually determines the machine latency. the algorithm is formulated as a binate constraint satisfaction problem, which is solved using a binate solver. the second contribution is a novel alternative result: the unreduced machine itself can be used directly to obtain minimum-cardinality output logic.thus, this paper presents two approaches: using optimista, which simultaneously performs state and logic minimization; or using no state reduction (if output logic cardinality is of sole interest). extensions for literal optimization, targetted to multi-level logic, are also proposed.
simultaneous short-path and long-path timing optimization for fpgas. this work presents the routing cost valleys (rcv) algorithm - the first published algorithm that simultaneously optimizes all short- and long-path timing constraints in a field-programmable gate array (fpga). rcv is comprised of a new slack allocation algorithm that produces both minimum and maximum delay budgets for each circuit connection, and a new router that strives to meet and, if possible, surpass these connection delay constraints. rcv achieves excellent results. on a set of 100 large circuits, rcv improves both long-path and short-path timing slack significantly vs. an earlier computer-aided design (cad) system that focuses solely on long-path timing. even with no short-path timing constraints, rcv improves the clock speed of circuits by 3.9% on average. finally, rcv is able to meet timing on all 72 peripheral component interconnect (pci) cores tested, while an earlier algorithm fails to achieve timing on all 72 cores.
model reduction for dc solution of large nonlinear circuits. a new algorithm based on model reduction using krylov subspace technique is proposed to compute the dc solution of large nonlinear circuits. the proposed method combines continuation methods with model reduction techniques. thus it enables the application of the continuation methods to an equivalent reduced-order set of nonlinear equations instead of the original system. this results in a significant reduction in the computational expense as the size of the reduced equations is much less than that of the original system.the reduced order system is obtained by projecting the set of nonlinear equations, whose solution represents the dc operating point, into a subspace of a much lower dimension. it is also shown that the both the reduced-order system and the original system share the first q derivatives w.r.t. the circuit variable used to parameterize the family of the solution trajectories generated by the continuation method.
timing distribution in vhdl behavioral models. a cad tool, timespec, developed for solving the timing distribution problem of allocating realistic delays to the internal primitives (rtl models) of a digital device by using the linear programming approach is described. the inconsistencies in the manufacturer's specifications are also detected and corrected. timespec allows the use of embedded timing in behavioral vhdl models, and thus the end-to-end delays for all paths in the digital device are made available. an interface is provided with an x windows based graphical tool, the modeler's assistant, which allows enumeration of all the input-to-output paths in the device. thus a cad tool is made available to system or chip designers/modelers for building accurate and synthesizable vhdl models
efficient sat-based unbounded symbolic model checking using circuit cofactoring. we describe an efficient approach for sat-based quantifier elimination that significantly improves the performance of pre-image and fixed-point computation in sat-based unbounded symbolic model checking (umc). the proposed method captures a larger set of new states per sat-based enumeration step during quantifier elimination, in comparison to previous approaches. the novelty of our approach is in the use of circuit-based cofactoring to capture a large set of states, and in the use of a functional hashing based simplified circuit graph to represent the captured states. we also propose a number of heuristics to further enlarge the state set represented per enumeration, thereby reducing the number of enumeration steps. we have implemented our techniques in a sat-based umc framework where we show the effectiveness of sat-based existential quantification on public benchmarks, and on a number of large industry designs that were hard to model check using purely bdd-based techniques. we show several orders of improvement in time and space using our approach over previous cnf-based approaches. we also present controlled experiments to demonstrate the role of several heuristics proposed in the paper. importantly, we were able to prove using our method the correctness of a safety property in an industry design that could not be proved using other known approaches.
clock distribution design and verification for powerpc microprocessors. with the increase of clock speeds, clock skew has become a significant part of the cycle time of high speed microprocessors. while many clocktree routing techniques promise zero or minimal skew, algorithm assumptions or our design methodology constraints often prevent a single approach from being suitable for the entire clock design. in this paper we describe a collection of strategies that are applied at various levels of design to yield clock distribution networks of acceptable skew for the two different clock design styles used by powerpc processors. we also describe a static timing based approach for analyzing the clock network to detect the various clock violations of interest.
exact and heuristic approaches to input vector control for leakage power reduction. we present two approaches to leakage power minimization in static cmos circuits by means of input vector control (ivc). we model leakage effects using pseudo-boolean functions. these are incorporated into an optimal integer linear programming model called vg-ilp that analyzes leakage variation with respect to a circuit's input vectors. a heuristic mixed-integer linear programming (mlp) method is also presented which has several advantages: it is faster, its accuracy can be quickly estimated, and trade-offs between runtime and optimality can easily be made. the proposed methods are used to generate a large set of experimental results on leakage reduction. it is shown that average leakage currents are usually 1.25 times the minimum, confirming the effectiveness of ivc. the heuristic mlp approach is much faster than exact ilp, while finding input vectors whose power consumption is only a few percent from the optimum.
minimum crosstalk switchbox routing. as technology advances, interconnection wires are placed in closer proximity. consequently, reduction of crosstalks between interconnection wires becomes an important consideration in vlsi design. in this paper, we study the gridded switchbox routing problems with the objectives of satisfying crosstalk constraints and minimizing the total crosstalk in the nets. we propose a new approach to the problems which utilizes existing switchbox routing algorithms and improves upon the routing results by re-assigning the horizontal and vertical wire segments to rows and columns, respectively, in an interative fashion. this approach can also be applied to the channel routing problem with crosstalk constraints. a novel mixed ilp formulation and effective procedures for reducing the number of variables and constraints in the mixed ilp formulation are then presented. the experimental results are encouraging.
optimal shape function for a bi-directional wire under elmore delay model. in this paper, we determine the optimal shape function for a bi-directional wire under the elmore delay model. given a bi-directional wire of length l, let f(x) be the width of the wire at position x, 0\leq x \leq l. let t_{dr} be the right-to-left delay. let t_{dl} be the left-to-right delay. let t_{bd}=\alpha t_{dr}+\beta t_{dl} be the total weighted delay where \alpha\geq 0 and \beta\geq 0 are given weights such that \alpha+\beta=1. we determine f(x) so that t_{bd} is minimized. our study shows that, if \alpha=\beta, the optimal shape function is f(x)=c, for some constant c; if \alpha\neq \beta, the optimal shape function can be expressed in terms of the lambert's w function as f(x)=-\frac{c_f}{2c_0}(\frac{1}{w(-ae^{-bx})}+1), where c_f is the unit length fringing capacitance, c_0 is the unit area capacitance, a and b are constants in terms of the given circuit parameters. if \alpha=0 or \beta=0, our result gives the optimal shape function for a uni-directional wire.
simultaneous analytic area and power optimization for repeater insertion. we present an analytic formula for repeater insertion in globalinterconnects that simultaneously minimizes silicon device areaand power dissipation for a given performance ¿{crit}/k where ¿{crit}is the minimum possible delay along a global interconnect, withrepeaters inserted, and 0
library-less synthesis for static cmos combinational logic circuits. traditional synthesis techniques optimize cmos circuits in two phases: i) logic minimization and ii) library mapping phase. typically, the structures and the sizes of the gates in the library are chosen to yield good synthesis results over many blocks or even for an entire chip. consequently this approach precludes an optimal design of individual blocks which may need custom structures. the authors present a new transistor level technique that optimizes cmos circuits both structurally and size-wise. the technique is independent of a library and hence can explore a design space much larger than that possible due to gate level optimization. results demonstrate a significant improvement in circuit performance of the resynthesized circuits.
optimal synthesis of multichip architectures. a global optimization approach to high level synthesis of vlsi multichip architectures is presented. optimal application-specific architectures are synthesized to minimize latency given constraints on chip area, i/o pin count and interchip communication delays. a mathematical integer programming (ip) model for simultaneously partitioning, scheduling, and allocating hardware (functional units, i/o pins, and interchip buses) is formulated. by exploiting the problem structure (using polyhedral theory), the size of the search space is decreased and a new variable selection strategy is introduced based on the branch and bound algorithm. multichip optimal architectures for several examples are synthesized in practical cpu times. execution times are comparable to those for previous heuristic approaches. there are, however, significant improvements in optimal schedules and allocations of multichips
dsp address optimization using a minimum cost circulation technique. this paper presents a new approach to solving the dsp address assignment problem. a minimum cost circulation approach is used to efficiently generate high performance addressing code in polynomial time. addressing code size improvements of up to 7 times are obtained, accounting for up to 1.6 times improvement in code size and performance of compiler-generated dsp code. results also show that memory layout has a small effect on code size and performance when optimal addressing is used. this research is important for industry since this value-added technique can improve code size, power dissipation and performance, without increasing cost.
transform domain techniques for efficient extraction of substrate parasitics. a semi-analytical technique for computation of the frequency- behavior of silicon substrates is demonstrated. the technique uses a boundary element approach, that utilizes the complex substrate green function and the two-dimensional fast fourier transform. the resultant dense system matrix is sparsified by application of orthogonal transform operators on the matrix representing the system. three transform operators are evaluated for this purpose - the discrete cosine transform (dct), the discrete wavelet transform (dwt) and the discrete hadamard transform (dht). the application of any one of these operators provides a rigorous sparsification technique, which significantly reduces the computation time. the green function is computed in the two layers at the top of the substrate. this is done so that contacts in the oxide layer can be included in the substrate model, along with contacts in the silicon substrate. hence, substrate loss terms in metal interconnect lines and in line-to- line interaction models, can be evaluated using this technique. extraction of a simple circuit-simulator compatible model from frequency-domain data is discussed.
analyzing software influences on substrate noise: an adc perspective. substrate noise affects the performance of mixed signal integrated circuits. power supply (di/dt) noise is the dominant source of substrate noise. there have been various attempts at the circuit and software levels to estimate this noise. software-level noise estimation is especially important, as designing noise tolerant circuits for all circumstances may be prohibitively expensive. in this paper, we propose a new software approach for estimating di/dt noise and incorporate it into a power simulator in order to investigate the influence of software on substrate noise. as a case study, we investigate how an analog-to-digital converter (adc) can be designed to adapt its resolution in the presence of substrate noise generated by a embedded processor core. the proposed strategies prevent unexpected adc performance degradations.
a unified theory of timing budget management. this work presents a theoretical framework that optimally solves many open problems in time budgeting. our approach unifies a large class of existing time-management paradigms. examples include time budgeting for maximizing total weighted delay relaxation, minimizing the maximum relaxation and min-skew time budget distribution. we show that many of the time management problems can be transformed into a min-cost flow instance that can be optimally and efficiently solved through well-known combinatorial techniques. experiments include mapping of several designs, which are implemented using parameterized coregen ip cores, on xilinx fpga devices. different time budgeting policies have been applied during the mapping stage. our time management techniques always improved the area requirement of the implemented testbenches compared to a widely-used path-based method. we also compared the maximum budgeting and fairness in delay budget assignments. our experimental results show that an average improvement of 19% in area can be achieved when fairness and maximum budgeting policies are combined, compared to pure maximum budgeting.