SOLVING THE NET MATCHING PROBLEM IN HIGH-PERFORMANCE CHIP DESIGN

In high-performance chip design, the problem of net matching is often critical for achieving correct circuit performance. We adopt a conserv ative design, to route all matched nets with identical topologies and equal wire lengths to achieve zero skew. The problem is formulated as a variant of the D-dimensional Steiner tree problem. We propose a two- stage solution, The first stage uses an iterative improvement strategy to generate the Steiner tree topology for all the nets. The second st age places the nodes using one of two methods. The first approach expr esses the optimal Steiner node positions as a linear programming solut ion, with average computational complexity O(n(2)m(2)), where n is the number of nets and m is the number of pins. Improved efficiency is ac hieved under the other approach by transforming the Manhattan metric t o an l(infinity) norm using a 45 degrees rotation of the solution spac e. The norm is then approximated by either an l(lambda) norm, for suit ably large values of lambda, or an exponential ''penalty'' function. T he solution space in both approaches becomes strictly convex, allowing us to apply a greedy approach which converges to an optimal solution with great efficiency, leading to a dramatic speed-up versus the linea r programming approach.