We consider representations of general nonoverlapping placements of rectangles by spatial relations (west, south, east, north) of pairs of rectangles. We call a set of representations complete if it contains a representation of every placement of $n$ rectangles. We prove a new upper bound of $\mathcal{O}(\frac{n!}{n^6} \cdot (\frac{11+5 \sqrt 5}{2})^n)$ and a new lower bound of $\Omega(\frac{n!}{n^4} \cdot (4 + 2 \sqrt2)^n)$ on the minimum cardinality of complete sets of representations. A key concept in the proofs of these results are pattern-avoiding permutations. The new upper bound directly improves upon the well-known sequence pair representation, which has size $(n!)^2$, by only considering a restricted set of sequence pairs. It implies theoretically faster algorithms for VLSI placement problems.

Multipatterning technology used in 7-nm technology and beyond imposes more and more complex design rules on the layout of cells. The often nonlocal nature of these new design rules is a great challenge not only for human designers but also for existing algorithms. We present a new flow for automatic cell layout generation that is able to deal with these challenges by globally optimizing several design objectives simultaneously. Our transistor placement algorithm not only minimizes the total cell area but at the same time guarantees the routability of the cell and finds a best arrangement and folding of the transistors. Our routing engine computes a detailed routing of all nets simultaneously. It computes a netlength optimal routing using a mixed-integer programming formulation. Additional DFM constraints are added to this model to improve yield and reduce chip manufacturing costs. We present experimental results on current 7-nm designs. Our approach allows to compute optimized layouts within a few minutes, even for large complex cells. The algorithms are used for the design of logic cells compatible with a published 7-nm technology from a leading chip manufacturer where they meet manufacturability requirements and significantly reduced design turn around times.

Multi patterning technology used in 7nm technology and beyond imposes more and more complex design rules on the layout of cells. The often non local nature of these new design rules is a great challenge not only for human designers but also for existing algorithms. We present a new flow for the automatic cell layout that is able to deal with these challenges by globally optimizing several design objectives simultaneously. Our transistor placement algorithm not only minimizes the total cell area but simultaneously optimizes the routability of the cell and finds a best folding of the transistors. Our routing engine computes a detailed routing of all nets simultaneously. In a first step it computes an electrically correct routing using a mixed integer programming formulation. To improve yield and optimize DFM, additional constraints are added to this model.