Algorithms for optimizing, two-dimensional symbolic layout compaction

A set of algorithms that implement a technique called Supercompaction is described for two-dimensional compaction layouts. The algorithms minimize a one-dimensional objective function (pitch) by moving objects in the layout in two dimensions. The objective function can be monotonically reduced to a locally minimal value, greatly simplifying search. The algorithms can change the layout by simple motion of components or by automatic jog introduction. Experiments shows that: (1) the number of iterations required to reach a locally optimal layout is very small; (2) the time per iteration is competitive with other compaction techniques; (3) supercompacted layouts are smaller in pitch and area than those produced by existing one-dimensional algorithms; and (4) the results of supercompaction are more predictable than those of existing one-dimensional methods