A postprocessing algorithm for crosstalk-driven wire perturbation

Much of the previous work on crosstalk minimization attempted to handle cro sstalk during the process of routing the nets. However, this necessitates t he estimation of the expected crosstalk due to nets that are yet to be rout ed. In contrast, postprocessing algorithms can use accurate crosstalk measu rements to respace the wires, thus improving the crosstalk even in routings produced by crosstalk-aware routers. However, the postprocessing algorithm s presented so far have been restricted either by the use of a gridded mode l or by the difficulty of optimizing the highly nonlinear crosstalk-based o bjective functions. We address the problem of minimizing the peak crosstalk in a routed region by respacing its critical nets and their neighbors. We study the variation of the crosstalk in a net and its neighbors when one of its trunks is pertu rbed, showing that the trunk's perturbation range can be efficiently divide d into subintervals having monotonic or unimodal crosstalk variation. This result enables us to determine the optimum location for the trunk without n eeding to solve any nonlinear equations. Using this, we construct an algori thm to minimize the peak crosstalk in the nets of a gridless channel. Altho ugh we present our results in terms of channel routing, our theory is also applicable to more general routing models. Furthermore, our crosstalk model subsumes the models used in most prior works on noise-aware routing. Our e xperiments verify the effectiveness of our approach.