Performance-Driven Steiner Tree Algorithms for Global Routing

This paper presents two performance-driven Steiner tree algorithms for global routing which consider the minimization of timing delay during the tree construction as the goal. One algorithm is based on nonlinear optimization method, another uses heuristic approach to guide the construction of Steiner tree. A new timing model is established which includes both total length and critical path between source and sink in delay formulation, and an upper bound for timing delay is deducted and used to guide both algorithms. Experiment results are given to demonstrate the effectiveness of the two algorithms.