Heuristics for iterative detailed standard cell placement

Abstract

In cell placement a number of cells with rectangular shapes, must be placed inside a chip area so that no cells overlap and a target function is optimized. In standard cell placement all rectangles have the same width and the chip area is split into rows of equivalent width. Cells must be placed inside rows without overlaps and without exceeding row boundaries. A final solution is obtained using at least two stages. In the first stage, often called global placement, cells are distributed so as to optimize the target function. This initial distribution might violate problem constraints, therefore at a second stage often referred to as detailed placement cells are assigned to rows and overlaps are alleviated. In this paper we focus on heuristics in the context of iterative detailed placement whereby after assigning cells to rows, an iterative process further improves the optimization function, in our case wire length. The basis of the search mechanism is cell swapping. Through experimental evaluation we identify useful trade-offs between solution quality and execution time for the proposed search methods. © 2016 ACM.