Convexity-Based Algorithms for Design Centering

Sachin S. Sapatnekar, Pravin M. Vaidya, Sung Mo Kang

Research output: Contribution to journalArticlepeer-review

42 Scopus citations


A new technique for design centering and polytope approximation of the feasible region for a design are presented. In the first phase, the feasible region is approximated by a convex polytope, using a method based on a theorem on convex sets. As a natural consequence of this approach, a good approximation to the design center is obtained. In the next phase, the exact design center is estimated using one of two techniques that we present in this paper. The first inscribes the largest Hessian ellipsoid, which is known to be a good approximation to the shape of the polytope, within the polytope. This represents an improvement over previous methods, such as simplicial approximation, where a hypersphere or a crudely estimated ellipsoid is inscribed within the approximating polytope. However, when the probability density functions of the design parameteres are known, the design center does not necessaily correspond to the center of the largest inscribed ellipsoid. Hence, a second technique is developed that incorporates the probability distributions of the parameters, under the assumption that their variation is modeled by Gaussian probability distributions. The problem is formulated as a convex programming problem and an efficient algorithm is used to calculate the design center, using fast and efficient Monte Carlo methods to estimate the yield gradient. An example is provided to illustrate how ellipsoid-based methods fail to incorporate the probability density functions and is solved using the convex programming-based algorithm.

Original languageEnglish (US)
Pages (from-to)1536-1549
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Issue number12
StatePublished - Dec 1994

Bibliographical note

Funding Information:
Manuscript received August 12, 1992; revised July 12, 1994. This work was supported in part by the Joint Services Electronics Program under contract NO00 14-92-J-1270, the Illinois Technology Challenge Grant under contract SCCA-92-82 122, the Semiconductor Research Corporation under contmt SRC92-DP-109, and the National Science Foundation under contracts CCR-9057-481 and CCR-9007-195. This paper was recommended by Associate Editer J. White. S. S. Sapatnekar is with the Department of Electrical Engineering and Computer Engineering, Iowa State University, Ames, IA 5001 1 USA. P. M. Vaidya is with the Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA. S. M. Kang is with the Coordinated Science Laboratory and the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA. IEEE Log Number 9404897.


Dive into the research topics of 'Convexity-Based Algorithms for Design Centering'. Together they form a unique fingerprint.

Cite this