An Efficient Hierarchical Timing-Driven Steiner Tree Algorithm for Global Routing

摘要

In this paper, we propose a hierarchical timing-driven Steiner tree algorithm for global routing which considers the minimization of timing delay during the tree construction as the goal. The algorithm uses heuristic approach to decompose the problem of minimum delay Steiner tree into hierarchy and to construct the sub-trees respectively based on dynamic programming technique. Taking the net topology into consideration, we build the final routing tree by reconnecting the sub-trees at each level recursively and then improve the connection with the objective of minimizing the delay from source to sink pins on the critical path. Meanwhile, some efficient strategies have been proposed to speed up the solving process. Experimental results are given to demonstrate the efficiency of the algorithm.