A detailed placement process which optimizes cell placement with up to one hundred
percent densities in a linear run time. The output from a conjugate-gradient coarse
placement process is input to the detailed placement process. A dynamic programming
technique is used to optimize cell placement by swapping cells between two or more
rows. The search space is pruned beforehand. A greedy cleanup phase using an incremental
row placer is used. Thereby, the detailed placement process handles congestion
driven placements characterized by non-uniform densities expeditiously and efficiently.