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

Author

Sapatnekar, Sachin S.

Author_Institution

Dept. of Electr. & Comput. Eng., Minnesota Univ., Minneapolis, MN, USA

Volume

19

Issue

5

fYear

2000

fDate

5/1/2000 12:00:00 AM

Firstpage

550

Lastpage

559

Abstract

Crosstalk is generally recognized as a major problem in integrated 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 worst 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 of nets, and it is amenable to being incorporated into the inner loop of a timing optimizer. To illustrate this, the method is applied to reduce the effects 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

Keywords

circuit layout CAD; circuit optimisation; circuit simulation; computational complexity; crosstalk; delays; integrated circuit layout; network routing; timing; channel routing; crosstalk; inner loop; integrated circuit design; optimal channel routing; polynomial-time complexity; timing model; timing optimizer; worst case complexity; Circuit synthesis; Cost function; Crosstalk; Delay effects; Delay estimation; Integrated circuit measurements; Polynomials; Routing; Timing; Wires;

fLanguage

English

Journal_Title

Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.845079

Filename

845079