Convex optimization for digital integrated circuit applications

As digital integrated circuits continue to scale with Moore's law, and device dimensions shrink into the submicron regime, more and more transistors can be built into an embedded system, to perform operations at an unprecedented speed. This very large integration induces large process uncertainty and environmental variation, which cause large performance uncertainty in digital circuits. This performance uncertainty can be handled by many advanced design techniques, including statistical digital circuit sizing method. The very large integration and high performance also require very careful and efficient power and ground networks design since these networks can occupy significant fraction of the available wiring capacity and dissipate a considerable amount of power. This thesis concerns a statistical digital circuit sizing problem and a statistical design of power and ground networks. These problems are formulated as convex optimization problems and solved by heuristic methods based on convex optimization for very large-scale problems. The thesis also concerns generalized geometric programming, a class of convex optimization, which is used to solve the statistical digital circuit sizing problem.; The first topic concerns generalized geometric programming, which is extended from geometric programming. A geometric program (GP) can be solved very efficiently and globally even for a very large-scale problem. Since a generalized geometric program (GGP) can be transformed into an equivalent GP, a GGP can be readily solved very efficiently. Generalized geometric programming can be applied to a number of engineering application problems, and is used to solve the statistical digital circuit sizing problem discussed in the following topic.; The second topic concerns the statistical digital circuit sizing problem. An activity network optimization problem is studied since the digital circuit sizing problem can be formulated as an activity network optimization problem. To optimize a stochastic activity network (SAN) is extremely difficult (or intractable) whereas to optimize a deterministic activity network (DAN) is very easy. A heuristic method to optimize a SAN by solving a sequence of DAN optimization problems is developed and is applied to the statistical digital circuit sizing problem. This heuristic method indeed works very well for most digital circuits and handles the performance uncertainty problem very efficiently.; The third topic concerns statistical design of power and ground networks, which involves deciding on an optimal topology as well as optimal widths of the networks. This problem can be cast as a convex optimization problem, and so can be solved very efficiently and globally. The constant ratio reduction property of zero optimal widths is exploited to develop a heuristic method for very large-scale problems. This heuristic solves very large-scale problems efficiently.