Heuristics to augment the performance of tetris legalization: Making a fast but inferior method competitive

Abstract

As process minimum feature sizes shrink, interconnect capacitance becomes a larger proportion of the total switched capacitance, thus standard cell and component placement increasingly affects power consumption. Therefore, minimizing the total interconnect wire length becomes a power reduction exercise as well. The final step of a standard cell placement process consists of legalization where the target is to eliminate overlaps as well as aligning cell positions to eligible rows. The simplest, yet fastest method in the literature is the Tetris algorithm which is commonly used as a performance yardstick for other more efficient but computationally demanding methods. In this paper we propose and evaluate standalone variations to the basic Tetris algorithm that aim at significantly improving its performance sometimes at the expense of running time. We then introduce combinations of the standalone heuristics. All heuristics are evaluated with commonly used benchmark circuits, assuming global placements produced by Gordian and NTUplace3. Results indicate that performance gains over the basic Tetris scheme of up to 75% in half perimeter wire length, 94% in displacement and 83% in interconnect power are achievable. Moreover, certain heuristics are able to improve half perimeter and displacement, while also reducing running time. Copyright © 2017 American Scientific Publishers. All rights reserved.