Accurate net models for placement improvement by network flow methods

An efficient iterative improvement procedure for row based cell placement is described with special emphasis on the objective function used to model net lengths. We prove that minimizing net length estimated with our new net model also minimizes the half perimeter of a rectangle enclosing all pins of a net. Contrary to the half perimeter the new objective function allows to compute costs for assigning cells to locations independently for all cells to be placed simultaneously. This offers our algorithm an important advantage compared to other iterative improvement techniques: Many cells can be placed simultaneously by formulating placement as a network flow problem. Our algorithm is superior to Timber-WolfSC 5.4, which minimizes the half perimeter. This is shown on benchmark circuits with up to 14% smaller area computed in one order of magnitude less cpu-time.