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 an heuristic approach to decompose the minimum delay Steiner tree problem into a hierarchy and to construct the sub-trees respectively based on a 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