FaSa: a fast and stable quadratic placement algorithm

摘要

Placement is the important step in VLSI design. Its speed affects the total speed of design flow, and its result can have a significant effect on subsequent design steps. The quadratic placement method is one of the most successful placement methods. In this paper, we propose a new fast and stable placement algorithm, FaSa. It uses the quadratic placement model and the method of Lagrange multipliers to solve the problem and incremental LU factorization to solve equations. Fasa is much faster than the old algorithms and the total wire length is comparable with other algorithms. FaSa is very stable, and does not depend on any coefficient. We test it with several real circuits. From the results, we see that FaSa is 3 times faster than the previous algorithm.