Lagrangian relaxation based register placement for high-performance circuits

To achieve low-skew clock distribution, clock tree synthesis (CTS) for local clock optimization is used so far. Challenged by the increasing design complexity and performance demand, a new strategy for local clock optimization is used along with register placement for high-performance circuits. Special local clock distribution is used and registers are legalized to fit required skew. In this paper, we study the register placement problem and formulate it as a minimum weighted maximum independent set problem on a weighted conflict graph. Then, we propose a novel Lagrangian relaxation based algorithm. By relaxing the overlap conflict constraints, the problem is transformed into a minimum weighted bipartite matching problem. Experiments show that our method can efficiently place all registers without overlaps with minimized total register movement.