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