An Efficient Algorithm for Some Multirow Layout Problems

Abstract

Automatic generation of standard CMOS logic cells has been studied intensively during the last decade. Some maturity has been achieved, and several commercial tools are available. The continuous progress in VLSI technology presents new challenges in developing efficient algorithms for the layout of standard CMOS logic cells and in combining them within functional macros. In this paper, three multirow layout problems are presented: transistor orientation, contact positioning and symbolic-to-shape translation. It is shown that these multirow problems have a common property, which we call quantitative dependency. Using this property, an optimization technique is presented, which is based on a penalty-delay strategy. It is proved that the penalty-delay strategy assures optimality, and that the optimal solution can be obtained in linear time. The algorithmic approach is based on the observation that optimal layout decisions in any region within a cell or a macro depend only on quantitative measures of the decisions in other regions, rather than on their details. This suggests to depart from the traditional approach of handling the different regions separately and combining them afterward into a single unit, an approach that may degrade the quality of the final layout. Instead, the entire macro can be processed at once, taking into account the mutual quantitative dependency between distinguished regions. © 1993 IEEE