Magma – Design Automation: Component Placement on Chips #SWI2002

The ‘holey cheese’ problem

One of the steps in the design process of chips is the positioning of every single component or ‘cell’ on the chip. The cells are mutually connected by wires. The wiring scheme is given, and in this phase of the design process, the positioning of the various cells must be determined. Some (relatively few) cells have a prescribed position.

For the classical positioning problem, one considers the chip as a two-dimensional plane; the cells are modeled by rectangles of various sizes. The positioning has to satisfy some conditions:

1. the cells must be placed within a certain rectangle (core area)
2. cells are not allowed to overlap
3. the total wire length must be minimized.

For this problem many algorithms are known, each one with its specific pros and cons.

The problem becomes more difficult when large parts of the core area are excluded from positioning, often caused by large, functional components that were placed beforehand (one could think of memory or components that are designed by other companies). The remaining ‘free area’ within the core area is usually comparable to cheese with holes or ‘holey cheese’. Obviously, the cells cannot be placed on the blockages, and this additional requirement makes the positioning problem significantly harder.