The complexity of compacting hierarchically specified layouts of integrated circuits

Abstract

In many CAD systems for VLSI design the specification of a layout is internally represented by a set of geometric constraints that take the form of linear inequalities between pairs of layout components. Some of the constraints may be explicitly stated by the circuit designer. Others are internally generated by the CAD system, using the design rules of the fabrication process. Layout compaction is then equivalent to finding a minimum area layout satisfying all constraints. We discuss the complexity of the constraint resolution problem arising in this context. Hereby we allow circuits to be specified hierarchically. The complexity of the constraint resolution is then measured in terms of the length of the hierarchical specification. We show the following results: 1. It is decidable in polynomial (cubic) time whether a given hierarchical layout specification yields a consistent set of geometric constraints. The size of minimum area layouts satisfying the constraints can also be determined in cubic time. 2. For every layout specification that is consistent a hierarchical description L of a minimum area layout can be computed in polynomial time in the length of L. 3. There is a consistent layout specification with the following property: No layout satisfying the constraints is concise, i.e., every hierarchical layout description consistent with the specification has a length which grows exponentially in the length of the specification. 4. We define a subclass of so-called well-formed layout specifications. Each well-formed specification has a concise layout, which can be hierarchically described in linear space. Such a layout can be found in polynomial time. However, it is in general not a minimum area layout. Indeed, there is a consistent well-formed specification all of whose minimum area layouts are inconcise,.i.e., need exponential space to be described.