Logic optimization is an integral part of digital circuit design. It reduces design area and power consumption, and quite often improves circuit delay as well. Redundancy removal is a key step in logic optimization, in which redundant connections in the circuit are determined and replaced by constant values 0 or 1. The resulting circuit is simplified, resulting in area and power savings. In this paper, we describe a redundancy removal approach for combinational circuits based on a combination of logic simulation and SAT. We show that this approach can handle large industrial-strength designs in a reasonable amount of CPU time.

In modern design flows, technology-dependent logic optimizations consist of technology mapping and transformations applied after mapping. Advances have been made in technology mapping in the last decade. However, it is inherently an intractable problem and state-of-the-art algorithms produce suboptimal netlists in terms of area and timing. Also, during the design flow, when physical information becomes available, wire loads and net delays change the timing values at the gates. That presents opportunities for further timing and area optimization. This is accomplished by transforms such as gate sizing, gate replication, buffer optimization, restructuring and remapping, and pin permutation. In this paper, we survey algorithms for technology-dependent optimizations, along with a comparison of their relative power to optimize the netlist.

In this paper, an efficient framework is proposed to analyze the worst case of voltage variation of power network considering multidomain clock gating. First, a frequency-domain-based simulation method is proposed to obtain the time-domain voltage response. With the vector fitting technique, the frequency-domain responses are approximated by a partial fraction expression, which can be easily converted to a time-domain waveform. Then, an algorithm is proposed to find the worst-case voltage variation and corresponding clock gating patterns, through superimposing the voltage responses caused by all domains working separately. The major computation of the whole framework is solving the frequency-domain equation system, whose complexity is about$O(N^{\alpha}D\log f_{\max})$, where$\alpha$is between one and two if using an iterative solver from the PETSc library.$N$is the node number,$f_{\max}$is the upper bound of frequency, and$D$is the number of clock domains. Numerical results show that the proposed simulation method is up to several hundred times faster than commercial fast simulators, like HSPICE and MSPICE. In addition, the proposed method is able to analyze large-scale power networks that the commercial tools are not able to afford.

This paper proposes an efficient method to find the worst case of voltage violation by multi-domain clock gating in an on-chip power network. We first present a voltage response in an arbitrary multi-domain clock gating pattern, using a superposition technique. Then, an integer linear programming (ILP) formulation is proposed to identify the worst-case gating pattern and the maximum variation area. The ILP based method is significantly faster than a conventional method based on enumeration. The experimental results are also compared with a case where peak voltage variation is induced, which shows the latter technique largely underestimated the overall variation effect.

This paper proposes an efficient analysis flow and an algorithm to identify the worst case noise for power networks with multiple clock domains. First, we apply the Laplace transform on the input current sources to derive the analytical formula. Then, we calculate the circuit frequency response with logarithmic scale frequency components. The frequency domain response is approximated by a rational function using vector fitting modeling. The rational function is used to derive the natural frequency of the power ground networks, and can be converted back into time domain easily. Based on the analysis results, we then present the worst case clock gating pattern algorithm to analyze the power networks with multiple clock domains. The most expensive part of the proposed algorithm is the matrix solving: O(F(N) ldr log f ldr D). Function F is the complexity of iterative solution of complex matrix with dimension N. We assume that there are D clock domains and the frequency spans from 0 to f Hz. Experimental results show that our method is up to 60X faster than HSPICE, and can analyze large circuits which are not affordable by HSPICE.

Mesh architectures are used to distribute critical global signals on a chip, such as clock and power/ground. Redundancy created by mesh loops smooths out undesirable variations between signal nodes spatially distributed over the chip. However, one problem with the mesh architectures is the difficulty in accurately analyzing large instances. Furthermore, variations in process and temperature, supply noise and crosstalk noise cause uncertainty in the delay from clock source to flip-flops. In this paper, we study the problem of analyzing timing uncertainty in mesh-based clock architectures. We propose solutions for both pure mesh and (mesh + global-tree) architectures. The solutions can handle large design and mesh instances. The maximum error in uncertainty values reported by our solutions is 1-3ps with respect to the golden Monte Carlo simulations, which is at most 0.5% of the nominal clock latency of about 600ps

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.

