A timing model incorporating the effect of crosstalk on delay and its application to optimal channel routing

Crosstalk is generally recognized as a major problem in intergrated circuit design. This paper presents a novel approach to the efficient measurement of the effect of crosstalk on the delay of a net using an algorithm whose w orst case complexity is polynomial-time in the number of nets. The cost of the algorithm is seen to be O(n log n) in practice, where n is the number o f nets, and it is amenable to being incorporated into the inner loop of a t iming optimizer. To illustrate this, the method is applied to reduce the ef fects of crosstalk in channel routing, where it is seen to give an average improvement of 23% in the delay in a channel as compared to the worst case, as measured by SPICE.