For all the cells in the netlist a position on the chip must be found. The position must satisfy geometrical constraints and should minimize certain metrics such as the required wiring length for connecting all the cells. To simplify the process, often placement is broken up into sub-steps:
- Global placement: Find rough positions of cells. Overlaps are allowed but the average density should be below 1 such that in a later step it is possible to arrange the cells without overlap.
- Buffer & Tie-cell insertion: The netlist must probably be modified after global placement.
Usually synthesized netlists contain nets which have constant logic values
1. Constant nets are driven by 'tie'-cells, which tie the signal to either
1. It makes sense to put tie-cells close to where they are needed. For this reason they are best created after global placement when the necessary information is available. Similarly, some nets may have too many cells attached such that the driver cell is too weak to drive all the load. In such cases it is necessary to insert buffers. The structure of the buffer network depends also on the locations of the driver and the loads. There fore buffer insertion is best done after global placement.
- Legalization: Arrange the cells such that they don't overlap and put them into rows such that the power rails and wells are connected by abutment.
- Filler insertion: Remaining space between the cells must be filled with 'filler'-cells
- to ensure connectivity of the power rails and wells
- to stabilize the power rails with capacitors
- to meet certain metal density constraints necessary for fabrication
- Detail placement
- Perform local optimizations
- Mirroring cells, switching cells locally
Good overview: http://cc.ee.ntu.edu.tw/~ywchang/Courses/PD_Source/EDA_placement.pdf