Estimating interference from large digital blocks, and its effect on on-chip power-distribution networks, is extremely important in deep submicron digital and mixed-signal IC design, especially for systems-on-a-chip. In this paper, we present automated extraction techniques that can be used to generate families of small, time-varying macromodels of digital cell libraries from SPICE-level descriptions. Our automated digital aggressor macromodeling for interference noise (ADAMIN) approach is based on importing and adapting the time-varying Pade/spl acute/ method, for linear time-varying model reduction, from the mixed-signal macromodeling domain. Our approach features naturally higher accuracy than previous ones and, in addition, offers the user a tradeoff between accuracy and macromodel complexity. Extracted macromodels capture a variety of noise interference mechanisms, including IR and L(dI/dT) drops for power rails. Using ADAMIN as a core, it is expected that library-characterization methodologies will evolve to include extracted, accurate-by-construction interference noise macromodels for digital cell blocks. Experimental results indicate speedups of several orders of magnitude over full SPICE-level circuits, with prediction accuracies considerably superior to those from commonly-used current-source-based aggressor models.

Substrate noise (SN) is an important problem in mixed-signal designs. With increasing design complexity, it is not possible to simulate for SN with a detailed SPICE model that uses an accurate model for each transistor. In this paper, we propose a sensitivity analysis- and static timing analysis-based methodology to derive a reduced model that computes the worst case substrate noise in the design. The reduced model contains only passive components, which are very few, and is very quick to simulate. The main feature of our methodology is that, unlike previous approaches, it is independent of input patterns and does not need to simulate for millions of clock cycles. This lets us apply it to a full-chip design in reasonable CPU time. We validate our reduced model on several benchmark circuits against a detailed and highly accurate reference model. On average, the reduced model is within 16.4% of the reference model and is up to 38 times faster. Finally, we apply our methodology to a mixed-signal switch chip design consisting of 8 million gates and show that it finishes in 17 minutes.

Noise analysis and power distribution network reliability assessment is extremely important in deep sub-micron digital and mixed-signal circuit design. Both relate closely to the nonlinear loading impact of digital circuits. Consequently, accurate estimation of the latter is critical. In this paper, we present extraction techniques that automatically generate a family of small, time-varying macromodels for digital cell libraries, at the time of their library characterization. Our approach is based on importing and adapting the time-varying pade (TVP) method, for linear time-varying (LTV) model reduction, from the mixed-signal macromodelling domain. Our approach features naturally higher accuracy than previous ones, and in addition, offers the user a tradeoff between accuracy and macromodel complexity. A key attraction of our approach is that it can be merged into cell library extraction methodologies to produce accurate-by-construction noise models for digital blocks. Simulations and comparisons confirming the efficacy of our approach are provided.

This paper describes XTalkDelay, an industrial-strength methodology and tool for measuring the impact of crosstalk on delays of paths in a design. The main cornerstone of XTalkDelay methodology, vis-a-vis other approaches, is its high delay computation accuracy. It deliberately avoids the use of approximate models for cells and nets and interconnect reductions. XTalkDelay employs a path-based approach; uses detailed and accurately distributed RC parasitics for critical nets and their aggressors; uses BSIM3-accurate gate models; and invokes HSPICE for delay computation using only the minimum required set of input patterns. XTalkDelay has been successfully applied on two industrial designs.

In most libraries, gate parameters such as the pin-to-pin intrinsic delays, load-dependent coefficients, and input pin capacitances have different values for rising and falling signals. Most performance optimization algorithms, however, assume a single value for each parameter. It is known that under the load-independent delay model, the gate assignment (or resizing) problem is solvable in time polynomial in the circuit size when a single value is assumed for each parameter (Kukimoto et al., 1998). We show that, in the presence of different rise and fall parameter values, this problem is NP-complete even for chain and tree topology circuits under the simple load-independent delay model (Murgai, 1999). However, we also show that, for tree circuits, the problem is not NP-complete in the strong sense, and we propose a dynamic programming algorithm that solves it exactly in pseudopolynomial time. More specifically, we show that the problem can be solved in time proportional to the size of the circuit, the number of choices available in the library for each gate and the delay of the circuit. We also present a straightforward way of extending this algorithm to general directed acyclic networks. We present experimental results on a set of benchmark problems using a standard commercial library and show that our algorithm generates provably optimum delays for 69 out of 73 circuits. We also compare our technique with two approaches traditionally used to solve this problem in the industry and academia and show that it performs better than these two. Interestingly, both traditional approaches also yield delays that are, in general, not far from the optimum.

