A 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. A new efficient algorithm is proposed to solve such a compaction problem on multiple grids. The worst-case time complexity of the algorithm is O ((M+1) (|V|+|E|)). The algorithm has been implemented in a compactor and applied to the layout designs for both microprocessor chips and ASIC chips