Abstract
For high-frequency design, buffer and flip flop insertion become inevitable for interconnect delay optimization. To the best of our knowledge, all existing works perform buffer and flip flop insertion on a given routing tree topology. However, the given topology may greatly limit the effectiveness of buffer and flip flop insertion. In this thesis, we present a method which simultaneously constructs a routing tree and performs buffer and flip flop insertion subject to latency constraints. We also propose four speed-up techniques to further reduce the computation time. Experimental results show that as compared to a sequential method which separates the tree construction and buffer/flip flop insertion into 2 steps, our method can always find a feasible solution for each test case while the sequential method can do so with only up to 56% probability. For those test cases in which both the sequential method and our method can generate feasible solutions, our method has up to 94% chances to bring out solutions of larger slacks at source pins.