Skip to main content

Heuristics to Augment the Performance of Tetris Legalization: Making a Fast but Inferior Method Competitive

Buy Article:

$107.14 + tax (Refund Policy)

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.


Document Type: Research Article

Publication date: June 1, 2017

More about this publication?
  • The electronic systems that can operate with very low power are of great technological interest. The growing research activity in the field of low power electronics requires a forum for rapid dissemination of important results: Journal of Low Power Electronics (JOLPE) is that international forum which offers scientists and engineers timely, peer-reviewed research in this field.
  • Editorial Board
  • Information for Authors
  • Subscribe to this Title
  • Terms & Conditions
  • Ingenta Connect is not responsible for the content or availability of external websites
  • Access Key
  • Free content
  • Partial Free content
  • New content
  • Open access content
  • Partial Open access content
  • Subscribed content
  • Partial Subscribed content
  • Free trial content