Performance evaluation of tetris-based legalization heuristics

Abstract

Algorithms for standard cell placement legalization have attracted significant research efforts in the past. A prominent member of this category is the Tetris algorithm which is a simple and particularly fast method for legalizing an initial placement containing overlaps. In the relevant literature sophisticated legalization schemes were proposed using Tetris as a performance yardstick. In order to achieve better performance such schemes usually sacrifice the fast running time of Tetris by a large margin. In this paper we turn our focus on simple Tetris variations that improve performance without seriously compromising running time. Specifically, we present five generic heuristic variations of the initial Tetris algorithm. Through experimental evaluation we conclude on the merits of each approach. © 2016 ACM.