Accurate net models for placement improvement by network flow methods

Abstract

An efficient iterative improvement procedure for row based cell placement is described. Special emphasis is placed on the objective function used to model net lengths. It is shown that minimizing the net length estimated with the 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 permits computation of costs for assigning cells to locations independently for all cells to be placed simultaneously. This provides the algorithm an important advantage compared to other iterative improvement techniques: many cells can be placed simultaneously by formulating placement as a network flow problem. The algorithm is superior to Timber-WolfSC 5.4, which minimizes the half perimeter.