INTERVAL GRAPH ALGORITHMS FOR 2-DIMENSIONAL MULTIPLE FOLDING OF ARRAY-BASED VLSI LAYOUTS

Folding or topological compaction of array-based VLSI layouts is an im portant optimization step that is carried out after logic synthesis. I n this paper, a new approach to two-dimensional multiple folding of ar ray-based VLSI layouts is presented. From the specification of the pro blem a pair of intersection graphs is created. We show that any pair o f interval graphs that contain the intersection graphs as spanning sub graphs corresponds to a set of feasible foldings. Next, a complete and exact characterization of the folding problem is presented. In partic ular, it is shown that the set of all feasible foldings associated wit h a given pair of interval graphs corresponds to the set of independen t colorings of a pair of compatibility graphs. The compatibility graph s are derived from a pair of interval graphs that contain the intersec tion graphs as spanning subgraphs. Thus, minimizing the area of a layo ut is tantamount to finding a pair of compatibility graphs such that t he product of their chromatic numbers is minimum. As important as mini mizing the area of a layout is, the ability to rapidly generate compac t layouts over a wide range of aspect ratios is often equally, if not more, important. The interval graph-based formulation of the folding p roblem permits a controlled and systematic generation of compact layou ts with varying aspect ratios. Efficient and provably correct algorith ms to generate compact layouts that have a given number of rows or a g iven number of columns within their minimum and maximum possible value s are given. The basic theory and methods are extended to include I/O and other types of constraints. Finally, the results of experiments th at were carried out on a large number of benchmark problems are given. These results are compared with those obtained by previously reported methods.