Folding or topological compaction of array-based VLSI layouts is an important optimization step that is carried out after logic synthesis. In this paper, a new approach to two-dimensional multiple folding of array-based VLSI layouts is presented. From the specification of the problem a pair of intersection graphs is created. We show that any pair of interval graphs that contain the intersection graphs as spanning subgraphs corresponds to a set of feasible foldings. Next, a complete and exact characterization of the folding problem is presented. In particular, it is shown that the set of all feasible foldings associated with a given pair of interval graphs corresponds to the set of independent colorings of a pair of compatibility graphs. The compatibility graphs are derived from a pair of interval graphs that contain the intersection graphs as spanning subgraphs. Thus, minimizing the area of a layout is tantamount to finding a pair of compatibility graphs such that the product of their chromatic numbers is minimum. As important as minimizing the area of a layout is, the ability to rapidly generate compact layouts over a wide range of aspect ratios is often equally, if not more, important. The interval graph-based formulation of the folding problem permits a controlled and systematic generation of compact layouts with varying aspect ratios. Efficient and provably correct algorithms to generate compact layouts that have a given number of rows or a given number of columns within their minimum and maximum possible values are given. The basic theory and methods are extended to include I/O and other types of constraints. Finally, the results of experiments that were carried out on a large number of benchmark problems are given. These results are compared with those obtained by previously reported methods.>

This paper describes a new layout style called the Flexible Transistor Matrix (FTM) for large scale CMOS module generation.FTM uses two layers of metal.Compared to Gate Matrix, FTM can generate significantly better results.In addition, the algorithm can control the aspect ratio, 1/0 pin positions and different transistor sizes.