A combined pairing and chaining algorithm for CMOS layout generation

Summary form only given. As CMOS VLSI circuits increment, their complexity and specifications become more aggressive, automatic layout generators gain popularity. These tools divide their task into a set of steps that include transistor pairing, chaining, sizing, placement of diffusion strips and routing. In each of these steps a high optimization degree is required in order to achieve good results. Usually, the transistors are placed in two parallel rows, one for the p- and one for the n-transistors. Transistors with the same gate connection are aligned vertically to reduce internal routing. Maintaining this constraint, a chaining algorithm should be able to find a minimum set of transistor chains in order to reduce the number of diffusion gaps, and hence, the overall area. Existing chaining algorithms try to find a minimal number of diffusion chains given a pre-fixed pairing. Therefore, pairs are fixed before the chains are generated, and the chain formation process cannot change those pairs. However, a different pairing can lead to a lower number of diffusion chains. Our main new feature is to combine the paring and chaining steps: the pairing disappears as a separate step and is dynamically generated during the chain formation process. In our approach, the set of all pairs of interest is generated. Not all pairs will be present in the final solution. The bipartite graph is extended to represent the new possible abutments. New incompatibilities must now be taken into account