Layout compaction algorithm with multiple grid constraints

As the chip density grows, wiring circuits on a VLSI chip becomes hard. It is then important to leave feed-through channels in the layouts of cells and macros. One strategy to achieve this goal is to keep wires on their respective wiring grids. This requirement presents a new constraint to the compaction problem of cells and macros. In this paper, a new efficient algorithm is proposed to solve such compaction problem on multiple grids.