Rj. Carragher et al., SOLVING THE NET MATCHING PROBLEM IN HIGH-PERFORMANCE CHIP DESIGN, IEEE transactions on computer-aided design of integrated circuits and systems, 15(8), 1996, pp. 902-911
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.