Compaction on the Torus

A compacter takes as input a VLSI layout and produces as output an equivalent layout of smaller area. An effective compaction system frees the designer from the details of the design rules, and hence, increases his or her productivity and on the other hand produces high quality layouts. A general framework for compaction on a torus is introduced. This problem comes up whenever an array of identical cells has to compacted. The framework is instantiated by several specific compaction algorithms: one-dimensional compaction without and with automatic job insertion and two-dimensional compaction