VLSI layout compaction with conditional constraints

The authors attempt to find a compaction algorithm that can suitably handle conditional constraints, such that the area of the compacted layout can be smaller than that made by traditional compactors. While the algorithm has many potential applications, the focus is on its application to the compaction of multiple-layer routings. The constraints imposed by conditional constraints make the automatic compaction of layout much more difficult than when the usual minimum separation constraints are applied. To solve the problem, the authors first formulate each conditional spacing constraint with a set of arcs in the constraint graph representation. It is proven that finding the optimal solution in general cases is NP-complete. The authors then propose a heuristic algorithm of compaction which can efficiently obtain a good solution