almost optimum placement legalization by minimum cost flow and dynamic programming
VLSI placement tools usually work in two steps: First, the cells that have to be placed are roughly spread out over the chip area ignoring disjointness ( global placement ). Then, in a second step, the cells are moved to their final position such that all overlaps are removed and all additional constraints are met ( detailed placement or legalization ).We consider algorithms for legalization. In particular, we analyze a generic legalization algorithm based on minimum cost flows and dynamic programming. Specializations are being used in industry for many years, and an improved version was proposed very recently in [2]. The objective of all these algorithms is to minimize the weighted sum of (squared) movements, i.e. they assume the placement to be already optimized except for not being legal.To evaluate results, we propose two different lower bounds for the legalization problem, one based on linear assignment, and the other one based on an integer linear programming relaxation. We prove that the second lower bound is always at least as good as the first one. We also show how to compute the bounds efficiently. We then give an extensive experimental analysis of the algorithms and the lower bounds by testing them on a set of recent industrial ASICs with up to 2.4 million cells. In particular, we show that the gap between the new algorithm and the better lower bound is usually less than 10 percent. This proves that the legalization problem is solved almost optimally.Besides (weighted) total (squared) movement, we also consider various other objectives like wirelength, timing, and routability. Our experiments demonstrate that minimizing total (weighted, squared) movement has almost no negative effect on the timing properties, routability and netlength. Therefore the new algorithm will help in overall design closure.
placement legalization cost flow dynamic programming tools posit constraint detailed placement algorithm generic specialization industrial version object movement evaluation lower bound assignment integer linear program computation experience experimentation analysis test timing demonstrate effect help design minimum-cost flow