A Tetris-based legalization heuristic for standard cell placement with obstacles

Legalization techniques are used both as a final stage and potentially as part of an iterative process of a global cell placement algorithm that distributes cells over a chip area in order to optimize criteria such as wirelength, routability, thermal dissipation etc. Although very efficient dynamic programming algorithms exist for standard cell placement legalization they usually incur high computational complexity, thus, might not be appropriate for acting as subcomponents in an iterative global placement process. On the other hand fast, single pass approaches such as Tetris heuristic, may offer low performance in terms of final placement quality. In this paper we turn our attention to legalization in standard cell placement under the presence of obstacles, with the aim of developing a fast yet efficient solution for the problem. The proposed heuristic is based on Tetris and involves judicious chip area splitting. Experiments with ibm circuits demonstrate that the resulting scheme, called OBstacle-aware Area Splitting Tetris (OBAST), offers significant performance improvement both in terms of solution quality and running time.