Buffered interconnect tree optimization using Lagrangian relaxation and dynamic programming

摘要

This paper presents a new synthesis method, based on combining Bottom-up Dynamic Programming and Lagrangian Relaxation, for finding effective solutions to a delay-constrained buffered interconnect tree. By introducing redundant length constraints and relaxing them using Lagrangian Relaxation, our approach decomposes the original problem into a series of dynamic programming sub-problems to synthesize the buffered interconnect tree. We then use an iterative strategy to minimize the interconnect cost and also to satisfy timing and length constraints.