Due to deep sub micron effects, accurate gate sizing is increasingly important. Most advanced methods for sizing assume that gates can be sized continuously, while most design is done with discrete gate array and standard cell libraries. To bridge this gap, this paper proposes a new approach to gate sizing which combines a small number of discrete gate sizes to approximate the ideal of continuous sizing. To date research has focussed on deciding an appropriate set of logic functions for the primitive gates in a library. The main contribution of this paper is the development of a theoretical framework for strategies of drive strength selection for libraries. We demonstrate that nearly continuous sizing can be achieved by combining gates of a small number of sizes. The experimental procedure is based on simulated annealing. The results show that with only 5 discrete sizes any continuous size within a range of two orders of magnitude can be approximated with an accuracy of 1.7%.

Gate sizing consists of choosing for each n o d e o f a mapped network a gate implementation in the library so that some cost function is optimized under some constraints.It has a signi cant impact on the delay, power dissipation, and area of the nal circuit.This paper compares ve gate sizing algorithms targeting discrete, non-linear, non-unimodal, constrained optimization.The goal is to overcome the non-linearity and nonunimodality of the delay and the power to achieve good quality results within a reasonable CPU time, e.g., handling a 10000 node network in 2 hours.We compare the ve algorithms on constraint free delay optimization and delay constrained power optimization, and show that one method is superior to the others.

Research on synthesis for low power has been done in all three stages of logic synthesis: technology independent optimization, technology mapping, and technology dependent optimization. This paper presents an integrated method, using remapping and technology dependent optimizations, to minimize the power of a mapped circuit under the given delay constraints. It produces 24% savings in power.

Integrated circuit design has principally focused on achieving performance goals (e.g., speed) with minimal cost (e.g., area) using as little design time as possible. To help designers achieve these goals computer-aided design tools have traditionally focused on tools which improve performance, reduce area, and improve productivity. In the beginning of this decade, a new design concern began to surface. Motivated by the desire to differentiate products by longer battery life, designers of integrated circuits for portable products began to be worried about the power consumption of their electronics. Moreover, as the decade progressed and smaller processing geometries appeared on the horizon, the problem of packing millions of transistors into a cost-effective plastic package emerged. Finally, product reliability added a third motivation to address the issue of power dissipation. As we approach the end of the decade, it appears that power dissipation will eclipse area as a design concern for many integrated circuits. In response to this, the electronic-design automation industry is beginning to produce products which aid in the reduction of power dissipation of integrated circuits. This paper aims to review the state-of-the-art of commercial tools for reducing power dissipation.

The problem of determining whether a redundant random-access memory (RRAM) containing faulty memory cells can be repaired with spare rows and columns is discussed. The approach is to increase the number of working RRAMs manufactured per unit time, rather than per wafer, by presenting a computationally efficient algorithm for detecting unrepairability, a computationally efficient algorithm for optimal repair for special patterns of faulty memory cells and online algorithms that can find an optimal repair or else detect unrepairability during memory testing, aborting unnecessary testing. Experimental validation of the approach is given that is based on industrial device fabrication data.>

Cartesian-factorable extensions and subgraphs of prime graphs are investigated. It is shown that minimal factorable extensions and maximal factorable subgraphs are not unique and that finding them is NP-hard even, in the case of minimal factorable extensions, if the prime graph in question is required to be a tree. Tight bounds on the density of a prime graph’s minimal factorable extension are derived. A dynamic programming algorithm is given for finding factorable extensions of certain types of trees.

In this paper we consider selections of the form “column = constant” on relations defined by linear recursive, two rule datalog programs. In general, counting methods perform well on such queries. However, counting methods fail in the presence of cycles in the database. We present an algorithm in the spirit of counting methods that correctly deals with cyclic data and has the same asymptotic running time as counting methods. The algorithm, which is based on reducing a query on a database to a question about intersections of semi-linear sets, works by using efficient methods to construct the appropriate semi-linear sets from the database and query constant.

Mehlhorn and Schmidt [Discrete Appl. Math., 15 (1986), pp. 315–327 ] consider the following problem. Given a directed graph with distinguished source vertex s, is it possible to order the edges so that all simple paths starting at s use edges in increasing order? They show how to solve their problem in $O( | E |^2 )$ steps, where $| E |$ is the number of edges. An algorithm that runs in $O( | V |^2 )$ steps is given, where $| V |$ is the number of vertices. The new algorithm and its analysis apply and extend previous results on dominators in directed graphs.