Fanout optimization is a fundamental problem in timing optimization. Most of the research has focused on the fanout optimization problem for a single net (or the local fanout optimization problem - LFO). The real goal, however, is to optimize the delay through the entire circuit by fanout optimization incurring minimum area penalty and without violating the pin loading constraints. This is known as the global fanout optimization (GFO) problem. In this paper, we show that the techniques proposed so far in the literature are either impractical or ineffective for large designs. We propose simple yet efficient and effective schemes for GFO and show that they outperform the "nearly-optimum" reverse topological (RT) algorithm [9] on large industrial designs. One of these schemes yields only 0.3% worse circuit delay on average, but incurs only 18.5% of the area penalty as compared to the RT algorithm and is about 3 times faster. A popularly used mincut-based strategy [7] was not found to be effective.

With the advent of deep sub-micron technologies, interconnect loads and delays are becoming significant, and layout-driven synthesis has become the need of the day. However, given the tight constraints imposed by the layout (e.g., area availability, congestion), only those synthesis transforms can be made layout-driven that are local and layout-friendly. Examples of such transforms are net buffering, gate resizing, and gate replication. In this paper, we address the problem of minimizing the delay of a mapped, roughly placed, and globally-routed design by buffer insertion and/or deletion without violating the local area constraints imposed by the layout and without overloading any buffer/cell pins. We believe that this is one of the most fundamental problems in layout-driven buffer optimization. To the best of our knowledge, no technique has been established to date that solves this problem. The concept of local (or block) area constraints we use in this paper is more powerful than that of the total design area traditionally used in logic synthesis.

In most libraries, gate parameters such as the pin-to-pin intrinsic delays, load-dependent coefficients, and input pin capacitances have different values for rising and falling signals. The performance optimization algorithms, however, assume a single value for each parameter. It is known that under the load-independent delay model, the gate assignment (or resizing) problem is solvable in time polynomial in the circuit size when a single value is assumed for each parameter. In the presence of different rise and fall parameter values, this problem was recently shown to be NP-complete even for chain and tree topology circuits under the simple load-independent delay model. In this paper, we propose it dynamic programming algorithm for solving this problem exactly in pseudo-polynomial time for tree circuits. More specifically, we show that the problem can be solved in time proportional to the size of the tree circuit, the number of choices available in the library for each gate, and the delay of the circuit. To the best of our knowledge, this is the first pseudo-polynomial exact algorithm for the gate assignment problem for trees in the presence of different rise and fall delays. We present a straightforward way of extending this algorithm to general directed acyclic graphs. We present experimental results on a set of benchmark problems using a standard commercial library and show that our algorithm generates provably optimum delays for 72 out of 76 circuits. We also compare our technique with two approaches traditionally used to solve this problem in the industry and academia and show that it is slightly better than these two. Interestingly, both traditional approaches also yield delays not far from the optimum.

Since busses take up a significant fraction of chip-area, the bus capacitances are often considerable, and the bus power may account for as much as 40% of the total power consumed on the chip. In applications where the integrity of data is not very important, data may be changed by 3 to 5% without losing too much information. One such application is that of a binary-encoded image, in which case the human eye cannot perceive the small change. However, these small changes can significantly reduce the number of transitions on the data bus and thus the power/energy consumed. We address the following problem: given a sequence of n k-bit data words and an error-tolerance e% (i,e., at most e% of the data bits are permitted to change), select the bits to be modified so that the total number of transitions is minimized. We show that a greedy strategy is not always optimum. We propose a linear-time dynamic programming based algorithm that generates an optimum solution to this problem. The experimental results for randomly generated data with a uniform distribution indicate that by changing e% data bits, the transitions can be reduced, on average, by 4e%.

Typically, cell parameters such as the pin-to-pin intrinsic delays, load-dependent coefficients, and input pin capacitances have different values for rising and falling signals. The performance optimization algorithms, however, assume a single value for each parameter. No work has been done to study the impact of separate rise and fall values on the complexity of optimization. We take the first step towards understanding this impact. We pick two problems that have polynomial-time complexities if a single value for each cell parameter is assumed. The first problem is that of buffer insertion on a fixed topology net to maximize the required time at the source of the net. The second is the gate resizing problem (and the more general technology mapping problem) for minimizing the circuit delay under the simplest, load-independent delay model. We show that under separate rise and fall parameters, both these problems become NP-complete. To the best of our knowledge, this is the first such result showing the effect of rise and fall parameters on the complexity of performance optimization problems. We then address the important question of devising a good practical algorithm for local fanout optimization.

