This paper proposes a new formalism for layout-driven optimization of datapaths. It is based on preserving an arithmetic bit level representation of the arithmetic circuit portions throughout various design stages. The arithmetic bit level description takes into account the arithmetic nature of the datapath and facilitates arithmetic reasoning to identify circuit transformations that are too complex to derive for Boolean reasoning. It is a bit-level representation so that it integrates well into standard design flows. Based on this representation, we developed an optimization algorithm for cycle time. It takes interconnect delay into account and can be applied at late design stages. A prototype has been integrated into a commercial EDA environment. For circuits implementing complex arithmetic expressions we achieved performance improvements of up to 32%.

Summary form only given. In Magma's BlastFusion/spl reg/ and BlastChip/spl reg/ software, very large blocks of logic (millions of gates) are handled flat. We implemented redundancy removal in a way that will allow it to run efficiently (fast, low memory usage) and robustly (no run time or memory explosion on any netlist) on industrial designs of up to several million gates. We achieve this without resorting to partitioning. We do not try to identify all redundancies in a circuit, as an exact solution to this NP-hard problem is infeasible for the large circuits we face. Instead we try to identify as many as possible in a reasonable run time. We use a carefully engineered combination of Fault Collapsing, Random Test Generation (RTG) and the D-algorithm.

This paper is about gate sizing under a statistical delay model. It shows we can solve the gate sizing problem exactly for a given statistical delay model. The formulation used allows many different forms of objective functions, which could for example directly optimize the delay uncertainty at the circuit outputs. We formulate the gate sizing problem as a nonlinear programming problem, and show that if we do this carefully, we can solve these problems exactly for circuits up to a few thousand gates using the publicly available large scale nonlinear programming solver LANCELOT.

In this paper we introduce the first divide and conquer algorithm that is capable of exact hazard-free logic minimization in a constructive way. We compare our algorithm with the method of Dill and Nowick (1992), which was the only known method for exact hazard-free minimization. We show that our algorithm is much faster than the method proposed by Dill and Nowick by avoiding a significant part of the search space. We argue that the proposed algorithm is a promising framework for the development of efficient heuristic algorithms.

In this paper we consider the problem of finding minimum and minimal sum of product circuits (PLAs) that correctly implement a given set of transitions without any hazards. In earlier work we introduced an efficient divide and conquer algorithm, the threeway method, that is capable of finding a minimum PLA-implementation for single output functions. We showed that this method was 10 times faster than the exact method proposed by Dill/Nowick. In this paper we extend the threeway method such that it can deal with multiple output functions. We compare the enhanced threeway method again with Dill/Nowick's method. We also propose an efficient heuristic method, derived from the threeway method, that is capable of finding minimal implementations of specifications that cannot be minimized by the exact methods.

A new method is presented to compute the exact observability don't cares (ODCs) for multiple-level combinational circuits. A new mathematical concept, called polarization, is introduced. Polarization captures the essence of ODC calculation on the otherwise difficult points of reconvergence. It makes it possible to derive the ODC of a node from the ODCs of its fanouts with a very simple formula. Experimental results for the 39 largest MCNC benchmark examples show that the method is able to compute the ODC set (expressed as a Boolean network) for all but one circuit in at most a few seconds.

A new method is presented to compute the exact observability don't cares (ODC) for multilevel combinational circuits. A new mathematical concept, called polarization, is introduced. Polarization captures the essence of ODC calculation on the otherwise difficult points of reconvergence. It makes it possible to derive the ODC of a node from the ODCs of its fanouts with a very simple formula. Experimental results for the 39 largest MCNC benchmark examples show that the method is able to compute the ODC set (expressed as a Boolean network) for all but 1 circuit in at most a few seconds.

The gate sizing problem is the problem of finding load drive capabilities for all gates in a given Boolean network such, that a given delay limit is kept, and the necessary cost in terms of active area usage and/or power consumption is minimal. This paper describes a way to obtain the entire cost versus delay tradeoff curve of a combinational logic circuit in an efficient way. Every point on the resulting curve is the global optimum of the corresponding gate sizing problem. The problem is solved by mapping it onto piecewise linear models in such a way, that a piecewise linear (circuit) simulator can do the job. It is shown that this setup is very efficient, and can produce tradeoff curves for large circuits (thousands of gates) in a few minutes. Benchmark results for the entire set of MCNC '91 two-level examples are given.

This paper describes optimization techniques using don't-care conditions that span the domain of high-level and logic synthesis. The following three issues are discussed: (1) how to describe and extract don't-care conditions from high-level descriptions; (2) how to pass don't-care conditions from high-level to logic synthesis; and (3) how to optimize the logic using don't-care conditions. Efficient techniques are given for these three problems which allow the use of large don't-care sets. Results from several examples demonstrate that these techniques are very effective for both area and delay minimization.

This paper presents the mapping problem for pass transistor selector mapping, which has not been addressed before. Pass transistor synthesis is potentially important for semi- or full-custom design techniques, which are increasingly attracting attention. Pass transistors have the advantage that fewer transistors are needed, and that circuits with high fanin and small delay can be constructed. Technology mapping approaches in the existing literature cannot handle these selectors, due to the restriction of I-hot encoding of the control signals. We present a new algorithm to address this problem, which is based an the novel idea of a general Boolean Oracle. Our oracle is based on ATPG techniques, and compared to BDDs, the oracle has the advantage that failure to complete only affects optimization locally, and does not hinder optimization elsewhere in the logic. A limitation of BDDs is that it is difficult to complete the algorithm if a BDD grows too large. The experimental results show up to 82% improvement in transistor count for the MCNC combinatorial multi-level examples.

A novel approach to technology mapping that produces a standard-cell IC implementation from a previously optimized and decomposed set of Boolean functions is presented. Instead of trying to solve the problem for random libraries of standard cells, which proved to be very difficult, it has been solved for cell generators, which are only limited by technology constraints. The completeness of the sets of cells that can be generated by a cell generator, given a certain technology, makes it possible to use an elegant mapping algorithm. The algorithm was coded in CommonLISP, and used to map a large number of benchmark examples. The results compare favorably with published results.>