An Extensible Legalization Framework for Multiple Physical Design Constraints

Legalization tries to remove all overlaps with minimum wire-length or total displacement while meeting design rules as much as possible. In advanced technology circuit designs, many cells of multi-row height and complex design rules have brought challenges to legalization. Academic researches usually focus on the legalization problem of one particular design rule, and no legalization framework considers multiple design rules. Therefore, this paper presents an extensible and general legalization framework that can support the replacement of legalization algorithms and the expansion of design rules. First, we design a complete basic operation module compatible with multiple legalization algorithms. Then, we develop an extensible design rules checking module to satisfy numerous design rules and quickly support new rules. Finally, we propose two acceleration techniques for the framework. Experimental results show that our algorithm framework can achieve a 3% reduction on maximum cell displacement, a 7% reduction on average cell displacement, and 26% less legalization runtime than the state-of-the-art commercial tool Innovus when dealing with multiple design rules on test cases derived from industrial designs.