Fanout optimization is a fundamental problem in timing optimization. Most of the research has focussed on the fanout optimization problem for a single net (or the local fanout optimization problem-LFO). The real goal, however, is to optimize the delay through the entire circuit by fanout optimization, This is the global fanout optimization (GFO) problem. H. Touati (1990) claims that visiting nets of the network in a reverse topological order (from primary outputs to inputs), applying the optimum LFO algorithm to each net, computing the new required time at the source and propagating the delay changes to the fanins yields a provably optimum solution to the GFO problem. This result implies that GFO is solvable in polynomial time if LFO is. We show that that is not the case. We prove that GFO is NP-complete even if there are a constant number of buffering choices at each net. We analyze Touati's result and point out the flaw in his argument. We then present sufficient conditions for the optimality of the reverse topological algorithm.

Recently, in [3], the following problem was addressed: Given a set of data words or messages to be transmitted over a bus such that the sequence (order) in which they are transmitted is irrelevant, determine the optimum sequence that minimizes the total number of transitions on the bus. In 1994, Stan and Burleson [5] presented the bus-invert method as a means of encoding words for reducing I/O power, in which a word may be inverted and then transmitted if doing so reduces the number of transitions. In this paper, we combine the two paradigms into one — that of sequencing words under the bus-invert scheme for the minimum transitions, i.e., words can be complemented, reordered and then transmitted. We prove that this problem DOPI — Data Ordering Problem with Inversion — is NP-complete. We present a polynomial-time approximation algorithm to solve DOPI that comes within a factor of 1.5 from the optimum. Experimental results show that, on average, the solutions generated by our algorithm were within 4.4% of the optimum, and that resequencing along with complementation leads to 34.4% reduction in switching activity.

Technology-independent timing optimization is an important problem in logic synthesis. Although many promising techniques have been proposed in the past, unfortunately they are quite slow and thus impractical for large networks. In this paper, we propose DEPART, a delay-based partitioner-cum-optimizer, which purports to solve this problem. Given a combinational logic network that is to be optimized for timing, DEPART divides it into sub-networks using timing information and a constraint on the maximum number of gates allowed in a single sub-network. These sub-networks are then dispatched, one by one, to a standard timing optimizer. The optimized sub-networks are re-glued, generating an optimized network. The challenge is how to partition the original network into sub-networks so that the final solution quality after partitioning and optimization is comparable to that from the timing optimizer. We propose a partitioning technique that is timing-driven and is simple yet effective. We compare DEPART with speed-up, a state-of-the-art timing optimization tool, and with various partitioning techniques such as min-cut based and region growing, on a suite of large industrial and ISCAS circuits. On more than half of the benchmarks, DEPART yields run-time improvements of 20 to 450 times over a normal invocation of speed-up (the overall average improvement being 8 times), without compromising the solution quality much. Min-cut and region growing partitioning schemes, not being timing-driven, perform poorly in terms of the final circuit delay.

Logic synthesis for look-up tables (LUTs) has received much attention in the past few years, since Xilinx introduced its LUT-based field-programmable gate array (FPGA) architectures. An m-input LUT can implement any Boolean function of up to m inputs. So the goal of synthesis for such architectures has been to synthesize a circuit in which each function can be implemented by one m-LUT such that either the total number of functions or the number of levels of the circuit is minimized. In this work, we focus on a different though related problem: synthesize the given circuit on a single memory or LUT L, which has a capacity of M bits. In addition to satisfying the memory constraint M, we also wish to minimize the total number of functions to be implemented. The main motivation for the problem comes from the problem of minimizing the simulation time on a hardware accelerator for logic simulation. This accelerator uses memory as a logic primitive. In fact, the problem is also relevant in the context of compile-code or software simulation. Another situation where the problem arises is in synthesis for the FPGA architectures being proposed that have on-chip memory for storing programs and data. The unused memory locations can be used to store logic functions. We show that the existing LUT synthesis methods are inadequate to solve this problem. We propose techniques to solve the problem and present experimental evidence to demonstrate their effectiveness.

