04/01/2000 09:00 AM
Computer Engineering
In this paper we present an efficient algorithm for determining the optimal spacing needed to eliminate cross-talk induced noise violations and cross-talk induced delay violations on nets with nonnegligible interconnect resistance. Since cross-talk violations cannot be accurately detected until very late in the routing process, we base our formulation on the topological representation of the detailed Manhattan routing in order to be able to easily identify and quantify uncommitted routing resources available to a net very late in the routing process. Our experimental results demonstrate that the performance of our algorithm is best characterized as O(n log(n)) in the number of spacing variables.
