Hybrid routing tree with buffer insertion under obstacle constraints

Performance optimization in very-large-scale integration (VLSI) design is the key success in today´s design automation methodologies. One of the performance issues is the interconnect delay in deep sub-micron VLSI circuits. The interconnect delay becomes more dominant compared to gate delay when the size of the gates is reduced. This paper presents an algorithm to optimize the timing performance of the routing tree under obstacle constraints. It is known that simultaneous routing and buffer insertion is proven to be NP-complete while the two-step approach may produce a poor solution. Therefore, we propose a hybrid algorithm that can modify a given routing tree simultaneously with buffer insertion. This paper describes this algorithm and we present experimental results that show the proposed algorithm can improve the timing of the routing tree significantly with low execution time.