In this paper, we revisit the classical problem of functional decomposition [1, 2] that arises so often in logic synthesis.One basic problem that has remained largely unaddressed to the best of our knowledge is that of decomposing a function such that the resulting sub-functions are simple, i.e., have small numberof cubes or literals.In this paper, we show h o w to solve this problem optimally.W e show that the problem is intimately related to the encoding problem, which is also of fundamental importance in sequential synthesis, especially state-machine synthesis.We formulate the optimum decomposition problem using encoding.In general, an input-output encoding formulation has to be employed.However, for eld-programmable gate array architectures that use look-up tables, the input encoding formulation suces, provided we use minimum-length codes.The last condition is really not a constraint, since each extra code bit means that an extra table has to be used (and that could be expensive).The unused codes are used as don't cares for simplifying the sub-functions.We compare the original implementation of functional decomposition, which ignores the encoding problem, with the new version that uses encoding while doing decomposition.We obtain an average improvement o f o v er 20% on a set of standard benchmarks for look-up table architectures.

Article Sequential synthesis for table look up programmable gate arrays Share on Authors: Rajeev Murgai View Profile , Robert K. Brayton View Profile , Albert Sangiovanni-Vincentelli View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 224–229https://doi.org/10.1145/157485.164681Online:01 July 1993Publication History 13citation184DownloadsMetricsTotal Citations13Total Downloads184Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Almost all mapping tools for programmable gate arrays (PGAs) start from a network optimized for the number of literals in the factored form. However, PGA architectures imposed different kinds of constraints on the synthesis process. For example, table look up (TLU) architectures restrict each function to at most m inputs (for a fixed m). This is unlike any type of constraint in PLA or standard-cell synthesis. Thus, standard cost functions like the number of cubes or factored form literals are not necessarily good complexity measures for TLU architectures. Decomposition and block count minimization are two steps in PGA mapping that are applied to an optimized design. In decomposition, a feasible representation of the network is obtained, which can be mapped directly onto the target architecture. Block count minimization then tries to maximally group the functions of the decomposed network into basic blocks such that the total number of blocks used are minimized. We address the problem of modeling the decompositon step, in optimization; in particular, we look at cube-packing, which has proved quite effective for the TLU architectures. We propose a technique for deriving a two-level representation of a logic function which yields better results after cube-packing. The technique rests on the idea of using the support of a set of primes as the basic object is two-level minimization, as opposed to a prime. Experiments indicate an average improvement of 12.5% over standard two-level methods.

We address the problem of determining the "complexity" of Boolean functions where complexity is measured as the minimum number of table look up blocks (TLUs) needed to implement a function. We present three new results. The first shows the exact value of the complexity of the class of (m+1)-input functions in terms of the TLUs with m inputs (m/spl ges/2). The next two derive upper bounds on the complexity, given some information about the representation of the function. One bound needs the number of literals and the number of cubes in a sum-of-products representation, and the other, the number of literals in a factored form. We compare these bounds with the results obtained by a TLU synthesis tool. On average, the factored form bounds are about 20% higher than the synthesized results, and hence are reasonable predictors of the number of TLUs needed. This prediction capability can be employed to quickly estimate, without performing any technology mapping, if a circuit can fit on one chip.>

The authors address the problem of clustering a circuit for minimizing its delay, subject to capacity constraints on the clusters. They present an algorithm for combinational circuits and give sufficient conditions under which it is optimum. In addition, they address the problem of minimizing the number of clusters and nodes without increasing the maximum delay found by the algorithm. Finally, they extend the clustering algorithm to minimize the clock cycle of a sequential synchronous circuit.>

The authors address the problem of synthesis for a popular class of programmable gate array architecture-the table look-up architectures. These use lookup table memories to implement logic functions. The authors present improved techniques for minimizing the number of table look up blocks used to implement a combinational circuit. On average, the results obtained on a set of benchmarks are 15-29% better than results obtained by previous approaches.>

The authors address the problem of delay optimization for programmable gate arrays. The main considerations are the number of levels in the circuit and the wiring delay. The authors propose a two-phase approach: the first phase involves delay optimizations during logic synthesis before placement, while the second uses logic resynthesis in the case of a timing-driven placement technique. Results and comparisons on benchmarks are presented.>

The problem of combinational logic synthesis is addressed for two interesting and popular classes of programmable gate array architectures: table-look-up and multiplexor-based. The constraints imposed by some of these architectures require new algorithms for minimization of the number of basic blocks of the target architecture, taking into account the wiring resources.

SLIP (system-level interactive partitioning), a framework for algorithms that partition and implement complex VLSI-based systems as a hierarchy of electronic packages, is described. SLIP provides a policy for representing hierarchical systems on the OCT data model as well as an attribute mechanism which is used to annotate the representation and to build models of the system. Modifications to the hierarchy are made with routines which maintain the consistency of both the data representation and the attributes.>